La macchina di Turing è uno dei concetti più importanti dell’informatica teorica. Eppure assomiglia pochissimo a un computer moderno: niente schermo, processore o tastiera e, nella sua forma teorica, nessun limite reale alla memoria.
Ideata da Alan Turing nel 1936, risponde a una domanda molto più fondamentale: che cos’è un calcolo? Turing immagina una macchina volutamente minimale, capace di leggere e scrivere simboli su un nastro seguendo regole precise.
Nonostante l’estrema semplicità, il modello è abbastanza potente da rappresentare ogni calcolo eseguibile da un algoritmo secondo la concezione classica della calcolabilità. Permette quindi di capire che cosa sia un algoritmo, che cosa un computer possa teoricamente calcolare e perché alcuni problemi restino impossibili da risolvere automaticamente indipendentemente dalla potenza delle macchine future.
Perché era necessario definire il calcolo?
All’inizio del XX secolo i matematici cercavano di formalizzare i fondamenti della disciplina. L’Entscheidungsproblem di David Hilbert chiedeva, in forma semplificata, se potesse esistere una procedura meccanica capace di decidere per ogni proposizione di un sistema logico se fosse dimostrabile.
Ma che cosa significa esattamente «seguire una procedura meccanica»? Nel 1936 il computer elettronico programmabile non esiste ancora. Occorre quindi definire matematicamente una procedura di calcolo indipendentemente da una macchina reale. È proprio ciò che fa Turing. La biografia di Alan Turing ricostruisce il contesto più ampio del suo lavoro.
Una macchina volutamente molto semplice
Una macchina di Turing classica possiede pochi elementi:
un nastro diviso in celle;
un insieme limitato di simboli;
una testina di lettura-scrittura;
un insieme finito di stati;
una tabella di regole di transizione.
A ogni passo la macchina osserva il simbolo sotto la testina. In base a quel simbolo e allo stato corrente, una regola indica se scrivere un simbolo, spostarsi a sinistra o a destra, cambiare stato ed eventualmente fermarsi. Poi il processo ricomincia.
Una sequenza di operazioni elementari può così produrre calcoli complessi.
Il nastro: una memoria teoricamente illimitata
Il nastro è rappresentato come una successione di celle, ciascuna contenente un simbolo di un alfabeto definito. Nel modello teorico si assume che sia disponibile abbastanza nastro da non esaurire la memoria durante il calcolo considerato.
Non significa che un computer reale possa avere memoria infinita. L’ipotesi separa due domande: un problema è teoricamente calcolabile? E disponiamo delle risorse fisiche necessarie per eseguire davvero il calcolo? La macchina di Turing studia soprattutto la prima.
La testina e gli stati
La testina osserva una sola cella alla volta, ne legge il simbolo, può sostituirlo e poi spostarsi. La macchina possiede inoltre uno stato corrente, per esempio q0, q1 o q2.
Una regola può dire: se la macchina è in q0 e legge 1, scrive 0, si sposta a destra e passa a q1.
Il comportamento completo dipende quindi da stato corrente + simbolo letto + regola di transizione.
Un esempio semplice: aggiungere 1
Rappresentiamo il numero 4 in forma unaria con quattro simboli 1:
1111
Vogliamo aggiungere 1. Finché la testina legge 1, si sposta a destra; quando incontra una cella vuota, scrive 1 e si ferma.
11111
La macchina ha calcolato 4 + 1 = 5. Nessun computer moderno eseguirebbe così un’addizione: l’esempio serve a mostrare che un calcolo può essere scomposto in regole meccaniche perfettamente determinate.
È un vero computer?
Non nel senso comune. La macchina di Turing è prima di tutto un oggetto matematico. Turing non stava proponendo nel 1936 il progetto industriale di un computer, ma un modello preciso per ragionare sulle procedure calcolabili.
Nel XIX secolo Babbage ragiona da ingegnere: come costruire una macchina generale capace di eseguire calcoli diversi? Le schede perforate avrebbero rappresentato operazioni e dati.
Turing pone una domanda più astratta: che cosa può fare in linea di principio una macchina di calcolo? I due approcci sono diversi, ma contribuiscono alla progressiva separazione tra macchina fisica e istruzioni che ne determinano il comportamento.
La macchina universale
Una delle idee più potenti di Turing è la macchina universale. Una particolare macchina può ricevere sul proprio nastro la descrizione di un’altra macchina insieme ai dati su cui questa dovrebbe lavorare e quindi simularne il funzionamento.
Non occorre dunque costruire fisicamente una macchina diversa per ogni procedura.
Una macchina, molti programmi
Oggi l’idea sembra naturale: lo stesso computer può mostrare una pagina web, modificare una fotografia, eseguire un gioco, elaborare un CSV, compilare codice o riprodurre un video. Non ricostruiamo l’hardware per ogni compito: cambiamo il programma.
La macchina universale formalizza questa separazione fra dispositivo generale e descrizione del calcolo da eseguire.
Macchina universale e architettura di von Neumann non sono la stessa cosa
La macchina universale di Turing è un modello matematico che dimostra la possibilità di simulare altre macchine. L’architettura di von Neumann descrive invece un’organizzazione pratica dei computer elettronici in cui istruzioni e dati possono essere conservati in memoria.
Le idee sono imparentate, ma rispondono a obiettivi diversi: Turing studia la calcolabilità; i progettisti dei primi computer elettronici affrontano anche architettura e realizzazione pratica.
Che cos’è un problema calcolabile?
In forma semplificata, un problema è calcolabile se esiste una macchina di Turing capace di produrre il risultato atteso in un numero finito di passi per gli input considerati.
L’intuizione «deve esistere un metodo» diventa così una domanda matematica: possiamo descrivere una procedura precisa? Può essere espressa con regole meccaniche? Terminerà producendo una risposta? Queste domande sono al centro della teoria della calcolabilità.
Non tutti i problemi sono calcolabili
Una delle conclusioni più importanti di Turing è controintuitiva: esistono problemi che nessun algoritmo può risolvere in tutti i casi. Non è un limite temporaneo dei computer degli anni Trenta e non scompare con processori più veloci o più memoria.
L’esempio più noto è il problema dell’arresto.
Il problema dell’arresto
Immaginiamo un programma HALT che riceva un programma qualsiasi e i suoi dati e debba rispondere: questo programma finirà per fermarsi o continuerà per sempre?
Per alcuni programmi la risposta è ovvia. Ma HALT dovrebbe funzionare per tutti i programmi possibili e tutti gli input. Turing dimostra che un algoritmo universale di questo tipo non può esistere.
Perché è così importante?
Il risultato rivela un limite fondamentale dell’automazione. Gli strumenti di analisi del codice possono trovare moltissimi problemi, riconoscere alcuni cicli o dimostrare proprietà per determinate categorie di programmi. Nessuno strumento può però risolvere perfettamente il problema dell’arresto per ogni programma possibile.
La differenza tra «molto difficile» e «impossibile in generale» è fondamentale.
Un limite indipendente dall’hardware
Anche computer un miliardo di volte più veloci, memoria gigantesca o una macchina ideale non renderebbero decidibile il problema dell’arresto.
Possiamo quindi distinguere almeno tre tipi di limiti: tempo, memoria e calcolabilità. I primi due riguardano le risorse necessarie; il terzo l’esistenza stessa di un algoritmo generale.
Calcolabilità e complessità
La calcolabilità chiede: esiste un algoritmo che risolve il problema? La complessità algoritmica chiede: se esiste, quanto tempo o memoria richiede?
Un problema può essere calcolabile ma estremamente costoso. Un problema indecidibile, invece, non possiede un algoritmo generale che dia sempre la risposta corretta.
Alonzo Church e il lambda calcolo
Alonzo Church sviluppò indipendentemente il lambda calcolo, un altro formalismo per rappresentare i calcoli. Pur apparendo molto diversi, il lambda calcolo e le macchine di Turing caratterizzano la stessa classe di funzioni calcolabili.
La convergenza di modelli indipendenti è uno degli elementi che rendono questa nozione così solida.
La tesi di Church-Turing
In forma semplificata: ogni calcolo realizzabile mediante una procedura effettiva può essere eseguito da una macchina di Turing.
È una tesi, non un normale teorema matematico, perché «procedura effettiva» nasce come nozione intuitiva. Molti modelli di calcolo sviluppati successivamente si sono comunque rivelati equivalenti per potenza di calcolo.
Un computer moderno è una macchina di Turing?
Non letteralmente. Ha memoria finita, architetture complesse, processori, cache, periferiche e spesso più core. Ma per studiare ciò che è calcolabile in linea di principio, i computer generalisti classici sono considerati equivalenti al modello di Turing sotto le consuete ipotesi sulle risorse.
Cambiare processore o linguaggio può rendere un calcolo più veloce, non spostare improvvisamente il confine fondamentale della calcolabilità.
Il linguaggio cambia ciò che è calcolabile?
Python, Java, C, JavaScript e C++ differiscono enormemente per sintassi, astrazioni, prestazioni e librerie. Un linguaggio generalista Turing-completo, tuttavia, può teoricamente esprimere ogni calcolo eseguibile da una macchina di Turing, disponendo di risorse sufficienti.
La potenza teorica è soltanto una delle molte dimensioni di un linguaggio.
Che cos’è la Turing-completezza?
Un sistema è generalmente detto Turing-completo quando possiede capacità sufficienti a simulare una macchina di Turing universale nelle consuete ipotesi teoriche di memoria. L’espressione si usa per linguaggi, macchine virtuali, sistemi di riscrittura e perfino alcuni giochi o software.
Essere Turing-completo non significa essere veloce, pratico o pensato per programmare: indica una potenza espressiva sufficiente per il calcolo generale.
Una macchina estremamente semplice può essere universale
Non servono centinaia di istruzioni diverse. Varianti molto semplici delle macchine di Turing possono essere universali. Comportamenti sofisticati possono emergere dalla ripetizione e combinazione di poche operazioni elementari.
Dati e istruzioni diventano informazione
Nella macchina universale, la descrizione della macchina simulata è rappresentata essa stessa come simboli: le istruzioni diventano dati che la macchina può leggere.
Testi, numeri, immagini, programmi e istruzioni possono essere rappresentati in forma manipolabile. L’articolo sulla teoria dell’informazione esplora un’altra faccia di questa astrazione, cioè come l’informazione possa essere misurata e codificata.
La macchina di Turing non misura le prestazioni
Il suo ruolo principale non è confrontare la velocità dei computer. Una macchina di Turing può svolgere un calcolo in modo incredibilmente lento rispetto a un computer reale. La domanda è: questo calcolo può essere eseguito da una procedura algoritmica?
Per valutarne l’utilità pratica bisogna poi studiare complessità, algoritmi e architettura reale.
E i computer quantistici?
I computer quantistici possono offrire vantaggi notevoli per alcune categorie di problemi e sfruttano principi fisici diversi. Nel quadro teorico abituale, però, non rendono calcolabili i problemi fondamentalmente non calcolabili nel senso di Turing.
Possono modificare l’efficienza di alcuni calcoli, non necessariamente il confine fondamentale fra calcolabile e non calcolabile.
Perché si insegna ancora la macchina di Turing?
Un nastro astratto può sembrare lontano dallo sviluppo software del 2026, ma rende comprensibili idee essenziali:
che cos’è un algoritmo;
la differenza tra programma e macchina;
il calcolo universale;
l’esistenza di problemi indecidibili;
la differenza tra calcolabilità e complessità;
i fondamenti teorici dei linguaggi di programmazione.
Come alcuni modelli idealizzati della fisica, semplifica la realtà per mettere in evidenza i principi fondamentali.
Dalla macchina di Turing ai computer moderni
La macchina di Turing del 1936 non è l’architettura dei nostri computer. Babbage immagina una macchina meccanica programmabile; le schede perforate mostrano che istruzioni e dati possono essere rappresentati su un supporto esterno; Turing formalizza una macchina universale; negli anni Quaranta i computer elettronici a programma memorizzato trasformano progressivamente queste idee in sistemi fisici.
L’architettura di von Neumann diventa poi uno dei modelli più influenti per organizzare concretamente processore, memoria, dati e istruzioni. Non si tratta di una linea storica semplice e molti ricercatori contribuirono a questi sviluppi.
Un’eredità ancora presente
Quasi novant’anni dopo l’articolo di Turing, il modello resta centrale nell’informatica teorica. Ogni volta che ci chiediamo se un problema possa essere automatizzato, se un programma possa analizzare perfettamente tutti gli altri programmi, se un linguaggio possa esprimere calcoli generali o quali siano i limiti intrinseci degli algoritmi, torniamo direttamente o indirettamente alla teoria della calcolabilità.
I computer sono cambiati radicalmente, ma una maggiore potenza non elimina i limiti matematici del calcolo.
Da ricordare
La macchina di Turing è un modello matematico del calcolo proposto da Alan Turing nel 1936. Usa un nastro, una testina di lettura-scrittura, simboli, stati e regole di transizione.
La macchina universale dimostra che una sola macchina può simularne molte altre quando riceve la loro descrizione come dato. Il problema dell’arresto dimostra invece che non esiste un algoritmo universale capace di decidere per tutti i programmi se termineranno.
Il modello insegna quindi due cose apparentemente opposte: una macchina molto semplice può eseguire un’enorme varietà di calcoli, ma nessuna macchina algoritmica può calcolare tutto.
Domande frequenti
Chi ha inventato la macchina di Turing?
Il matematico britannico Alan Turing propose il modello nell’articolo del 1936 On Computable Numbers, with an Application to the Entscheidungsproblem.
È mai stata costruita una macchina di Turing?
Il concetto originale è un modello matematico, non il progetto di un computer. In seguito sono stati costruiti modelli fisici a scopo didattico.
Che cos’è il nastro?
È la memoria teorica del modello: una successione di celle contenenti simboli che la testina può leggere e modificare.
Che cos’è una macchina universale di Turing?
È una macchina capace di leggere la descrizione di un’altra macchina e il suo input e di simularne il comportamento.
Che cos’è il problema dell’arresto?
Chiede se un algoritmo generale possa decidere per qualsiasi programma e input se il programma finirà. Turing dimostrò che un algoritmo del genere non può esistere.
I computer moderni sono Turing-completi?
I computer generalisti e la maggior parte dei linguaggi generalisti sono considerati Turing-completi in senso teorico, con le consuete ipotesi sulla memoria disponibile.
I computer quantistici superano i limiti della macchina di Turing?
Possono risolvere alcuni problemi calcolabili in modo molto più efficiente, ma nel quadro teorico abituale non rendono calcolabili problemi fondamentalmente non calcolabili.
