Alan Mathison Turing (1912–1954) è considerato uno dei padri fondatori dell’informatica teorica. I suoi lavori tra il 1936 e il 1952 hanno definito, con una chiarezza senza precedenti, che cosa significhi “calcolare”, quali problemi siano risolvibili da una procedura meccanica e dove risiedano i limiti intrinseci del calcolo. Il cuore del suo lascito comprende le macchine di Turing, l’idea di macchina universale, la dimostrazione dell’indecidibilità di problemi fondamentali, le macchine con oracolo e il concetto di intelligenza artificiale misurata operativamente tramite il cosiddetto Turing Test.
1936: “On Computable Numbers” e la definizione formale di algoritmo
Nel saggio del 1936 On Computable Numbers, with an Application to the Entscheidungsproblem, Turing introduce un modello astratto di calcolatore, oggi noto come macchina di Turing, capace di rappresentare qualsiasi procedura algoritmica intuitivamente eseguibile. Il modello è volutamente minimale: un nastro infinito suddiviso in celle, una testina di lettura/scrittura, un insieme finito di stati e una funzione di transizione. Da questa semplicità discendono tre risultati cardine:
- Formalizzazione dell’effettiva calcolabilità: una funzione è calcolabile se esiste una macchina di Turing che la calcola. Questa formalizzazione rende matematicamente trattabili concetti come “procedura meccanica” o “algoritmo”.
- Macchina di Turing universale: Turing dimostra l’esistenza di una macchina capace di leggere la descrizione (codificata) di qualsiasi altra macchina e simularne il comportamento. L’idea di universalità è il fondamento concettuale del software: un’unica macchina fisica può realizzare infiniti programmi.
- Indecidibilità dell’Entscheidungsproblem: rispondendo a Hilbert, Turing mostra che non esiste un metodo generale per decidere la verità di tutte le formule della logica del primo ordine. La prova passa per la non computabilità del problema dell’arresto.
Il problema dell’arresto: il primo limite strutturale
Il problema dell’arresto chiede se esista una procedura che, data la descrizione di un programma e del suo input, stabilisca sempre se quel programma terminerà. Turing dimostra che nessuna macchina di Turing può risolvere correttamente e in tutti i casi questo problema. La dimostrazione usa una costruzione di diagonalizzazione e auto-riferimento: se esistesse un decidente universale dell’arresto, lo si potrebbe usare per costruire una macchina che si comporta in modo contraddittorio rispetto alla sua stessa previsione. Questo risultato inaugura la teoria dell’indecidibilità e, più in generale, la distinzione tra problemi decidibili e indecidibili.
La Tesi di Church–Turing
In parallelo allo λ-calcolo di Alonzo Church e ad altre formalizzazioni (p.es. sistemi di Post, funzioni ricorsive di Kleene), Turing sostiene la tesi secondo cui ogni processo di calcolo “effettivamente eseguibile” è computabile da una macchina di Turing. La Tesi di Church–Turing non è un teorema, bensì un principio metodologico che unifica modelli diversi e giustifica l’uso della macchina di Turing come standard di computabilità.
Oltre il calcolabile: oracoli e gradi di Turing
Nel 1939, in Systems of Logic Based on Ordinals, Turing introduce le macchine con oracolo (o oracle Turing machines): macchine di Turing arricchite da una “scatola nera” in grado di rispondere istantaneamente a una certa classe di domande. Con questo strumento definisce la riducibilità di Turing e avvia lo studio gerarchico dell’incomputabile attraverso i gradi di Turing. L’idea è duplice: alcuni problemi indecidibili sono “più difficili” di altri; e la potenza computazionale dipende dalle risposte accessorie fornite dall’oracolo. Questa linea di ricerca ha plasmato la teoria della calcolabilità posteriore (Post, Kleene, Friedberg, Sacks, Shoenfield, ecc.).
Impatto su complessità e linguaggi
Sebbene Turing non formalizzi le classi di complessità moderne, la sua nozione di computazione come sequenza di passi elementari su un nastro fornisce la metrica naturale per misurare tempo e spazio di calcolo. La possibilità di codificare programmi e dati sullo stesso nastro (universalità) permette argomenti di simulazione e diagonalizzazione temporale alla base di risultati successivi (p.es. gerarchie di tempo e spazio). Inoltre, la sua idea di descrivere programmi come dati prefigura i concetti di linguaggio di programmazione e interprete/compilatore, oltre a rendere chiaro cosa significhi che un linguaggio sia Turing-completo.
Intelligenza artificiale: criterio operativo (1950)
Nel 1950, con Computing Machinery and Intelligence, Turing sposta l’attenzione dalla definizione metafisica di “intelligenza” a una prova empirica: se una macchina può sostenere un’interazione linguistica in cui un interlocutore umano non distingue affidabilmente se stia parlando con un umano o con una macchina, allora ha mostrato un comportamento intelligente. Il Turing Test non è una definizione unica dell’intelligenza, ma un criterio operativo che ha influenzato sia la filosofia della mente sia l’IA pratica, incentivando lo studio di rappresentazione della conoscenza, ragionamento e linguaggio naturale.
Dalla teoria alla macchina: ACE e calcolo moderno
Dopo la guerra, Turing progetta l’Automatic Computing Engine (ACE) al National Physical Laboratory (UK). Il suo rapporto del 1945 e i lavori correlati illustrano un’architettura a programma memorizzato, sfruttando in modo esplicito il principio di universalità. Anche se altre linee progettuali diventeranno più influenti industrialmente, il contributo di Turing collega la teoria del 1936 con le prime macchine elettroniche generali, dimostrando la fecondità del modello astratto nella pratica.
Modelli computazionali e metodi: perché proprio la macchina di Turing?
- Minimalità espressiva: un dispositivo estremamente semplice cattura l’intera nozione di algoritmo; ciò rende possibili prove di impossibilità pulite.
- Codificabilità: dati e programmi codificabili sullo stesso supporto consentono l’auto-riferimento controllato e le tecniche di simulazione.
- Robustezza: modelli alternativi (λ-calcolo, funzioni ricorsive, macchine di Post) risultano equivalenti in potere espressivo, rafforzando la tesi che non sia il “mezzo” a definire l’algoritmo, ma la trasformazione effettiva dei simboli.
Limiti, implicazioni e eredità
I risultati di Turing non sono semplici curiosità negative: tracciano le frontiere del calcolo, guidano la progettazione di linguaggi, compilatori e sistemi, e fondano intere aree—dalla verifica formale (che deve convivere con l’indecidibilità generale) alla teoria dell’estrazione di programmi, fino alla sicurezza (riducibilità, completezza, impossibilità). L’intuizione che l’hardware general-purpose più un software adatto realizzino qualsiasi computazione effettiva è oggi incarnata da computer, cloud e dispositivi mobili. Sul versante scientifico più ampio, Turing applica metodi computazionali anche alla morfogenesi (1952), mostrando come semplici regole locali (reazione–diffusione) generino struttura: un’anticipazione dell’uso del calcolo come strumento esplicativo nelle scienze naturali.
Conclusione
Con un’unica, brillante idea — descrivere il calcolo come manipolazione di simboli da parte di una macchina estremamente semplice — Turing ha fornito il linguaggio concettuale con cui pensiamo a programmi, problemi e prove. La sua opera definisce che cosa è il calcolo, mostra che cosa non può essere calcolato e suggerisce come giudicare l’intelligenza delle macchine. È difficile immaginare l’informatica teorica senza la geometria essenziale tracciata dai suoi risultati.