La macchina di Turing è uno dei modelli fondamentali dell’informatica teorica. La sua importanza non deriva dalla somiglianza con un computer moderno, ma dal fatto che permette di descrivere con estrema precisione che cosa significhi eseguire un procedimento algoritmico. Una macchina di Turing non “comprende” ciò che sta facendo: applica semplicemente, passo dopo passo, un insieme finito di regole meccaniche.

Come ricorda anche la presentazione introduttiva pubblicata da HUMAI, il modello può essere immaginato come costituito da un nastro suddiviso in celle, una testina capace di leggere e scrivere un simbolo alla volta, un insieme finito di stati interni e un insieme di regole che stabiliscono il comportamento della macchina. Il calcolo nasce dall’interazione continua fra questi elementi.

1. Il funzionamento essenziale della macchina di Turing

Il nastro è formato da celle, ciascuna delle quali contiene un simbolo appartenente a un alfabeto finito. In una versione molto semplice possiamo immaginare un alfabeto formato da 0 e 1, eventualmente con un simbolo speciale che rappresenta una cella vuota. Il nastro costituisce la memoria esterna della macchina: può contenere l’input iniziale, dati intermedi prodotti durante il calcolo e, alla fine, l’output.

La testina osserva una sola cella alla volta. A ogni passo legge il simbolo contenuto nella cella corrente, può sostituirlo con un altro simbolo e si sposta normalmente di una posizione verso sinistra oppure verso destra.

La macchina possiede inoltre un insieme finito di stati interni, che indicheremo con \(Q\). Per esempio, una macchina con due stati può avere

Infine vi è la funzione di transizione, cioè l’insieme delle istruzioni che costituisce il vero e proprio programma della macchina. In una variante deterministica con alfabeto binario possiamo rappresentarla, in forma semplificata, come

La funzione prende come ingresso due informazioni: lo stato corrente e il simbolo letto. Restituisce tre indicazioni: quale simbolo scrivere, in quale direzione muovere la testina e quale sarà il nuovo stato. Per esempio,

significa: se la macchina si trova nello stato \(A\) e legge uno zero, allora scrive uno, si sposta verso destra e passa nello stato \(B\). L’evoluzione del calcolo è dunque determinata dalla coppia

La macchina continua ad applicare transizioni finché raggiunge una condizione di arresto, per esempio entrando nello stato speciale \(\mathrm{HALT}\). Non è però garantito che una macchina si arresti: alcune configurazioni di regole possono generare un’esecuzione infinita.

2. Perché gli stati permettono di discriminare le scelte

Il ruolo degli stati è particolarmente importante. Se il comportamento della macchina dipendesse soltanto dal simbolo letto, ogni volta che la testina incontrasse, per esempio, uno zero, la macchina sarebbe obbligata a compiere sempre la stessa operazione. Gli stati introducono invece un ulteriore elemento di discriminazione.

Possiamo infatti avere

In entrambi i casi la macchina sta leggendo lo stesso simbolo 0, ma può reagire in modo diverso perché nel primo caso si trova nello stato \(A\) e nel secondo nello stato \(B\). Lo stato rende quindi possibile contestualizzare il simbolo letto: la decisione non dipende semplicemente da “che cosa vedo”, ma anche da “in quale situazione interna mi trovo mentre lo vedo”.

In questo senso, aumentando il numero di stati aumenta il numero delle situazioni interne che la macchina può distinguere. Se \(Q=\{A,B,C\}\), la stessa lettura di uno zero può teoricamente produrre tre comportamenti differenti a seconda dello stato corrente.

3. Lo stato come forma di memoria

Dire che gli stati costituiscono una forma di memoria richiede una precisazione. Uno stato non è una “cella” in cui viene scritto un dato come avviene sul nastro. La memoria nasce piuttosto dal fatto che lo stato corrente può dipendere da ciò che è accaduto in precedenza e può, a sua volta, influenzare il comportamento futuro.

Supponiamo che lo stato \(A\) significhi intuitivamente “non ho ancora incontrato un 1” e che lo stato \(B\) significhi “ho già incontrato almeno un 1”. Se durante la lettura del nastro la macchina incontra per la prima volta un uno, una transizione può portarla da \(A\) a \(B\). Successivamente la testina potrebbe trovarsi molto lontana dalla cella in cui quell’uno era stato osservato, ma il fatto che la macchina sia ancora nello stato \(B\) conserva una traccia di quell’evento passato.

