Discussione:Macchina di Turing/Domande
Aggiungi argomento
Questo è lo spazio per esprimere dubbi e domande sulla lezione. Se vuoi far presente un problema alla lezione in sé, come, ad esempio, un errore, devi usare la pagina di discussione relativa. I commenti presenti in questa pagina non devono essere conformi al punto di vista neutrale, ma, in ogni caso, devi rimanere in argomento ed evitare insulti, parolacce e altre parole che possono riscaldare gli animi. Sii comprensivo e gentile. Una discussione civile e un dibattito educato rende le pagine delle domande luogo amichevole.
Ricorda di firmare i commenti usando 4 tildi (~~~~), che verranno automaticamente sostituite col tuo nome utente e la data corrente.
Clicca qui per aggiungere una nuova domanda · Rispondi a una domanda già esistente
Salve!
Cercherò di essere il più breve possibile, ma prima di tutto vorrei ringraziare l’autore o gli autori della lezione sulla macchina di Turing, un soggetto al quale, benché sia un profano in materia, mi sto interessando in questo momento, diciamo così, per degli scopi culturali d’altro genere e più generali. Tra tutti i documenti che ho letto a questo riguardo, fino adesso questa lezione è sicuramente il più chiaro che ho trovato e quello che mi è servito di più per la sua comprensione.
Tuttavia, c’è qualcosa che mi è rimasto oscuro, ragione per la quale scrivo e posto questo messaggio nella sezione «Domande». Si tratta del riconoscitore di Turing multitestina, in particolare il calcolo delle «k marcature su un simbolo solo». A prima vista la questione sembrerebbe semplice: se, per esempio, una macchina T con una sola testina simula una macchina M con 3 testine, dal momento che ciascuna di queste ultime può occupare allo stesso tempo la stessa cella, ogni simbolo dell’alfabeto del nastro potrà essere letto/scritto dalle tre testine e, dunque, avere tre marcature differenti. Ciò che non riesco a comprendere è lo svolgimento del calcolo della formula che fa riferimento al binomio di Newton. Probabilmente, anzi sicuramente, ciò proviene dalle mie lacune in matematica, una materia che adoro, ma di cui da lungo tempo avevo interrotto lo studio per vari motivi.
In breve, la formula per trovare il numero di coppie, terne, quaterne, ecc., non mi è chiara. Per esempio, per le terne la formula ½ * (k su 3) come si svilupperebbe assegnando un valore numerico a k? In questa formula, k dovrebbe corrispondere al numero di testine, dunque essere = 3. Ma allora il 3 del coefficiente binomiale k su 3 si riferisce a cosa, forse al numero di marcature corrispondenti da apporre sotto ogni simbolo dell’alfabeto, dunque una per ogni testina?
Come ho già detto, sicuramente l’incomprensione riguarda le mie lacune in matematica, ma può anche darsi – non lo so – che in questa parte dello scritto la presentazione delle formule e dei calcoli sia un po’ sbrigativa, come non è il caso altrove.
Grazie.