Le macchine di Turing spiegate
Nel 1936, prima che esistessero i computer elettronici, il matematico ventiquattrenne Alan Turing si chiese che cosa significhi che un calcolo è meccanico. La sua risposta fu una macchina immaginaria così semplice che difficilmente potrebbe fare di meno: legge e scrive simboli su un nastro, una cella alla volta, secondo una tabella fissa di regole. Quella macchina finì per definire il calcolo stesso, e mostrò che ad alcune domande nessun computer potrà mai rispondere.
La domanda di Turing
Nel 1928 David Hilbert chiese se esista una procedura meccanica che decida, per ogni enunciato della matematica, se può essere dimostrato: l'Entscheidungsproblem. Per rispondere, qualcuno doveva dire esattamente che cos'è una procedura meccanica. Nel suo articolo del 1936 On Computable Numbers, Turing immaginò un impiegato che lavora con carta e matita e ridusse il lavoro ai suoi passi più piccoli: guardare un simbolo, cambiarlo, spostarsi su un simbolo vicino e ricordare un po' di ciò che si stava facendo. Il risultato fu la macchina di Turing.
La macchina
Una macchina di Turing ha un nastro diviso in celle, infinito in entrambe le direzioni, ognuna delle quali contiene un simbolo, di solito il simbolo vuoto. Una testina si trova su una cella e la macchina è in uno di un numero finito di stati. Una tabella di regole indica, per ogni stato e ogni simbolo che la testina può leggere, il simbolo da scrivere, la direzione in cui spostarsi e lo stato successivo. La macchina applica una regola per passo. Quando entra in uno stato di arresto si ferma, e ciò che resta sul nastro è la sua risposta.
Programmi come tabelle di regole
Ogni tabella di regole è un programma. Per aggiungere 1 a un numero binario, la macchina va all'estremità destra del numero, poi si sposta a sinistra trasformando gli 1 in 0 finché trova uno 0 o una cella vuota, che trasforma in 1. Per controllare se una parola è palindroma, cancella il primo simbolo, lo ricorda nel suo stato, corre all'altra estremità e controlla che l'ultimo simbolo corrisponda, poi ripete. I programmi lunghi, come uno che moltiplica o ordina, sono costruiti con gli stessi pochi tipi di regole.
La macchina universale
L'idea più importante di Turing fu che la tabella di regole stessa può essere scritta sul nastro. Una macchina di Turing universale legge la descrizione di qualsiasi altra macchina e del suo input, e poi la imita passo dopo passo. Una sola macchina fissa può quindi eseguire ogni programma: è il principio di ogni computer a programma memorizzato, in cui il software è solo un insieme di dati in memoria. Ogni sistema in grado di imitare una macchina di Turing universale si dice Turing-completo, compresi tutti i linguaggi di programmazione, il Gioco della vita di Conway e l'automa cellulare Rule 110.
La tesi di Church-Turing
Nello stesso anno Alonzo Church descrisse il calcolo con il suo lambda calcolo, e le due definizioni risultarono calcolare esattamente le stesse funzioni. Lo stesso valse per ogni modello successivo, dalle macchine a registri ai processori moderni. La tesi di Church-Turing afferma che tutto ciò che può essere calcolato con una procedura passo per passo può essere calcolato da una macchina di Turing. Non può essere dimostrata, perché «procedura passo per passo» è un'idea informale, ma non è mai stato trovato un controesempio.
Il problema della fermata
Turing mostrò poi che alcune domande non hanno una risposta meccanica. Supponiamo che una macchina possa decidere, per ogni programma e ogni input, se quel programma prima o poi si ferma. Costruiamo un nuovo programma che interroga questo decisore su se stesso e poi fa il contrario: se gli viene detto che si ferma, gira all'infinito, e se gli viene detto che gira all'infinito, si ferma. Entrambe le risposte sono sbagliate, quindi il decisore non può esistere. Il problema della fermata è indecidibile, e con esso l'Entscheidungsproblem: nessun algoritmo può risolvere ogni questione matematica.
Castori indaffarati
Nel 1962 Tibor Radó trasformò il problema della fermata in un gioco: tra tutte le macchine con n stati e i simboli 0 e 1 che si fermano quando vengono avviate su un nastro vuoto, quale scrive il maggior numero di 1, e quanti passi può compiere una macchina del genere? Questi numeri, i valori del castoro indaffarato, crescono più in fretta di qualsiasi funzione calcolabile, perché un modo per calcolarli risolverebbe il problema della fermata. I valori noti sono 6, 21 e 107 passi per due, tre e quattro stati; per cinque stati la macchina campione di Heiner Marxen e Jürgen Buntrock compie 47.176.870 passi, un valore dimostrato nel 2024 dalla collaborazione online bbchallenge con una dimostrazione verificata al computer. Per sei stati si conoscono macchine che vanno avanti per più passi di quanti se ne possano scrivere nella notazione ordinaria.
Esplora
Apri il simulatore di macchina di Turing per eseguire otto programmi già pronti o scriverne di tuoi. Segui la testina passo dopo passo e guarda quale regola scatta, osserva il contatore che non si ferma mai, verifica palindromi e fai girare i castori indaffarati: i 107 passi della macchina campione a quattro stati entrano nel diagramma, e i 47 milioni di passi della macchina campione a cinque stati richiedono pochi secondi alla velocità Velocissima.
Domande frequenti
La macchina di Turing è mai stata costruita?
Non come la descrisse Turing, dato che il suo nastro è infinito, ma all'idea seguirono presto veri computer a programma memorizzato, che lo stesso Turing contribuì a progettare dopo la seconda guerra mondiale. Da allora alcuni appassionati hanno costruito modelli funzionanti in legno, con i LEGO e perfino nel Gioco della vita, tutti con un nastro finito, che basta per qualsiasi calcolo che termina.
Qual è la differenza tra i numeri di passi 14 e 21 per tre stati?
Le domande del castoro indaffarato sono due: il maggior numero di 1 scritti e il maggior numero di passi compiuti. Per tre stati, la macchina del simulatore scrive il massimo di sei 1 in 14 passi, mentre un'altra macchina a tre stati compie il massimo di 21 passi ma lascia solo cinque 1. Per due, quattro e cinque stati, una sola macchina vince in entrambe.
Turing-completo significa potente?
Significa capace di calcolare qualsiasi cosa calcolabile, con abbastanza tempo e memoria, il che non dice nulla sulla velocità. Una macchina di Turing ha bisogno di molti passi per un'aritmetica semplice, e alcuni sistemi sono Turing-completi quasi per caso, come giochi di carte, formule dei fogli di calcolo e la redstone di Minecraft.
Perché un computer non può semplicemente eseguire un programma per vedere se si ferma?
Eseguirlo mostra che un programma si ferma, se si ferma, ma se non si è ancora fermato non puoi sapere se non si fermerà mai o se ha solo bisogno di più tempo. La dimostrazione di Turing mostra che nessun metodo più astuto funziona per ogni programma, anche se per molti programmi particolari la domanda ha una risposta.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il simulatore di macchina di Turing