Nel 1936 un matematico inglese di ventiquattro anni, Alan Turing, scrisse un articolo che non parlava di computer, perché i computer non esistevano ancora. Parlava di un problema di logica matematica. Per risolverlo Turing inventò una macchina immaginaria così semplice da sembrare un giocattolo, e così generale da descrivere tutto ciò che un computer potrà mai fare. Quella macchina porta oggi il suo nome.
Il problema di partenza
Negli anni Venti il matematico tedesco David Hilbert aveva posto una serie di domande sui fondamenti della matematica. Una di queste era l'Entscheidungsproblem, il «problema della decisione»: esiste un procedimento meccanico che, data una qualsiasi affermazione della logica matematica, permetta di stabilire in un numero finito di passi se è dimostrabile?
Per rispondere bisognava prima chiarire una cosa che tutti davano per scontata: che cosa significa, esattamente, «procedimento meccanico»? Turing affrontò proprio questa domanda nel suo articolo On Computable Numbers, with an Application to the Entscheidungsproblem.
La macchina di Turing
Turing partì da un'osservazione: che cosa fa una persona quando esegue un calcolo con carta e matita, seguendo regole precise? Legge un simbolo, decide che cosa fare in base a ciò che ha letto e a ciò che ricorda, scrive qualcosa, si sposta. Ridusse questo comportamento all'essenziale.
I componenti
- Un nastro infinito diviso in caselle, ognuna delle quali può contenere un simbolo o essere vuota.
- Una testina che legge e scrive una casella alla volta e può spostarsi a sinistra o a destra.
- Un numero finito di stati interni, che rappresentano ciò che la macchina «ricorda».
- Una tabella di regole: per ogni combinazione di stato attuale e simbolo letto, dice che cosa scrivere, in che direzione muoversi e in quale stato passare.
Niente altro. Non ci sono operazioni aritmetiche predefinite, né memoria indirizzabile, né istruzioni complesse.
Un esempio
Una macchina che aggiunge 1 a un numero binario scritto sul nastro, partendo dalla cifra più a destra, potrebbe avere regole come queste:
| Stato | Simbolo letto | Scrive | Movimento | Nuovo stato |
|---|---|---|---|---|
| riporto | 1 | 0 | sinistra | riporto |
| riporto | 0 | 1 | fermo | fine |
| riporto | vuoto | 1 | fermo | fine |
Partendo da 1011 la macchina trasforma gli ultimi due 1 in 0, trova uno 0, lo trasforma in 1 e si ferma: il risultato è 1100. Sembra poco, ma combinando regole di questo tipo si può costruire qualsiasi calcolo.
La macchina universale
L'idea più profonda dell'articolo è un'altra. Turing mostrò che la tabella di regole di una macchina si può a sua volta scrivere sul nastro come sequenza di simboli. Esiste quindi una macchina universale: una singola macchina che, leggendo sul nastro la descrizione di un'altra macchina e i suoi dati, ne simula il comportamento.
Oggi lo diamo per scontato: lo stesso computer esegue un foglio di calcolo, un browser e un videogioco, perché i programmi sono dati caricati in memoria. Nel 1936 era una scoperta concettuale. La distinzione tra «macchina» e «programma» diventava relativa: una macchina sufficientemente generale può diventare qualsiasi altra macchina.
Il limite: ciò che non si può calcolare
Con questo strumento Turing rispose alla domanda di Hilbert, e la risposta fu negativa. Dimostrò che esistono problemi ben definiti che nessuna macchina può risolvere. L'esempio più noto, formulato in seguito come problema della fermata, è questo: non esiste un programma che, dato un qualsiasi altro programma e i suoi dati, stabilisca sempre correttamente se si fermerà o continuerà all'infinito.
L'argomento è per assurdo. Se un simile programma esistesse, se ne potrebbe costruire un altro che lo interroga su sé stesso e poi fa l'opposto di ciò che è stato previsto: si ferma se è stato previsto che non si fermi, e viceversa. La contraddizione dimostra che il programma di partenza non può esistere.
Chi sviluppa software incontra le conseguenze pratiche di questo risultato. Nessuno strumento di analisi statica potrà mai trovare con certezza tutti i cicli infiniti di un programma qualsiasi: può solo usare approssimazioni, segnalando casi sospetti.
Turing e Church
Negli stessi mesi il logico statunitense Alonzo Church arrivò allo stesso risultato negativo usando un formalismo diverso, il lambda calcolo. Turing dimostrò che i due approcci definiscono la stessa classe di funzioni calcolabili. Poi andò a Princeton, dove completò il dottorato sotto la guida di Church. L'idea che queste definizioni equivalenti catturino davvero il concetto intuitivo di calcolo è nota come tesi di Church-Turing.
L'eredità
Dopo la guerra, durante la quale lavorò alla decrittazione a Bletchley Park, Turing progettò un computer reale, l'ACE, e nel 1950 scrisse un celebre articolo sull'intelligenza delle macchine. Morì nel 1954. Dal 1966 l'Association for Computing Machinery assegna il premio Turing, considerato il più importante riconoscimento in informatica.
Ma il contributo più duraturo resta quello del 1936. Ogni volta che diciamo che un linguaggio di programmazione è «Turing-completo» intendiamo che può calcolare tutto ciò che calcola una macchina di Turing: cioè tutto ciò che è calcolabile.
In sintesi
- Nel 1936 Turing definì in modo rigoroso che cosa sia un procedimento meccanico, con una macchina fatta di nastro, testina, stati e regole.
- La macchina universale, che simula qualsiasi altra macchina leggendone la descrizione, anticipa il concetto di programma memorizzato.
- Turing dimostrò che esistono problemi non risolvibili da alcuna macchina, come quello noto oggi come problema della fermata.
- Alonzo Church giunse indipendentemente allo stesso risultato con il lambda calcolo.
