Macchina di Turing, ipotetico dispositivo di calcolo introdotto nel 1936 dal matematico e logico inglese Alan M. Turing. Turing originariamente concepì la macchina come uno strumento matematico in grado di riconoscere infallibilmente le proposizioni indecidibili, cioè quelle affermazioni matematiche che, all’interno di un dato sistema assiomatico formale, non possono essere dimostrate vere o false. (Il matematico Kurt Gödel aveva dimostrato che tali proposizioni indecidibili esistono in qualsiasi sistema abbastanza potente da contenere l’aritmetica). Turing invece dimostrò che non può mai esistere un metodo algoritmico universale per determinare se una proposizione è indecidibile.
La macchina di Turing non è una macchina in senso ordinario, ma piuttosto un modello matematico idealizzato che riduce all’essenziale la struttura logica di qualsiasi dispositivo di calcolo. Come previsto da Turing, la macchina esegue le sue funzioni in una sequenza di passi discreti e assume solo uno di una lista finita di stati interni in ogni momento. La macchina stessa consiste in un nastro infinitamente estensibile, una testina che è capace di eseguire varie operazioni sul nastro, e un meccanismo di controllo modificabile nella testina che può memorizzare indicazioni da un insieme finito di istruzioni. Il nastro è diviso in quadrati, ognuno dei quali è vuoto o ha stampato sopra uno di un numero finito di simboli. La testina del nastro ha la capacità di muoversi verso, leggere, scrivere e cancellare ogni singola casella e può anche cambiare in un altro stato interno in qualsiasi momento. Qualsiasi atto di questo tipo è determinato dallo stato interno della macchina e dalla condizione del quadrato scansionato in un dato momento. L’output della macchina – cioè la soluzione di una domanda matematica – può essere letto dal sistema una volta che la macchina si è fermata. (Tuttavia, nel caso delle proposizioni indecidibili di Gödel, la macchina non si fermerebbe mai, e questo divenne noto come il “problema dell’arresto”.)
Incorporando tutte le caratteristiche essenziali dell’elaborazione delle informazioni, la macchina di Turing divenne la base per tutti i successivi computer digitali, che condividono lo schema di base della macchina: un dispositivo di input/output (nastro e lettore), una memoria (stoccaggio del meccanismo di controllo) e un’unità di elaborazione centrale (meccanismo di controllo).