Nel 1935-6 il matematico inglese Alan Turing, nel tentativo, fruttuoso, di dimostrare che questo programma non era realizzabile, produsse la prima descrizione rigorosa di quello che si deve intendere per esecuzione meccanica, attraverso quello che fu denominato "automa", o macchina, di Turing.

     Pur essendo possibile costruire una macchina reale di Turing, l'idea è servita in realtà solo come modello, quello del più semplice tipo di computer realizzabile. Nonostante la sua semplicità però, la capacità di calcolo della macchina non è inferiore in nulla a quella del più sofisticato calcolatore odierno e futuro. In realtà la macchina è la rappresentazione fedele di cosa sia un algoritmo, e quello che i calcolatori possono fare è solo eseguire algoritmi. L'unica rilevante differenza è la velocità di esecuzione, che nel caso della macchina di Turing è la peggiore concepibile!

     Anzi, se si accetta la visione riduzionista della cosiddetta "Intelligenza Artificiale", secondo la quale il cervello umano non fa nulla più che seguire meccanicamente degli schemi di pensiero, bisogna concludere che il semplice automa inventato dal matematico inglese è ben più "intelligente" di quanto sembri dopo averne vista la descrizione. Oppure che gli umani farebbero bene a non sovrastimare le proprie capacità intellettuali!

     Come si vedrà parlando della macchina di Von Neumann, che è il primo modello di computer realmente a questi somigliante, un calcolatore è fatto essenzialmente dei seguenti elementi:

- dati iniziali da trasformare in finali (input e output);

- un programma da seguire per effettuare la trasformazione;

- una memoria in cui depositare i dati intermedi dei calcoli;

- un "agente", cioè qualcosa che esegua le azioni programmate.

     Non ha alcuna importanza chi e come esegua le azioni, se sia la CPU di un computer che modifica le celle di una RAM, o se invece sia una persona che esegue l'algoritmo usando della carta per dati iniziali, finali e intermedi. Quello che importa è che le azioni previste siano eseguite "ineluttabilmente".

     Una descrizione matematica però non può accontentarsi se non di precisare esattamente cosa siano dati, memoria ed azioni possibili.

     L'informazione nei computer è immagazzinata e trattata in una rappresentazione "digitale", utilizzando due stati contrapposti, detti 1 e 0, che fisicamente indicano la presenza di una tensione alta o bassa in un punto dei circuiti elettrici che costituiscono il calcolatore. Dal punto di vista logico i due stati rappresentano una scelta tra due possibilità contrapposte, tipicamente vero/falso, pieno/vuoto, sì/no. Questo permette di descrivere grandezze "discrete" come i numeri interi, che variano per salti, senza continuità, oltre a tutte quelle cose che si possono costruire con un alfabeto di un numero finito di lettere, come quelli delle lingue naturali.

     Nella visione originale la macchina era appunto una manipolatrice di parole, mentre quella che proporremo, del tutto equivalente, tratta i più semplici bit 0 e 1, che possono comunque rappresentare tutti i numeri e le parole. Questa versione della macchina è di solito usata perché più somigliante ai computer dell'originale veri.

     Le parti costituenti la macchina sono essenzialmente due, il nastro e la tabella. La tabella, che potremmo dire essere la parte interna della macchina, è come il costruttore l'ha fatta, immutabile, e contiene il programma da eseguire. Il nastro invece è il supporto per i dati iniziali, finali ed intermedi, cioè input, output e memoria. Il nastro è la parte su cui la macchina agisce.

     Il nastro è di lunghezza infinita e, in posizioni equidistanti lungo di esso, posizioni che possono essere individuate da numeri interi: ... , -3, -2, -1, 0, 1, 2, ... ci sono quelle che che chiameremo celle in quanto sono esattamente corrispondenti alle celle di una memoria. Queste celle che possono essere vuote o riportare un segno: per fissare le idee si può pensare rispettivamente a 0 per la cella vuota ed 1 per quella segnata. Importante è il fatto che solo un numero finito di celle riporta un segno e quindi, in questo caso ,ci sono un numero finito di 1, tutti gli altri sono 0.

     La macchina si muove sul nastro, legge il segno che trova nella data posizione e, a seconda dei casi, ci scrive 0 o 1, per poi spostarsi alla posizione precedente o seguente. Dato che input, output e memoria sono tutti sullo stesso nastro, ci vuole un modo per poterli distinguere. Come memoria si intende uno spazio inizialmente vuoto, cioè con soli zeri, che possa ospitare i dati intermedi senza sovrascrivere alcun dato iniziale, e si decide, arbitrariamente, che debba stare sulla sinistra della posizione iniziale della macchina. Se decidiamo che questa stia sulla cella 0, le posizioni negative conterranno tutte 0 e costituiranno la memoria iniziale.

   Sulla destra invece, cioè nelle celle indicate da 0 o da numeri positivi, ci sarà l'input, nel quale solo un numero finito di celle riporterà il segno 1. Se e quando la macchina terminerà la sua elaborazione, l'output, cioè il risultato finale, si troverà a sinistra della posizione finale della macchina. In rosso sono indicate le posizioni iniziale e finale della testina di lettura/scrittura della macchina.

     L'estrema semplificazione dei dati possibili, 0 o 1, e delle capacità di selezionare la parte di input/output successiva, spostandosi a destra o sinistra di una sola posizione, permette di descrivere il programma nel modo più scheletrico immaginabile.

     Si è detto sopra che la macchina "legge la cella su cui si trova e, a seconda del caso, ci scrive 0 o 1 e si sposta a destra o sinistra". Cosa si intende con "a seconda del caso" ? Con "caso" si intende uno degli "stati interni" (in numero finito) della macchina. Uno stato interno della macchina è uno dei punti del programma che la macchina deve eseguire, ed poiché il programma è fisicamente costituito da una "tabella", è una delle righe della tabella. Normalmente i programmi sono strutturati sequenzialmente, cioè "esegui questo, poi quest'altro, ... " e solo occasionalmente ci sono i cosiddetti salti condizionali, "se ... vai al punto xyz", con la nota e problematica istruzione goto. Nella macchina di Turing non esiste una sequenza predeterminata, per cui il passaggio da un punto all'altro del programma avviene sempre con salti condizionali, e quindi ciascuno dei punti del programma ha bisogno di essere nominato o, come si usa dire, etichettato. Lo stato interno è quindi semplicemente un nome (etichetta) del punto di programma in esecuzione.

     Per fissare le idee si può nominare questi stati S0, S1, ..., SN, ma si deve capire che non sono in sequenza. Quello che serve è solo l'indicazione dello stato iniziale, cioè del punto da cui si inizia l'elaborazione, che si può utilmente indicare con S0, e dello stato finale, che potremo indicare con S-1, usando come spesso si fa un numero negativo per un caso speciale.

