Tu sei qui

Cosa possiamo calcolare? L’influsso di Alan Turing a 100 anni dalla sua nascita

Alberto Pettorossi
Maurizio Proietti
Gennaio 2012

Nel 2012 ricorre il centenario della nascita del matematico britannico Alan Turing (23 giugno 1912 - 7 giugno 1954). Egli ha contribuito in modo del tutto particolare a gettare le basi dell’informatica, dell’odierna teoria della computazione e di quella che oggi chiamiamo, con termine forse impreciso e spesso non ben compreso, "intelligenza artificiale".

Centrale per questi contributi è il lavoro che Alan Turing ha scritto nel 1936 intitolato: "On Computable Numbers, with an Application to the Entscheidungsproblem" (Sui Numeri Calcolabili, con un’Applicazione al Problema della Decisione, “Proceedings of the London Mathematical Society”, 2, Vol. 42, 230-265, 1936-37). In questo lavoro egli esamina il concetto di "calcolabilità effettiva", un concetto empirico che, egli riesce a formalizzare in modo preciso, introducendo un modello di macchina di calcolo che in suo onore è, da allora, chiamato macchina di Turing.

Tale formalizzazione è risultata perfettamente adeguata per tutti gli sviluppi successivi della teoria della computazione ed è sempre stata, ed è ancora, un punto di riferimento imprescindibile.

Alan Turing ha anche studiato la relazione tra l’intelligenza e le macchine di calcolo e ha indagato sulla questione dell’apprendimento nelle macchine (Computing Machinery and Intelligence, “Mind” 59 (1950) 433-460).

Un altro suo lavoro spesso citato è quello su: "The Chemical Basis of Morphogenesis" (La Base Chimica della Morfogenesi, “Philosophical Transactions of the Royal Society of London”, Series B 237 (641) 37-72, 1952), in cui egli descrive reazioni chimiche oscillanti, simili a quelle di Belousov-Zhabotinsky, che sono state poi effettivamente osservate negli anni 60.

Ricordiamo, infine, il contributo importante e socialmente molto apprezzato, che Alan Turing ha dato nel campo della crittografia, un campo meno teorico, ma tuttavia fortemente collegato alla matematica e al calcolo automatico. Lavorando, insieme ad altri specialisti, presso il centro di Bletchley Park in Gran Bretagna durante la Seconda Guerra Mondiale, egli ha sviluppato sistemi elettromeccanici per la decrittazione dei messaggi cifrati della Marina Tedesca che utilizzava la macchina Enigma.

Questi sono i punti salienti dell’attività scientifica e professionale di Alan Turing.

Ritorniamo ora, con più di dettaglio, sui contributi per cui egli è considerato il padre della scienza dei calcolatori, dell’informatica e dell’intelligenza artificiale per metterne in luce le idee fondamentali.

Turing caratterizza il "calcolabile"

La macchina di Turing è un dispositivo con un numero finito di stati che ha in più a disposizione una sequenza potenzialmente infinita di celle elementari, detta nastro (naturalmente, ad ogni momento del calcolo solo un numero finito di tali celle è effettivamente utilizzato). La macchina può leggere quello che è scritto in una di queste celle e può scrivere sulla cella letta un nuovo simbolo, spostandosi poi a leggere la cella di sinistra o di destra rispetto a quella appena letta.

Nonostante la sua semplicità, questa macchina riesce a calcolare tutte le funzioni matematiche (da numeri naturali a numeri naturali) che sono "effettivamente calcolabili", cioè che sono calcolabili da un qualsiasi dispositivo fisicamente realizzabile, anche molto più potente, come lo sono i calcolatori odierni.

La macchina di Turing, inoltre, riesce a calcolare tutte funzioni che sono calcolabili con i dispositivi che la tecnologia ci metterà a disposizione nel futuro (questa affermazione va sotto il nome di Tesi di Church-Turing). In gergo tecnico, si dice che per ogni funzione ricorsiva parziale si può definire una particolare macchina di Turing che la calcola (o, equivalentemente, per ogni problema semidecidibile esiste una macchina di Turing che lo risolve).

Esistono (e sono formalmente definibili) funzioni non calcolabili e per queste non esiste una macchina di Turing che le calcola. In questo senso la macchina di Turing definisce esattamente il limite della calcolabilità effettiva.

Un esempio di funzione non calcolabile, esempio fornito da Turing stesso, è la funzione che per ogni data macchina di Turing, vale 1 se la macchina data si ferma e vale 0 se la macchina data non si ferma.

Il "calcolatore universale" e la differenziazione tra hardware e software

