VII. 6. La macchina di Turing

1000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010100011101010100100101011101010100110100010100010101101000001101001000001010110100010011101001010000101011101001000111010010101 0000101110100101001101000010000111010100001110101000010010011101000101010110101001010110100000110101010010110100100100011010000000011010000001110101001010101011101000010011101001010101010101011101000010101011101000010100010111010001010011010010000101001101001010 0100110100100010110101000101110100100101011101001010001110101001010010011101010101000011010010101010111010100100010110101000010110101000100110101010101000101101001010100100101101010010010111010101001010111010100101001101010100001110100010010010101110101010010101 1101010100000111010100100000110101010100101110101001010110100010010001110100000001110100101001010101011101001010010010101110100000101011101000010001110100000101010011101000010100111010000010001011101000100001110100001001010011101000100001011010001010010111010001 0100101101001000001011010001010100100110100010101010111010010000011101001001010101011101010101001101001000101011010010010010110100000001011010000010001101000001001011010000000001101001010001011101001010100011010010100101011010000010011101001010100101101001001110 1010000001010111010100000011010101000101010110100101010110101000010101110101001001010111010100010010110101001000010111010000001110101001000101101010010100110101010001011101010010100101110101010000010111010101000001011101000000111010101000010101110100101010110101

E' abbastanza sorprendente che un dispositivo semplice come la macchina di Turing [104] rappresenti il più potente strumento di calcolo conosciuto, nel senso che per ogni problema per cui è nota una procedura di soluzione è possibile formulare un algoritmo eseguibile da una macchina di Turing.
La macchina di Turing contiene un insieme finito di stati, un alfabeto finito (comprendente un simbolo nullo) e un insieme finito di istruzioni. E' composta da una testina che possiede uno stato interno e può muoversi lungo un nastro infinito diviso in celle. Ogni cella contiene una lettera dell'alfabeto. Una istruzione è una quintupla del tipo (s, v, s', v', m), dove s indica lo stato attuale della testina, v il valore della cella sulla quale è posizionata la testina, s' il nuovo stato, v' il nuovo valore e m una azione di movimento (destra o sinistra). Per maggiori dettagli è utile visitare il sito Come osservare una macchina di Turing [105].
Ecco come vengono eseguite le istruzioni: se lo stato interno è uguale a s e il valore sotto la testina è v, la macchina passa allo stato interno s', scrive sul nastro il valore v' ed esegue il movimento specificato da m. L'esecuzione termina quando la macchina si trova in una condizione per la quale non è specificata alcuna istruzione. Per facilitare la comprensione di questo meccanismo è disponibile una simulazione [106] della macchina di Turing.
Ci sono alcune convenzioni comunemente usate nella macchina di Turing: i numeri sono rappresentati in notazione unaria e il numero intero n è rappresentato da una sequenza di n+1 1 consecutivi.
Malgrado l'estrema (o voluta) semplicità di questa macchina, essa risulta capace (con un adatto assegnamento di istruzioni) di risolvere problemi di grande complessità, ma la sua importanza non sta ovviamente in tale capacità (per la quale sono molto più convenienti gli elaboratori reali), ma nell'essere uno strumento concettuale che permette di definire rigorosamente gli algoritmi e di ottenere risultati di grande generalità. Le ricerche finora condotte fanno pensare che qualsiasi algoritmo possa essere realizzato mediante una macchina di Turing. Tale ipotesi viene detta "ipotesi fondamentale della teoria degli algoritmi" e l'accettarla significa che si considera la teoria degli algoritmi coincidente con la teoria della macchina di Turing.