October 26
La macchina di Turing è stato descritto nel 1937 da Alan Mathison Turing, un matematico inglese e pioniere dell'informatica. Una macchina di Turing non è una macchina in senso tradizionale; non è un dispositivo meccanico che è destinato ad essere effettivamente costruito. Invece, è una macchina concettuale o matematico.
Alan Mathison Turing nacque a Paddington, Londra, nel 1912. Ha studiato matematica all'Università di Cambridge, dove ha successivamente insegnato, prima di trasferirsi a Princeton University nel 1936. Ritornò in Inghilterra nel 1938 e durante la seconda guerra mondiale ha lavorato per il Codice Governo e Cypher School a Bletchley Park in Gran Bretagna, dove ha guidato il team responsabile per il cracking il codice tedesco Enigma. Ha lavorato per il National Physical Laboratory e l'Università di Manchester dopo la guerra ed è stato eletto come un compagno della Royal Society nel 1951. A seguito di una condanna per omosessualità nel 1952, Turing si suicidò nel 1954 a 41.
Una macchina di Turing è, infatti, un semplice calcolatore astratta. Esso può essere visualizzato come avente una lunghezza infinita, 1-D nastro divisa in celle, ciascuna delle quali contiene uno 0 o un 1. Essa ha anche una testina di lettura e scrittura che può muoversi avanti e indietro lungo il nastro per accedere al contenuto di ogni cella. Il nastro può essere pensato come memoria della macchina di Turing - ma, ovviamente, infinita - e la testina di lettura-scrittura come il bus di memoria.
Alan Turing ha descritto la macchina di Turing, nel tentativo di rispondere a una delle domande fondamentali della filosofia della scienza informatica, vale a dire, che cosa significa per un compito di essere calcolabile. Intuitivamente, un compito è computabile se può essere suddiviso in una serie di istruzioni - altrimenti noto come "algoritmo" - che può essere eseguita da una macchina di qualche tipo per completare l'operazione. Tuttavia, diverse macchine possono essere in grado di eseguire istruzioni diverse e completare i compiti diversi, quindi ci sono un numero infinito di macchine di Turing.
Tuttavia, Turing immaginò ogni algoritmo, per ogni compito particolare, scritto come un insieme di istruzioni in una forma standard. Se il modulo standard per ogni attività viene fornita a una singola macchina di Turing, la macchina può essere fatto per interpretare le istruzioni e procedere nello stesso modo come particolari macchine di Turing ed è in grado di completare tutti i compiti possibili. Questo fenomeno è noto come "macchina di Turing universale".