La macchina di Turing

Nel 1936 il matematico inglese Alan Turing progettò una macchina ideale che fosse in grado di risolvere problemi.
Questa macchina, nota come macchina di Turing, si compone di un nastro, che possiamo immaginare di carta e di una testina di lettura/scrittura (TLS) che scorre sopra il nastro.
La macchina funziona su intervalli discreti di tempo; ad ogni istante il suo stato dipende dallo stato precedente; la sua struttura è:

a. Il nastro è suddiviso in singole celle nelle quali può essere scritto un simbolo appartenente un alfabeto predefinito; il nastro è da considerarsi infinito a destra e a sinistra.
b. La TLS deve essere in grado di leggere i simboli scritti in una cella, di scrivervi un nuovo simbolo, di muoversi in entrambi i versi lungo il nastro.
c. La macchina che comanda la testina è definita istante per istante da una quintupla di elementi:
1. s: lo stato della macchina all'istante presente;
2. i: il simbolo letto all'istante presente;
3. S(s, i): lo stato della macchina all'istante successivo; è funzione dei primi due parametri.
4. I(s, i): il simbolo scritto dalla macchina all'istante successivo; è funzione dei primi due parametri.
5. V(s, i): il verso (movimento) della macchina (destra/sinistra); è funzione dei primi due parametri.

Questa macchina, concettualmente semplice, è in grado di risolvere una classe di problemi molto vasta; un esempio semplice ma non banale è quello di stabilire se una sequenza di parentesi è ben formata.
Ma quanto è vasta la classe dei problemi risolubili con la macchina di Turing? secondo una celebre congettura di Alonzo Church questo insieme coinciderebbe con quello delle funzioni computabili.
Si tratta comunque di una classe non banale, nel senso che esistono problemi che non sono risolubili con la macchina di Turing; lo stesso Turing dimostrò che non è risolubile il problema dell'arresto, in altri termini non è possibile una macchina di Turing in grado di decidere se un'altra macchina di Turing si arresterà o no, dati uno stato e un nastro iniziale.
Turing studiò in particolare la cosiddetta macchina universale, una macchina di Turing in grado di imitare una qualsiasi particolare macchina di Turing.
La macchina universale di Turing ha costituito il primo modello del futuro computer programmabile. In un certo senso gli odierni computer programmabili sono macchine universali di Turing.