È dunque possibile formulare una definizione intuitiva molto generale:

Una memoria si ottiene quando lo stato presente di un sistema dipende da eventi precedenti e questa informazione persistente può modificare le decisioni successive.

Lo stato attuale può essere visto come una compressione del passato: non occorre conservare necessariamente l’intera storia dell’esecuzione; è sufficiente conservare la parte di informazione che sarà rilevante per le decisioni future.

Si deve però distinguere questa memoria interna finita dalla memoria fornita dal nastro. Gli stati appartengono a un insieme finito stabilito una volta per tutte nella definizione della macchina, mentre il nastro può fornire una quantità arbitrariamente grande di spazio di lavoro. Per questo si parla degli stati come di memoria finita di controllo, mentre il nastro svolge il ruolo della memoria esterna potenzialmente illimitata.

4. Numero di stati e complessità del comportamento

Quando si dice che una macchina di Turing ha \(n\) stati, si intende che il suo insieme di stati ordinari contiene \(n\) elementi. Lo stato di arresto viene normalmente trattato separatamente. Per una macchina binaria con \(n\) stati, la funzione di transizione deve specificare cosa accade per ogni coppia formata da uno stato e da uno dei due simboli leggibili. Le situazioni da specificare sono quindi

Per una macchina con due stati \(A\) e \(B\), per esempio, bisogna definire le quattro transizioni corrispondenti a

L’aumento del numero degli stati non aggiunge semplicemente qualche istruzione: aumenta il numero di configurazioni interne che la macchina può distinguere e quindi permette strategie di calcolo molto più articolate. È precisamente questo fatto che rende interessante la funzione Busy Beaver.

5. Il Busy Beaver

Il Busy Beaver considera tutte le macchine di Turing appartenenti a una determinata classe, per esempio macchine deterministiche binarie con esattamente \(n\) stati, avviate su un nastro inizialmente vuoto. Tra queste vengono considerate soltanto le macchine che prima o poi si arrestano.

Una delle versioni più comuni della funzione, che qui indichiamo con \(BB(n)\), assegna a ogni \(n\) il massimo numero di passi eseguito da una macchina a \(n\) stati che alla fine si arresta:

È importante precisare la convenzione, perché nella letteratura sul Busy Beaver si incontra anche una funzione, spesso indicata con \(\Sigma(n)\), che massimizza non il numero di passi ma il numero di simboli 1 lasciati sul nastro al momento dell’arresto.

Nella convenzione basata sul tempo di esecuzione, per le piccole macchine binarie si hanno:

6. Un esempio: il record a due stati

Consideriamo la macchina a due stati definita dalla seguente funzione di transizione:

In notazione funzionale:

Partendo da un nastro vuoto, questa macchina esegue sei transizioni prima di raggiungere \(\mathrm{HALT}\). Si può inoltre dimostrare, analizzando l’intero insieme delle macchine pertinenti, che nessuna macchina binaria a due stati che si arresta riesce a effettuare più di sei passi. Quindi

Nella variante che massimizza il numero di uno lasciati sul nastro si ottiene invece \(\Sigma(2)=4\).

7. Perché non basta simulare tutte le macchine?

A prima vista, il calcolo di \(BB(n)\) sembra poter essere risolto con una procedura brutale: enumerare tutte le macchine con \(n\) stati, farle partire, registrare il numero di passi di quelle che si fermano e scegliere il massimo.

Il problema si manifesta quando una macchina continua a funzionare senza arrestarsi. Dopo un milione, un miliardo o un numero astronomico di passi, non possiamo concludere semplicemente che non si fermerà: potrebbe arrestarsi al passo successivo o dopo un intervallo ancora più lungo.

Dunque, per sapere con certezza di avere trovato il Busy Beaver, non basta conoscere le macchine che si sono già fermate. Bisognerebbe anche stabilire, per tutte le altre candidate, quali continueranno per sempre. Qui entra in gioco il problema della fermata.

8. Il problema della fermata

