I pionieri dell'informatica: Alan Turing

Il metodo di Turing ha avuto un profondo significato per la scienza emergente dell’informatica.

Alan Turing, per esteso Alan Mathison Turing, nasce il 23 giugno 1912 a Londra, in Inghilterra.

Matematico e logico, ha dato importanti contributi alla matematica, alla crittoanalisi, alla logica, alla filosofia e alla matematica biologia e anche alle nuove aree chiamate in seguito informatica, scienze cognitive, intelligenza artificiale e vita artificiale.

Figlio di un funzionario statale, Turing ha studiato in una delle migliori scuole private per poi entrare all’Università di Cambridge per studiare matematica nel 1931.

Dopo la laurea nel 1934, gli fu riconosciuta una borsa di studio al King’s College (il suo college dal 1931) in grazie alle sue ricerche sulla teoria della probabilità.

Nel 1936 l’articolo seminale di Turing “On Computable Numbers, with an Application to the Entscheidungsproblem” fu raccomandato per la pubblicazione dal logico matematico americano Alonzo Church, che aveva appena pubblicato un documento con il quale raggiungeva le stesse conclusioni di Turing, sebbene da un metodo diverso.

Nello stesso anno Turing si trasferì alla Princeton University per studiare per un dottorato di ricerca. in logica matematica sotto la direzione di Church (completato nel 1938).

La Macchina di Turing

Le “macchine di Turing”, descritte per la prima volta dal matematico nel 1936-37, sono semplici dispositivi computazionali astratti il cui obiettivo è indagare sull’estensione e sui limiti di ciò che può essere calcolato.

Le “macchine automatiche” di Turing, come le chiamò nel 1936, furono appositamente ideate per il calcolo dei numeri reali.
Furono nominate per la prima volta “macchine di Turing” da Alonzo Church in una recensione dell’articolo di Turing nel 1937.
Oggi sono considerati uno dei modelli fondamentali della computabilità e dell’informatica teorica.

Turing ha introdotto le macchine sue omonime nel contesto della ricerca sui fondamenti della matematica e, più in particolare, ha usato questi dispositivi astratti per dimostrare che non esiste un metodo o una procedura generale efficace per risolvere, calcolare o calcolare ogni istanza del seguente problema.

Problema decisionale (Entscheidungsproblem): Il problema di decidere per ogni affermazione in logica di primo ordine, il cosiddetto calcolo funzionale ristretto, se è derivabile o meno in quella logica.

Si noti che nella sua forma originale (Hilbert & Ackermann 1928), il problema era posto in termini di validità piuttosto che di derivabilità.
Dato il Teorema di Completezza di Kurt Gödel (1929), dimostrare che esiste una procedura efficace (o meno) per la derivabilità è anche una soluzione del problema nella sua validità.

Per affrontare questo problema, è necessaria una nozione formalizzata di “procedura efficace” e le macchine di Turing avevano lo scopo di fare esattamente questo.

Il Problema Decisionale (Entscheidungsproblem): quello che i matematici chiamavano un “procedura efficace” per risolvere tale problema era semplicemente un metodo che poteva essere paragonato a quello di un impiegato matematico umano che lavorava a memoria.

Ai tempi di Turing, questi lavoratori meccanici erano infatti chiamati “computer” e i computer umani svolgevano alcune mansioni poi svolte in seguito dai computer elettronici. L’Entscheidungsproblem ha cercato un metodo efficace per risolvere il problema matematico fondamentale di determinare esattamente quali affermazioni matematiche sono dimostrabili all’interno di un dato sistema matematico formale e quali no.

Un metodo per determinarlo è chiamato “metodo decisionale”.

Nel 1936 Turing e Church dimostrarono per vie parallele che, in generale, il problema dell’Entscheidungsproblem non ha soluzione, dimostrando che nessun sistema formale coerente di aritmetica ha un metodo decisionale efficace e di conseguenza, anche i sistemi puramente logici, notevolmente più deboli dell’aritmetica, non lo possiedono.

Questo risultato e altri – in particolare i Teoremi di Incompletezza del matematico-logico Kurt Gödel – hanno deluso le speranze, nutrite da alcuni matematici, di scoprire un sistema formale che riducesse l’intera matematica a metodi che i computer (umani) potrebbero eseguire.

Fu nel corso del suo lavoro sull’Entscheidungsproblem che il matematico londinese inventò la macchina universale di Turing, un sistema informatico astratto che incapsula i principi logici fondamentali del computer digitale.

La Tesi Church-Turing

Un passo importante nell’argomentazione di Turing sul problema della decisione è stata l’affermazione, ora chiamata tesi di Church-Turing, che tutto ciò che è umanamente calcolabile può essere calcolato anche dalla macchina universale di Turing.

