Nel 1936, un matematico di Cambridge di 24 anni di nome Alan Turing pubblicò un articolo che avrebbe posto le fondamenta teoriche dell’intero campo dell’informatica, anni prima che venisse costruito un computer general-purpose. Intitolato “Sui numeri calcolabili, con un’applicazione all’Entscheidungsproblem”, l’articolo si proponeva di rispondere a una domanda specifica posta da David Hilbert, ma nel farlo Turing inventò un modello astratto di calcolo così potente e così chiaro da restare, ancora oggi, il fondamento concettuale dell’informatica.
Il problema che Turing si propose di risolvere.
L’obiettivo dichiarato dell’articolo era risolvere l’Entscheidungsproblem (“problema della decisione”), una sfida formulata da Hilbert nel 1928: esiste un metodo definito — un algoritmo — capace di determinare, per qualsiasi affermazione data in un sistema logico formale, se tale affermazione sia dimostrabile? Hilbert sperava che la risposta fosse sì, il che avrebbe significato che la matematica poteva, in linea di principio, essere interamente meccanizzata.
Per porre questa domanda in modo rigoroso, Turing aveva bisogno di una definizione precisa di cosa significhi “calcolare” qualcosa — cosa costituisca una procedura meccanica, passo dopo passo. Questa necessità di una definizione formale di algoritmo è ciò che lo condusse al suo contributo centrale e più duraturo.
La macchina di Turing.
Invece di ragionare in modo astratto sul calcolo, Turing immaginò un dispositivo fisico semplice: un nastro infinito diviso in celle, ciascuna contenente un simbolo; una testina di lettura/scrittura in grado di spostarsi di una cella a sinistra o a destra; e un insieme finito di stati interni che determinano, in base allo stato corrente e al simbolo letto, quale simbolo scrivere, in quale direzione muoversi e in quale stato entrare successivamente.
Nonostante la sua estrema semplicità, Turing sostenne in modo convincente che una tale macchina potesse svolgere qualsiasi processo che un “calcolatore” umano — all’epoca, termine che indicava una persona che eseguiva calcoli a mano, seguendo un insieme fisso di regole — potesse svolgere. Questa affermazione, secondo cui la sua macchina cattura l’intera portata di ciò che è meccanicamente calcolabile, è oggi nota come tesi di Church-Turing (poiché il logico americano Alonzo Church era giunto indipendentemente a una nozione equivalente, chiamata lambda calcolo, nello stesso periodo).
Turing introdusse inoltre l’idea di una macchina universale: una singola macchina di Turing che, dato l’insieme codificato di istruzioni di qualsiasi altra macchina di Turing insieme al suo input, potesse simularne esattamente il comportamento. Questa è l’antenata teorica di ogni computer moderno: un dispositivo general-purpose che esegue qualunque programma gli venga fornito, invece di essere costruito per un unico compito specifico.
Numeri calcolabili e non calcolabili.
Turing definì un numero reale “calcolabile” se le sue cifre decimali potevano essere prodotte da una tale macchina, funzionante all’infinito, cifra dopo cifra. Ciò gli permise di porre una domanda più affilata: tutti i numeri reali sono calcolabili? Utilizzando un argomento di diagonalizzazione che ricorda la dimostrazione di Cantor sulla non numerabilità dei numeri reali, Turing dimostrò che la risposta è no — i numeri calcolabili, sebbene infiniti in quantità, formano solo un insieme numerabile, e quindi quasi tutti i numeri reali sono, in un senso ben definito, per sempre fuori dalla portata di qualsiasi algoritmo.
Il problema della fermata e la risposta a Hilbert.
Da questo apparato concettuale, Turing derivò il suo risultato più celebre: il problema della fermata (halting problem) è indecidibile. Non esiste un algoritmo generale — nessuna macchina di Turing — capace di determinare, per ogni possibile macchina e input, se quella macchina si fermerà eventualmente o continuerà a funzionare per sempre. La dimostrazione utilizza nuovamente un espediente di diagonalizzazione: Turing suppone che una tale macchina di decisione esista, quindi costruisce una contraddizione facendo sì che una macchina riceva in input la propria stessa descrizione, in un ciclo autoreferenziale che rispecchia la medesima struttura logica utilizzata da Gödel cinque anni prima nei suoi teoremi di incompletezza.
Questo risultato permise a Turing di rispondere direttamente all’Entscheidungsproblem di Hilbert: no, non esiste una procedura meccanica generale per decidere la dimostrabilità di affermazioni matematiche arbitrarie. Se una tale procedura esistesse, potrebbe essere usata per risolvere il problema della fermata, che Turing aveva appena dimostrato essere impossibile.
Eredità.
Lo scopo immediato dell’articolo era negativo — mostrare cosa non si potesse fare — ma il suo impatto duraturo fu straordinariamente generativo. Definendo il calcolo con precisione matematica totale, Turing fornì a ingegneri e scienziati successivi esattamente il vocabolario concettuale necessario per costruire macchine reali: la distinzione tra hardware e software, la possibilità stessa di un computer general-purpose a programma memorizzato, e i limiti teorici che ancora oggi delineano i dibattiti dell’informatica su quali problemi siano risolvibili in assoluto, indipendentemente da quanto tempo o hardware si abbia a disposizione.
È una notevole ironia storica che un articolo dedicato a dimostrare i limiti del calcolo meccanico sia diventato il documento fondativo della scienza della costruzione di macchine calcolatrici. Turing non si limitò a rispondere alla domanda di Hilbert; diede all’umanità un linguaggio rigoroso per pensare agli algoritmi, e con esso, il progetto dell’era digitale.