Il problema della fermata chiede se esista un algoritmo universale capace di ricevere la descrizione di una macchina di Turing e del suo input e stabilire sempre, in un tempo finito, se quella macchina prima o poi si fermerà oppure continuerà indefinitamente.

Il risultato fondamentale di Turing è che un tale algoritmo universale non esiste. Il problema della fermata è indecidibile: non esiste una singola procedura algoritmica che risolva correttamente il problema per tutte le possibili macchine e per tutti i possibili input.

9. Busy Beaver e impossibilità di una soluzione universale

Il legame con il Busy Beaver è profondo. Supponiamo, per assurdo, di possedere un algoritmo universale capace di calcolare \(BB(n)\) per qualunque \(n\).

Prendiamo allora una macchina appartenente alla classe considerata, con \(n\) stati, e facciamola funzionare per al massimo

passi. Per definizione di \(BB(n)\), nessuna macchina a \(n\) stati che alla fine si arresta può superare \(BB(n)\) passi. Di conseguenza, se la macchina non si è ancora arrestata dopo quel limite, possiamo concludere che non si arresterà mai.

In altre parole, la conoscenza generale di \(BB(n)\) fornirebbe un limite massimo universale per il tempo di arresto delle macchine della classe considerata. Questo permetterebbe di distinguere algoritmicamente le macchine che si fermano da quelle che non si fermano e porterebbe quindi a una soluzione del problema della fermata per la codifica pertinente.

Ma una soluzione universale del problema della fermata è impossibile. Ne segue che non può esistere un algoritmo capace di calcolare \(BB(n)\) per ogni valore di \(n\).

Questo non significa che \(BB(n)\) sia indefinito. Per ogni \(n\), il valore esiste ed è un numero naturale ben determinato: le macchine a \(n\) stati sono in numero finito e, tra quelle che si arrestano, esiste quindi un massimo numero di passi. Ciò che manca è una procedura algoritmica universale capace di produrre questi valori per tutti gli \(n\).

10. Il significato concettuale del Busy Beaver

Il Busy Beaver rende particolarmente evidente la differenza fra ciò che è matematicamente ben definito e ciò che è algoritmicamente calcolabile. La domanda “qual è il massimo numero di passi eseguibile da una macchina a \(n\) stati che poi si ferma?” è perfettamente precisa. Eppure non esiste una procedura generale capace di fornire la risposta per ogni \(n\).

La funzione cresce inoltre più rapidamente di qualunque funzione totale calcolabile. Se una funzione calcolabile potesse fornire, per ogni \(n\), un limite superiore sufficientemente efficace ai tempi di arresto delle macchine a \(n\) stati, quel limite potrebbe essere sfruttato per affrontare il problema della fermata. Il comportamento estremo del Busy Beaver è quindi un riflesso numerico dell’indecidibilità.

Conclusione

La macchina di Turing nasce da elementi estremamente semplici: un nastro, una testina, un insieme finito di simboli, un insieme finito di stati e una funzione di transizione. Tuttavia proprio l’interazione fra questi elementi rende possibile una ricchezza di comportamento enorme.

Il concetto di stato è centrale. Lo stato consente di discriminare il comportamento della macchina a parità di simbolo letto e costituisce una forma di memoria perché conserva informazione sul passato capace di influenzare il futuro. Il nastro rappresenta invece la memoria esterna e potenzialmente illimitata. Il calcolo emerge dall’interazione fra memoria finita di controllo, memoria esterna e regole locali di transizione.

Il Busy Beaver porta questa struttura al limite: fissato un numero di stati, cerca la macchina che riesce a prolungare maggiormente il proprio calcolo pur dovendo, alla fine, arrestarsi. Per piccoli valori il record può essere stabilito mediante enumerazione, simulazione e dimostrazioni specifiche. Non esiste però una soluzione universale. Per stabilire sempre il record bisognerebbe infatti essere capaci di distinguere sistematicamente le macchine che prima o poi si fermeranno da quelle che continueranno per sempre. È esattamente la barriera posta dal problema della fermata.

Il Busy Beaver mostra così, in una forma particolarmente concreta, uno dei limiti fondamentali del calcolo: esistono numeri perfettamente definiti che nessun algoritmo universale può calcolare in tutti i casi.