L’affermazione è importante perché segna i limiti del calcolo umano.

Church nella sua opera utilizzò invece la tesi che tutte le funzioni umanamente calcolabili sono identiche a quelle che chiamò funzioni definibili lambda (funzioni sugli interi positivi i cui valori possono essere calcolati mediante un processo di sostituzione ripetuta).

Turing dimostrò nel 1936 che la tesi di Church era equivalente alla sua, dimostrando che ogni funzione definibile lambda è calcolabile dalla macchina universale di Turing e viceversa.

In una revisione del lavoro di Turing, Church ha riconosciuto la superiorità della formulazione della tesi di Turing sulla propria (che non faceva alcun riferimento alle macchine informatiche), affermando che il concetto di calcolabilità da parte di una macchina di Turing “ha il vantaggio di rendere con efficacia evidente immediatamente tale identificazione”.

Il Problema Filosofico della Computazione

Nel suo contesto originale, l’identificazione di Turing tra i numeri calcolabili e le macchine di Turing mirava a dimostrare che il problema decisionale non è un problema calcolabile e quindi non un cosiddetto problema di “processo generale”.

L’assunto di base da fare per questo risultato è che la nostra nozione “intuitiva” di computabilità può essere formalmente definita come computabilità di Turing e quindi che non ci sono problemi “calcolabili” che non siano computabili da Turing.

Ma qual era la nozione “intuitiva” di calcolabilità di Turing e come possiamo essere sicuri che copra davvero tutti i problemi calcolabili e, più in generale, tutti i tipi di calcoli? Questa è una domanda fondamentale nella filosofia dell’informatica.

Al momento in cui Turing stava scrivendo il suo articolo, il computer moderno non era ancora stato sviluppato e quindi le riformulazioni della tesi che identificano la computabilità di Turing con la computabilità di un computer moderno sono interpretazioni piuttosto che affermazioni storicamente corrette della tesi del matematico britannico.

Le macchine informatiche esistenti all’epoca in cui Turing scrisse il suo articolo, come l’analizzatore differenziale o le calcolatrici da tavolo, erano piuttosto limitate in ciò che potevano calcolare e venivano utilizzate in un contesto di pratiche computazionali umane.
Non sorprende quindi che Turing non abbia tentato di formalizzare il calcolo automatico, ma piuttosto il calcolo umano e quindi i problemi calcolabili nell’articolo di Turing diventano calcolabili con mezzi umani.

Questo è diviene esplicito dove è possibile dimostrare che le macchine di Turing sono un modello “naturale” di computazione umana.
L’analisi si traduce in una sorta di calcolatore umano astratto che soddisfa una serie di condizioni diverse che sono radicate nel riconoscimento di Turing di una serie di limitazioni umane che delimitano ciò che possiamo calcolare (del nostro apparato sensoriale ma anche del nostro apparato mentale).

Risolvere l'Enigma

Tornato dagli Stati Uniti alla sua borsa di studio al King’s College nell’estate del 1938, Turing si iscrisse alla Government Code and Cypher School e, allo scoppio della guerra con la Germania nel settembre 1939, si trasferì al quartier generale dell’organizzazione in tempo di guerra. a Bletchley Park, Buckinghamshire.

Poche settimane prima, il governo polacco aveva fornito a Gran Bretagna e Francia i dettagli dei successi polacchi contro Enigma, la principale macchina di cifratura utilizzata dall’esercito tedesco per crittografare le comunicazioni radio.

Già nel 1932, un piccolo team di matematici-crittoanalisti polacchi, guidato da Marian Rejewski, era riuscito a dedurre il cablaggio interno di Enigma, e nel 1938 il team di Rejewski aveva ideato una macchina per la decodifica del codice chiamata “Bomba” (la parola polacca per una specie di gelato).

Il funzionamento della “Bomba” dipendeva dalle procedure operative tedesche, e un cambiamento di tali procedure nel maggio 1940 la rese inutile.

Durante l’autunno del 1939 e la primavera del 1940, Turing e altri progettarono una macchina per decifrare tali codici. Per il resto della guerra, questa nuova “Bomba” fornì agli alleati grandi quantità di informazioni militari.

All’inizio del 1942 i crittoanalisti di Bletchley Park stavano decodificando circa 39.000 messaggi intercettati ogni mese, una cifra che in seguito salì a più di 84.000 al mese – due messaggi al minuto, giorno e notte.
Nel 1942 Turing ideò anche il primo metodo sistematico per violare i messaggi crittografati dalla sofisticata macchina cifratrice tedesca che gli inglesi chiamavano “Tunny”.