Quindi un esempio di un punto di programma può essere:

stato 27: leggi la cella; se è scritto 0, scrivici 1, vai a destra e passa allo stato 15; se è scritto 1, lasciaci 1, vai a sinistra e passa allo stato 33.

Che può essere scritto in forma simbolica, tabellare appunto:

in cui R sta per Right , destra, ed L per Left, sinistra. In sostanza quindi il programma della macchina di Turing è una tabella che a ciascuna coppia (stato, lettura-cella) si fa corrispondere la tripletta (scrittura-cella, spostamento, nuovo-stato).

     Lo stato finale non è come gli altri, perché è semplicemente lo stato in cui l'elaborazione della macchina termina, per cui non compare nella tabella, non avendo alcuna elaborazione corrispondente.

     Qui è utile fermarsi per dare una definizione di algoritmo meno precisa ma più suggestiva. Sono necessari:

- uno "spazio dati", cioè qualcosa come il nastro della macchina, contenente un numero finito di tipi di segni, spazio replicato tre volte (per input, output e memoria, che nella macchina di Turing sono fusi assieme);

- delle "testine di lettura/scrittura" in ognuno dei tre spazi;

- delle "azioni elementari" di due tipi, una per definire come si spostano le testine all'interno dei loro spazi dati, un'altra per definire le funzioni elementari, cioè le trasformazioni dei dati da letti a scritti;

- il programma, che in funzione di: 1) stato interno, 2) lettura attuale, decida: 1) scrittura, 2) spostamento testine, 3) nuovo stato.

Il punto importante è questo: i segni sono di un numero finito di tipi, ci si possono applicare un numero finito di trasformazioni, seguendo un numero finito di passi di programma, ma la computazione segue, a causa delle istruzioni condizionali "se .. vai a ..", una via che dipende dai "luoghi dove passa", e quindi può essere anche arbitrariamente lunga ,oltre ad usare una quantità arbitrariamente grande di memoria. Si può dire in breve che gli algoritmi sono un tentativo di lavorare con l'arbitrariamente grande con strumenti del tutto finiti e limitati.

     E' interessante vedere quali sono i termini di un linguaggio di programmazione più evoluto, cioè di un tipico linguaggio imperativo, necessari per descrivere la struttura e il programma di una macchina di Turing.

     Questo permette di distinguere quello che in questi linguaggi è necessario da quello che è invece solo utile per aumentarne l'espressività.

     Prenderemo ad esempio un simil-C, notando che con altri linguaggi i termini sono gli stessi. Servono due variabili intere, una per rappresentare lo stato, e la chiamiamo s, e l'altra, nominata m, per indicare la posizione di memoria, o cella. Ad s diamo i valori 0, 1, ... N, per indicare gli stati normali ed il valore speciale -1 per indicare lo stato finale. La variabile m deve essere una cosiddetta variabile puntatore, disponibile in C ma, per esempio, non in Basic, una variabile cioè il cui valore è l'indirizzo di una cella di memoria che riporta il contenuto a cui siamo interessati. In C per indicare la cella referenziata da m si usa la scrittura *m.