Nel lavoro del 1936 Turing introduce una particolare macchina di Turing, detta macchina di Turing universale, che riesce a calcolare una qualsiasifunzione ricorsiva parziale. Questa macchina universale esegue il calcolo avendo nel suo nastro, inizialmente, la descrizione (come sequenza di caratteri, ognuno nella sua cella) di una macchina di Turing che calcola la funzione ricorsiva parziale data, seguita dalla sequenza di caratteri che è l’input per tale funzione. La descrizione della macchina di Turing che calcola la funzione data è il software, cioè il programma di calcolo memorizzato nel nastro, mentre l’hardware è, appunto, la stessa macchina di Turing universale.

In un certo senso, quando compriamo un personal computer, noi essenzialmente compriamo una versione sofisticata della macchina di Turing universale. In pratica le cose sono un poco più complicate a causa, tra l’altro, della presenza di ciò che oggi chiamiamo il "sistema operativo" e i "compilatori", ma fondamentalmente il meccanismo di calcolo dei nostri calcolatori è appunto quello della macchina di Turing universale, come è stata poi ingegnerizzata da John von Neumann (1903-1957), un altro pioniere dell’informatica.

Possiamo dire che il grande passo in avanti della macchina di Turing rispetto ad altre macchine di calcolo proposte precedentemente, quali la macchina calcolatrice ideata da Pascal nel 1642, è appunto l’esistenza della macchina universale, che può simulare il comportamento di una qualsiasi altra macchina di calcolo, una volta fornitane la descrizione (come programma di calcolo).

L’"intelligenza" e la "capacità di ragionamento" nelle macchine

Turing tratta la questione della capacità delle macchine di "pensare" come quella della determinazione della misura di una grandezza fisica. E, come per misurare la lunghezza di un oggetto, occorre decidere quando due oggetti hanno la stessa lunghezza, egli individua un test di uguaglianza di intelligenza, che oggi è conosciuto col nome di "test di Turing". Esso può essere definito così. Si considerano tre stanze isolate, l’unica comunicazione tra esse può avvenire attraverso terminali di calcolatori che permettono di far domande e ricevere risposte. In una stanza sta un calcolatore, in una seconda sta un persona e in una terza sta un interrogatore. Attraverso una serie di domande e le conseguenti risposte, l’interrogatore deve cercare di individuare la stanza in cui sta il calcolatore e quella in cui sta la persona. Se non ci riesce, si dice che la macchina ha l’intelligenza uguale a quella della persona.

Varie versioni di questo test sono state proposte per specificarlo con più precisione. In particolare, si sono indicati vari protocolli di comunicazione per porre le domande e ricevere le risposte e si è indicata la natura dell’interrogatore.

Non ci soffermiamo su questi punti. E’, invece, di interesse la questione psicologica e antropologica di base, cioè, se l’intelligenza si manifesti attraverso risposte a domande o se l’intelligenza, interagendo con la volontà e la libertà, si manifesti anche al di là di un dialogo con un interrogatore.

Meno controversa è la questione dell’apprendimento delle macchine, che si riduce in un certo senso, alla capacità dei programmi di calcolo di modificarsi e di migliorarsi, in seguito a operazioni già eseguite in cui la performance non è stata considerata soddisfacente (tale valutazione può essere fatta con l’ausilio di particolari programmi di controllo). I programmi possono essere adattativi perché i programmi sono scritti nel nastro della macchina di Turing (oggi si direbbe, sono scritti nella memoria del calcolatore) e, pertanto, come un qualsiasi altro dato memorizzato, possono essere modificati in base a risultati parziali del calcolo o, appunto, in base a precedenti esecuzioni del programma stesso. Per esempio, tali programmi adattativi si possono usare per sviluppare programmi di calcolo che giocano a scacchi o ad altri giochi similari.

La tecnologia attuale che utilizza il calcolatore come mezzo di controllo di apparecchiature sofisticate, o come sistema di supporto alle decisioni (in campo medico o finanziario, per esempio), o come dimostratore automatico di teoremi, o verificatore di proprietà di programmi (in modo da individuare, per esempio, se essi sono dei "virus" o no), o come simulatore di fenomeni fisici, o come solutore di equazioni differenziali e problemi matematici in genere, già permette il miglioramento dei programmi. Ma ciò rientra nella semplice capacità di calcolo dei computer in quanto la capacità deduttiva e di ragionamento in una teoria formale o logica è facilmente riducibile, come Alan Turing ha dimostrato, a manipolazione di simboli che può essere guidata da opportune strategie di controllo.