Alla fine della guerra, Turing fu nominato Ufficiale dell’Eccellentissimo Ordine dell’Impero Britannico (OBE) per il suo lavoro di decrittazione.

Lo Sviluppo del Computer

Nel 1945, finita la guerra, Turing fu reclutato al National Physical Laboratory (NPL) di Londra per creare un computer elettronico.
Il suo progetto per l’Automatic Computing Engine (ACE) è stata la prima specifica completa di un computer digitale multiuso elettronico a programma memorizzato.

Se l’ACE di Turing fosse stato costruito come aveva pianificato, avrebbe avuto molta più memoria di tutti gli altri primi computer, oltre ad essere più veloce.

Tuttavia, i suoi colleghi della NPL ritennero che l’ingegneria fosse troppo difficile da tentare e fu costruita una macchina molto più piccola, il Pilot Model ACE (1950).

NPL perse la corsa per costruire il primo computer digitale a programma memorizzato elettronico funzionante al mondo – un onore che andò al Royal Society Computing Machine Laboratory dell’Università di Manchester nel giugno 1948.

Scoraggiato dai ritardi di NPL, Turing assunse la carica di vicedirettore del Computing Machine Laboratory in quell’anno.
Dopo l’arrivo di Turing a Manchester, i suoi principali contributi allo sviluppo del computer furono la progettazione di un sistema di input-output, utilizzando la tecnologia di Bletchley Park, e la progettazione del suo sistema di programmazione.

Ha anche scritto il primo manuale di programmazione e il suo sistema è stato utilizzato nel Ferranti Mark I, il primo calcolatore elettronico digitale commercializzabile (1951).

Pioniere dell'Intelligenza Artificiale

Turing è stato uno dei padri fondatori dell’intelligenza artificiale e della moderna scienza cognitiva, nonché uno dei primi esponenti dell’ipotesi che il cervello umano sia in gran parte una macchina informatica digitale. Ha teorizzato che la corteccia alla nascita è una “macchina non organizzata” che attraverso “l’allenamento” si organizza “in una macchina universale”. Turing propose quello che in seguito divenne noto come il “test di Turing” come criterio per stabilire se un computer artificiale sta pensando (1950).

Gli Ultimi Anni

Turing fu eletto membro della Royal Society di Londra nel marzo 1951.

Nel marzo 1952 fu condannato per “gravi atti osceni” – vale a dire, l’omosessualità, un crimine in Gran Bretagna a quel tempo – e fu condannato a 12 mesi di “terapia” ormonale.

Con dei precedenti penali, non sarebbe mai più stato in grado di lavorare per il Government Communications Headquarters (GCHQ), il centro di decodifica del dopoguerra del governo britannico.

Turing trascorse il resto della sua breve ma monumentale carriera a Manchester, dove nel maggio 1953 fu assegnato a un gruppo di lettori creato appositamente per la teoria dell’informatica.

Dal 1951 Turing aveva lavorato su quella che oggi è conosciuta come “vita artificiale”.

Ha pubblicato “The Chemical Basis of Morphogenesis” nel 1952, descrivendo aspetti della sua ricerca sullo sviluppo della forma e del modello negli organismi viventi.

Turing ha utilizzato il computer Ferranti Mark I di Manchester per modellare il suo ipotetico meccanismo chimico per la generazione della struttura anatomica negli animali e nelle piante.

Nel bel mezzo di questo lavoro pionieristico, Turing fu scoperto morto nel suo letto, avvelenato dal cianuro.
Il verdetto ufficiale fu suicidio, ma nessun movente fu stabilito all’inchiesta del 1954.

La sua morte è spesso attribuita al “trattamento” ormonale che ha ricevuto per mano delle autorità dopo il suo processo per la sua omosessualità.

Eppure morì più di un anno dopo che le dosi ormonali erano terminate e, in ogni caso, il resiliente Turing aveva sopportato quel trattamento crudele con quella che il suo caro amico Peter Hilton chiamava “noncuranza”.

Inoltre, a giudicare dai verbali dell’inchiesta, non è stata presentata alcuna prova per indicare che Turing intendesse togliersi la vita, né che l’equilibrio della sua mente fosse disturbato (come sosteneva il coroner).

In effetti, il suo stato mentale sembra essere stato irrilevante in quel momento.

Sebbene non si possa escludere il suicidio, è anche possibile che la sua morte sia stata semplicemente un incidente, il risultato dell’inalazione di fumi di cianuro da un esperimento nel piccolo laboratorio adiacente alla sua camera da letto.

Non si può nemmeno del tutto escludere l’omicidio da parte dei servizi segreti britannici o alleati, dato che Turing possedeva una conoscenza sterminata in termini di crittoanalisi, in un’epoca dominata dalla paranoia dettata dall’incombente Guerra Fredda.