Macchina di Turing: cos'è e come funziona

La macchina di Turing non è un oggetto che si possa toccare. È un modello immaginato su carta per rispondere a una domanda precisa: che cosa significa, esattamente, calcolare? Alan Turing rispose nel 1936 descrivendo una macchina minima, fatta di nastro, testina e stati, e mostrando che con questi pochi ingredienti si può riprodurre qualunque procedimento che una persona chiamerebbe un calcolo (pochi anni dopo, lo stesso Turing avrebbe messo queste idee al servizio della decifrazione del codice nazista Enigma: il Recap su Alan Turing e la macchina Enigma ne racconta la vicenda).

Gli elementi del modello

Il nastro è diviso in caselle, ognuna capace di contenere un simbolo. È infinito in una direzione, così la macchina trova sempre una casella libera quando avanza. Una testina si posiziona su una casella alla volta, legge il simbolo che vi trova e, se serve, lo sostituisce con un altro.

La macchina si trova sempre in uno fra un numero finito di stati (Turing li chiamava “m-configurazioni”). Bastano pochi stati, combinati con le regole giuste, per rappresentare procedimenti complicati.

A collegare stati e simboli c’è la funzione di transizione: dato lo stato attuale e il simbolo letto, stabilisce tre cose, quale simbolo scrivere, in che direzione muovere la testina, e in quale nuovo stato passare. Per l’architettura di von Neumann, che descrive come sono organizzati i computer reali, la macchina di Turing è l’antenato teorico: un modello pensato prima che esistesse un solo microprocessore, e usato ancora oggi per capire i limiti di quelli che verranno.

Come funziona un passo

Ogni passo della macchina è fatto di tre azioni elementari: scrivere un simbolo, spostare la testina di una casella, cambiare stato. L’ordine conta, ma la logica resta sempre la stessa: l’azione dipende soltanto dallo stato e dal simbolo del momento presente.

Esempio pratico: per rappresentare il numero 3, una macchina di Turing in notazione unaria scrive sul nastro un blocco di quattro simboli “1” consecutivi (il numero n si scrive con n+1 simboli). Basta un solo simbolo ripetuto, con le regole giuste per contarlo, per fare già aritmetica.

Lo stesso principio, regole minime applicate passo dopo passo, si ritrova in un esempio diverso: una macchina che incrementa un numero scritto in codice binario scorre le cifre da destra a sinistra, cambia gli “1” in “0” finché non trova uno “0”, e lo trasforma in “1”. È lo stesso riporto che si fa a mano sommando in colonna, tradotto in un linguaggio di sole due cifre.

Chi cerca una definizione più generale di che cos’è una sequenza di regole come questa può leggere il Recap su l’algoritmo: la macchina di Turing ne è una delle formalizzazioni più rigorose, scritta fin nei minimi dettagli.

Il problema della fermata

Un procedimento di questo tipo può bloccarsi, oppure proseguire all’infinito senza mai fermarsi. Il problema della fermata chiede se esiste un metodo generale, una macchina che funzioni per qualunque altra macchina e qualunque input, capace di dire in anticipo quale dei due casi si verificherà.

La risposta è no. La dimostrazione procede per assurdo: si ipotizza che esista una macchina capace di decidere la fermata di ogni altra macchina, e si costruisce un caso particolare che usa quella stessa macchina contro sé stessa, arrivando a una contraddizione logica. La tecnica si chiama costruzione diagonale, ed è dovuta a Turing.

È un’impossibilità dimostrata, valida per qualunque macchina, lenta o velocissima: più tempo o più potenza di calcolo non cambiano il risultato.

La tesi di Church-Turing

A metà degli anni Trenta del Novecento, Alonzo Church e Alan Turing arrivarono, in modo indipendente, alla stessa idea: tutto ciò che si può calcolare con un metodo effettivo, un algoritmo nel senso intuitivo del termine, lo si può calcolare con una macchina di Turing.

È una tesi: nessuna dimostrazione matematica formale esiste, ma la convergenza di modelli di calcolo nati in modo indipendente negli stessi anni, le macchine di Turing, le funzioni ricorsive di Church, altri formalismi, verso un’unica classe di funzioni calcolabili ha reso la tesi più credibile nel tempo. Il logico Kurt Gödel riconobbe nella macchina di Turing una definizione precisa, e a suo parere corretta, della nozione intuitiva di procedimento meccanico: un giudizio autorevole, non un teorema dimostrato.

La conseguenza pratica riguarda ogni computer che esista o che potrà mai esistere: i limiti del modello teorico valgono anche per le macchine reali, qualunque sia la tecnologia con cui sono costruite. Il problema della fermata non è un difetto di questo o quel linguaggio di programmazione: è un confine che la tesi di Church-Turing porta dentro ogni macchina reale, come racconta anche il Recap sulla storia del computer. C’è anche una conseguenza legata ai numeri anziché ai programmi: i numeri reali sono un’infinità più grande dei possibili programmi per macchina di Turing, che invece si possono contare uno a uno, elencandoli in un lungo catalogo immaginario. Da questo segue che esistono necessariamente numeri reali che nessuna macchina di Turing riuscirà mai a calcolare: sono semplicemente più numerosi dei programmi disponibili per calcolarli, qualunque sia il tempo che si lascia alla macchina per lavorare.

Una macchina che simula le altre

Il nome “macchina di Turing universale” indica l’idea di una singola macchina capace di simulare qualunque altra macchina di Turing. È un’estensione diretta del modello descritto fin qui, ma il meccanismo preciso resta fuori dall’ambito trattato qui: lo citiamo solo per nome, perché compare spesso insieme al resto della teoria della computabilità.