Vita, morte e MIRACOLI di Alan Mathison Turing

La vita di Turing si può leggere in molte biografie: ottima ed enciclopedica tra di esse quella di Andrew Hodges (pubblicata in Italia da Bollati Boringhieri); molto piacevole l'agile libretto di Gianno Rigamonti, TURING, il genio e lo scandalo (Flaccovio editore, Palermo, 1991). In entrambi i libri si possono anche trovare cenni della sua tragica fine, della quale la società inglese - ma chissà altre società come si sarebbero comportate - non può certo menar vanto.

E i miracoli? Ebbene sì, ha fatto anche questi o, almeno, a sentire Kurt Gödel, ne ha fatto almeno uno, anche se in combutta con altri logici del primo Novecento.

Martin Davis, grande logico e informatico americano, allievo di Emil Post - un altro "grande" che ha avuto una vita infelice - e autore, assieme a Hilary Putnam e Julia Robinson, di tanti importanti risultati che hanno poi permesso a Jurij Matijasievic di fare l'ultimo passo e risolvere il decimo Problema di Hilbert, nell'introduzione a un suo libro di Informatica teorica scriveva, nel 1982, che "It is remarkable that it has proved possible to give a precise mathematical characterizatioin of the class of processes that can be carried out by purely mechanical means. It is in fact the possibility of such a characterization that underlies the ubiquitous applicability of digital computers".

Ma che c'entra Turing con tutto questo? C'entra perché è stato uno degli autori e dei fondatori di questa teoria, assieme ad Alonzo Church, a Stephen Cole Kleene e lo stesso Gödel. Ma fra tutti era quello che alla generalità di questa teoria e alla sua portata rivoluzionaria ci credeva di più. Analizzando il modo in cui un essere umano procede quando deve effettuare un computo arbitrario, ha estratto alcuni elementi base essenziali e, idealizzando questi, un modello astratto di macchina, la Macchina di Turing appunto.

Alan M. Turing

Alonzo Church

Non contento di questo, ha anche enunciato una Tesi, che va sotto il nome di Tesi di Church-Turing, che afferma che qualsiasi funzione intuitivamente calcolabile - cioè tale che noi abbiamo l'impressione, o la convinzione, di riuscire a calcolarla in qualche modo, con le idee e le tecniche che ci possono venire in mente al momento, questa funzione è calcolabile anche da una Macchina di Turing.
Church, proprio nello stesso periodo aveva proposto un altro modello di computo, più formale, meno intuitivo e il nostro Turing in appendice al suo articolo dimostrò che i due modelli erano equivalenti.

Gödel, oltre ad essere timido e introverso, era pure più prudente. Quando gli cominciarono a parlare di queste cose e della possibilità di costruire una teoria che carpisse in modo del tutto generale la nozione intuitiva di "calcolabile" si mostrò scettico. In quegli anni la Logica aveva fatto tanti passi avanti, alcuni sconvolgenti. Di alcuni - cruciali - lui stesso era stato il massimo e unico artefice. Ma i risultati erano sempre legati a un particolare formalismo, a uno specifico sistema formale. Così era stato per nozione di "definibile" e per quella di "dimostrabile". Perché doveva avvenire qualcosa di diverso per quella di "computabile"? Ma riflessivo e onesto come sempre, il nostro Kurt, ci pensa e ci ripensa e, alla fine, si convince del contrario. Una volta convinto, è quello che con più forza sottolinea l'importanza di questi risultati tutte le volte che ritorna sull'argomento:

Kurt Gödel

"It it seems to me that the great importance of the concept of general recursiveness (or Turing computability) is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e. not depending on the formalism choosen: In all other cases treated previously such as demonstrability or definability, one has been able to define them only relative to a given language … for the concept of computability, however although it is merely a special kind of demostrability or decidability the situation is different. By a kind of miracle it is not necessary to distinguish orders and the diagonal procedure does not lead outside the defined notion", scriveva nel 1946. Osserviamo che non aveva mai parlato di miracolo, presentando i suoi risultati.

E ancora nel 1965: "The concept of "computable" is in a certain sense "absolute", while practically all other familiar metamathematical concepts (e.g., provable, definable, etc.) depend quite essentially on the system with respect to which they are defined".

Il miracolo consiste dunque nell'avere formulato una teoria che carpisce integralmente una nozione intuitiva - quella di calcolabile - e anche nel fatto che in questa teoria riusciamo pure a dimostrare un po' di cose interessanti. Citiamone solo due. Un risultato positivo e uno negativo.
Quello positivo ci dice che esiste una Macchina di Turing UNIVERSALE, cioè un'unica macchina che è in grado di fare il lavoro di qualsiasi altra macchina di Turing particolare, specifica. E' quello a cui noi oggi siamo abituati: un qualsiasi calcolatore, il nostro portatile che pesa meno di due chili, può fare qualsiasi cosa (qualsiasi cosa sia computabile, ovviamente, non esageriamo!). Non è che con il mio calcolatore posso fare, in linea di principio, cose diverse di quelle che si possono fare con il calcolatore di un mio amico, prescindendo da limitazioni concrete, di memoria e altro, ovviamente. I nostri calcolatori, cioè, sono - in un certo senso - Macchine di Turing Universali.

