La macchina di Turing in primo luogo è 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 si tratta di un apparato meccanico che è destinato ad essere effettivamente costruita. Invece, è una macchina concettuale o matematica.

Alan Turing

Alan Mathison Turing nacque a Paddington, Londra, nel 1912. Studiò matematica all'Università di Cambridge, dove ha successivamente insegnato, prima di trasferirsi all'Università di Princeton nel 1936. Ritornò in Inghilterra nel 1938 e durante la seconda guerra mondiale lavorato per il governo codice e Cypher School a Bletchley Park in Gran Bretagna, dove guidò la squadra responsabile per spezzare il codice Enigma tedesco. Lavorò per il National Physical Laboratory e l'Università di Manchester nel dopoguerra e fu eletto Fellow della Royal Society nel 1951. A seguito di una condanna per omosessualità nel 1952, Turing si suicidò nel 1954 a 41.

Calcolatore astratto

Una macchina di Turing è, infatti, un semplice computer astratto. Esso può essere visualizzato come avendo un nastro infinitamente lungo, 1-D, diviso in celle, ognuna delle quali contiene uno 0 o un 1. Ha anche una testina di lettura-scrittura che può muoversi avanti e indietro lungo il nastro per accedere al contenuto di ogni cella. Il nastro può essere pensato come la memoria della macchina di Turing..--ma è, naturalmente, infinito..--e la testina di lettura-scrittura come il bus di memoria.

Filosofia

Alan Turing ha descritto la macchina di Turing nel tentativo di rispondere a una delle domande fondamentali nella filosofia dell'informatica, vale a dire, che cosa significa per un compito di essere calcolabile. Intuitivamente, un compito è calcolabile se si possono essere suddivisi in una serie di istruzioni..--altrimenti noto come un "algoritmo"--che può essere effettuato da una macchina di qualche tipo per completare l'attività. Tuttavia, diverse macchine possono essere in grado di eseguire diverse istruzioni e completare i compiti diversi, quindi ci sono un numero infinito di macchine di Turing.

Macchina di Turing universale

Tuttavia, Turing immaginato ogni algoritmo, per ogni specifica attività, scritto come un insieme di istruzioni in un modulo standard. Se il modulo standard per ogni attività è fornito ad una singola macchina di Turing, la macchina può essere fatto a interpretare le istruzioni e trasportarle fuori nello stesso modo come macchine di Turing particolari ed è in grado di completare tutte le attività possibili. Questo è ciò che è noto come una "macchina di Turing universale".