Descrivere in maniera semplice la teoria che Turing elaborò per la definizione della sua macchina formale è un'impresa scoraggiante; ci proverò con l'aiuto di un sito di informatica.

La macchina di Turing deve possedere tre caratteristiche principali:

- un sistema di memorizzazione esterno dei dati immessi e di quelli elaborati;

- un dispositivo di lettura e di scrittura di tali dati;

- un meccanismo di controllo per stabilire le azioni da intraprendere.

L'unità esterna di memorizzazione della macchina di Turing è definita come un "nastro" (paragonabile proprio ad un nastro magnetico, se vogliamo) di lunghezza infinita: esso è in grado di memorizzare tutti i dati relativi ad ogni particolare elaborazione indipendentemente dalla loro quantità. Il nastro è sezionabile in celle (o locazioni di memoria): ciascuna di esse può contenere un simbolo o essere vuota (null). Il dispositivo di lettura e scrittura può essere assimilato ad una testina magnetica in grado di trasferire i simboli desiderati sul nastro stesso; nel contempo, occorre che esista la possibilità di deciderne la direzione di movimento mediante una unità di controllo. Quest'ultima inoltre contiene naturalmente il programma da eseguire.

Schema semplificato del funzionamento della "macchina di Turing"

In quest'ottica, la macchina risulta sostanzialmente "dedicata" ad ogni unica applicazione che si intende simulare: infatti essa non è dotata di un dispositivo di memoria di massa sul quale far risiedere o poter leggere il programma stesso.

La logica di controllo della macchina è composta da frasi o stringhe composte da cinque campi o istruzioni (dette "quintette"). L'esecuzione di ogni quintetta è vincolata sostanzialmente sia dal simbolo presente al momento nell'unità di lettura e scrittura che dallo stato della macchina. Lo stato della macchina è una condizione essenzialmente arbitraria. In linea di principio potremo definire uno stato arbitrario Si di avvio, nel quale la macchina inizia l'esecuzione della procedura di calcolo, fino a raggiungere la speciale condizione H (Halt) che corrisponde al termine dell'esecuzione. Tra questi due stati possono naturalmente esserci n stati differenti che riflettono appunto il risultato dell'elaborazione in corso e stabiliscono quale quintetta eseguire di conseguenza.

Ogni quintetta è composta dai seguenti cinque elementi:

   1. L'attuale stato della macchina

   2. Il simbolo contenuto nella cella correntemente in corso di lettura

   3. Il simbolo da scrivere nella medesima cella se non avviene alcuna modifica del dato

   4. Lo stato della macchina a seguito delle precedenti operazioni (2 e 3)

   5. La direzione di scorrimento del nastro (avanti o indietro).

Ad esempio, la quintetta (S1, 7, 9, S2, R) viene eseguita ogni qualvolta la macchina si trova nello stato S1 e la testina di lettura legge un 7. A quel punto, il 7 viene sostituito da un 9, la macchina viene posta nello stato S2 ed il nastro viene fatto scorrere di una posizione verso destra (R = right = destra).