Capiamo meglio, adesso la frase di Martin Davis che abbiamo citato all'inizio.

Passiamo al risultato negativo. La teoria è cosi potente che ci permette di dimostrare che esistono dei problemi per i quali possiamo dimostrare che non esiste nessun algoritmo di decisione, cioè nessun procedimento meccanico, nessun programma, che mi permetta di rispondere con un SI o con un NO alla domanda posta. Uno lo abbiamo già citato, è il decimo Problema di Hilbert, che i matematici conoscono molto bene. I famosi risultati di Gödel ne sono un altro illustre esempio, che tra l'altro in questo contesto acquistano una maggiore comprensibilità. Ma possiamo portare anche esempi più terra terra (apparentemente). Uno è il cosiddetto Teorema della Fermata che afferma che non esiste nessun programma in grado di dirci se un altro programma fatto girare su un certo valore della variabile d'ingresso, si fermerà prima o poi per darci il risultato. Un altro è il teorema di corrispondenza di Post che ci dice che, in generale, non possiamo sapere se una specie di gioco fatto con le tessere del domino ammette o no una soluzione.

David Hilbert

Questa Teoria è uscita dalla testa di Turing (e anche di altri grandi come lui). Una strana coincidenza è che tutti si sono dati convegno per trovare indipendentemente l'uno dall'altro questi risultati a metà degli anni Trenta (i lavori sono apparsi nel 1936). Rispetto agli altri suoi sodali, Turing ha fatto anche qualche altra cosa in più. Già abbiamo ricordato la visualizzabilità del suo modello - della sua Macchina - rispetto ad altre proposte, pur equivalenti dal punto di vista matematico. Abbiamo ricordato anche la grinta con la quale ha sostenuto le sue idee. Durante la guerra, riuscì a decifrare i codici della marina tedesca e, dopo la guerra, si diede da fare per costruirli i calcolatori mentre, contemporaneamente, delineava gli elementi matematici base di una teoria della morfogenesi.

Nel 1950 scrisse, poi, un articolo dal titolo provocatorio "Macchine calcolatrici e intelligenza" per la rivista filosofica inglese Mind. Si mise a scherzare su ciò che i calcolatori avrebbero potuto fare e sulla possibilità di una "intelligenza meccanica", introducendo un gioco (il gioco dell'imitazione) come test empirico per stabilire l'intelligenza di una macchina. Il giorno in cui non saremo in grado di distinguere dalle risposte fornite da un essere umano e da una macchina quale sia l'uomo e quale sia la macchina, vuol dire che le macchine hanno raggiunto un livello "accettabile" di intelligenza.

In una parola, nel tempo libero, inventò anche l'Intelligenza Artificiale, cinque anni prima che questo nome fosse inventato. Il suo allievo Robin Gandy, scomparso anche lui da qualche anno, ricordava che Turing si era divertito moltissimo a scrivere questo articolo, che rideva da matti quando gliene leggeva alcuni passi. Un altro segno della sua grandezza, la capacità di ridere anche delle proprie cose e di divertirsi nel fare cose importanti, di assoluta grandezza.
Gandy, ricostruendo la nascita della teoria della calcolabilità, osservava anche lui che l'esistenza di una teoria profonda aiuta lo sviluppo della tecnologia connessa. Così è stato per l'elettricità che ha potuto basarsi sulla teoria di Maxwell. Così è stato per l'Informatica che ha potuto basarsi sulla Teoria della calcolabilità. Così non è stato per i motori a scoppio, che hanno contribuito loro allo sviluppo della Termodinamica, invece di trovarsela bella e pronta. Non è un caso che si sono sviluppati molto più lentamente.

Finora siamo stati fortunati con l'Informatica, ma i nuovi sviluppi, la rete, i sistemi distribuiti, non hanno una vera teoria su cui fondarsi. Per i problemi centrali di questi settori la teoria della calcolabilità è un riferimento troppo remoto e generico per svolgere un ruolo significativo. Se vogliamo che lo sviluppo ulteriore delle nostre tecnologie continui ad essere rapido come è stato finora (e non totalmente alieno, come rischia di essere lo sviluppo tecnologico non fondato su teorie generali e profonde), sarebbe bene investire anche sulla ricerca di base, invitare tutti a riflettere sulle grosse questioni di fondo, sperando che qualche nipotino di Turing ci dia prima o poi una mano ad avere un riferimento teorico per quello che sta succedendo.

Vita, morte e MIRACOLI di Alan Mathison Turing

Settimo Termini