Un blocco di istruzioni come visto sopra sarà scritto:

if (*m = 0) {*m = 1; m = m + 1; goto 15}

if (*m = 1) {*m = 1; m = m  - 1; goto 33}

in cui la seconda clausola condizionale non è stata scritta con un semplice "else" per mantenere l'apparenza simmetrica tra le due.

Si vede quindi che quello che è strettamente necessario è:

- un modo "illimitato" di indirizzare la memoria, che consenta cioè di avere a disposizione una quantità sufficiente di variabili (per questo si può usare un puntatore, non di tipo astratto come quelli forniti dal Pascal, ma che, come quelli del C, permettano un'aritmetica, seppur limitata a sommare o sottrarre 1);

- l'assegnamento di valore alle variabili;

- l'esecuzione condizionata da un test, cioè la if (...) { ... };

- l'istruzione di salto incondizionato, cioè la goto.

     La prima richiesta sembra lasciar fuori molti linguaggi, però in realtà la condizione di memoria illimitata non è soddisfatta da alcun computer e linguaggio reale, per cui il puntatore "illimitato" può essere sostituito in tutti i casi da un array sufficientemente grande. Si rischierà così di uscire dai limiti dell'array, ma questa è la tipica situazione di "running out of memory" cui possono incorrere tutti i calcolatori reali. I computer reali possono ritenersi equivalenti ad una macchina di Turing solo fino a quando non esauriscono la memoria, ma questo non è un problema perché finché non capita, l'esecuzione è la stessa, quando accade basta solo rifare tutto usando una memoria più grande.

     Come si vede, restano fuori tutte le caratteristiche evolute dei linguaggi, come il concetto di variabile di un dato tipo, la strutturazione dei dati, le procedure e le funzioni, e le strutture di controllo più sofisticate, alternative semplici e a più casi, cicli ecc. . Inoltre, anche se utilizzato a basso livello, non vi rientra neanche l’idea astratta di puntatore, o riferimento. Questo significa che tutti questi concetti sono imitabili con i pochi termini visti, non certo che la loro espressività sia sostituibile, perché se così fosse non avrebbe senso parlare di evoluzioni dei linguaggi.

     Infine, una notazione sulla struttura generale della macchina di Turing, e cioè la divisione programma/dati. Il programma della macchina è la tabella degli stati interni, per cui si può senz’altro dire che in questo caso è un programma fisso ed immutabile o, come si usa dire, statico. Come si vedrà nel caso della macchina di Von Neumann, nei calcolatori reali spesso i programmi che vengono eseguiti sono nella stessa memoria dei dati e quindi in teoria un programma può modificare la sua stessa struttura, essere cioè dinamico. Il fatto che il programma della macchina di Turing sia statico dimostra quindi che non c’è necessità di programmi che si automodificano, nel senso che non producono algoritmi più potenti dei programmi statici.

     In realtà l’unico vero caso di automodifica utilizzato è il seguente: agire sull’indirizzo di chiamata di un’istruzione, in modo che questa sia un salto ad un punto non fisso ma variabile. Questa situazione capita in due casi importanti, il ritorno da procedura, nel quale l’indirizzo di ritorno non è fissato nella procedura stessa, e le variabili di tipo procedura (in C puntatori a funzione), quelle che permettono di implementare il "legame dinamico delle procedure" nei linguaggi ad oggetti. Questi due casi sono fondamentali per l’espressività ed astrattezza di un linguaggio, ma non sono strettamente necessari per l’esecuzione di algoritmi.

     C’è inoltre da dire che la divisione rigida programma/dati è illusoria. Infatti una macchina di Turing esegue un solo speciale algoritmo, non come un computer che li esegue tutti trovando in memoria le istruzioni oltre ai dati. Si può però facilmente accordarsi su un modo di esprimere le istruzioni della macchina con dei semplici bit e inventare una macchina speciale, detta macchina universale di Turing, che li esegua, imitando il comportamento di una qualsiasi altra macchina data.

     La macchina universale è quindi una rappresentazione più vicina ai computer veri. E’ da notare la corrispondenza di concetti: il nastro è la RAM che contiene dati e codice dei programmi, la tabella interna è il microcodice cablato all’interno della CPU e della ROM.