SCIENZA&STORIA/ Alan Mathinson Turing: nel centenario della nascita

- Paolo Borghese

Nel 1912 nasceva Alan Mathinson Turing, inventore della famosa macchina universale. Libertà, pragmatismo, originalità scientifica sono caratteri peculiari di questo protagonista del passato.

Borghese_00_aperturabis_439x302_ok
ACE (Automatic Computer Engine) 1950 Pilot, il prototipo della macchina di Turing esposto dal 1958 nella galleria principale dello Science Museum di Londra.

Il 23 giugno 1912 nacque a Londra Alan Mathinson Turing, uno dei più geniali scienziati del secolo scorso, la cui opera in diversi campi dalla matematica, alla logica e alla filosofia ha prodotto contributi significativi e decisivi per la società.
Quando morì il 7 giugno 1954 a Wilmslow in circostanze drammatiche, quasi sicuramente suicida, anche se non fu abbandonata l’ipotesi di assassinio o comunque di pressioni a cui fu sottoposto forse a causa del suo lavoro sulle comunicazioni segrete, il mondo era diventato totalmente differente da quello esistente al suo esordio.
L’autore ne tratteggia un ritratto in cui libertà e pragmatismo, tipici del suo carattere, si intrecciano con l’ originalità in campo scientifico, in particolare «la capacità di costruire immagini concrete di concetti astratti».

La vita breve quanto intensa di Turing non manca di attrarre e affascinare sia gli esperti sia un pubblico più vasto di cultori appassionati.
Il suo comportamento talvolta eccentrico era, credo, dovuto anche al carattere giocoso e particolarmente libero da ogni costrizione, ma altrettanto determinato. [Immagine a sinistra: Alan M. Turing (1912-1954; qui all’arrivo di una maratone nel 1946]
L’estrema capacità di concentrazione e indipendenza di giudizio gli permisero di formarsi e sopravvivere senza troppi danni già a partire dai primi impatti con una scuola pubblica il cui obiettivo dichiarato, in Inghilterra come del resto nel mondo occidentale di quegli anni, era essenzialmente di «educazione».
La sua straordinaria e geniale intelligenza lo portò a dedicarsi a problemi sempre nuovi e di confine mai affrontati prima, o meglio si può dire che i confini di cui noi sentiamo la necessità per circoscrivere e studiare una disciplina per Turing non esistevano affatto, perché li superava con leggerezza e originalità. A mio parere, fra i suoi contemporanei solo il russo Pavel Florenskij possedeva simili capacità.
In questo articolo più che fornire informazioni complete sulla vita e sulle opere di Turing, per le quali rinvio gli interessati alla bibliografia riportata in appendice, mi pongo l’obiettivo di cogliere nella sua ricerca l’aspetto che mi ha più colpito, cioè la sua capacità di costruire immagini concrete di concetti astratti. Il dispiegarsi nella pratica del suo pensiero ha portato all’attuale e pervasivo mondo dell’informatica e della scienza dei computer. Il mondo «digitale», che è per le giovani generazioni niente più che un dato di fatto, esiste nella sua forma attuale anche grazie all’opera di Turing, non solo di studio teorico delle macchine, ma anche di progettazione effettiva dei calcolatori reali.

Entscheidungsproblem – il problema della decidibilità

La ricerca matematica era, nei primi decenni del secolo XX, dominata dalla figura di David Hilbert, scienziato di grande versatilità, autore di notevoli risultati in molteplici campi della matematica e della fisica.
La sua competenza era tanto ampia e profonda da portarlo alla convinzione che la scienza matematica sia da considerarsi come un tutto indivisibile, un organismo la cui vitalità è condizionata dalla interconnessione delle sue parti. [Immagine a sinistra: David Hilbert (1862-1943)]
La scuola di Gottinga diventa, anche grazie alla sua presenza, il centro principale della matematica mondiale dalla fine del XIX secolo per oltre trent’anni fino all’avvento al potere dei nazisti. L’esilio a cui furono allora costretti i più brillanti esponenti della scuola ebbe effetti devastanti a tal punto che si narra di come Hilbert, al gerarca che gli chiedeva quale fosse lo stato della ricerca, diede con amarezza la risposta: «la matematica a Gottinga non esiste più».
Al congresso internazionale tenuto a Parigi nel 1900 Hilbert presentò una lista di problemi che divenne celebre presso i matematici in quanto considerata un piano di lavoro che orientò le generazioni future per i decenni a venire. Alcuni dei ventitre problemi, come la cosiddetta ipotesi di Riemann sugli zeri della funzione z, sono tuttora aperti.

Ipotesi di Riemann

La congettura di Riemann afferma che gli zeri non banali della funzione hanno, nel piano complesso, parte reale pari a ½. La sua dimostrazione avrebbe importanti conseguenze nella teoria dei numeri primi; anche se buona parte dei matematici la ritiene vera, non è stata (ancora) dimostrata.

Fra gli altri problemi, il X riguarda le equazioni diofantee (da Diofanto di Alessandria, matematico greco del III secolo), equazioni in una o più incognite a coefficienti interi di cui si ricercano soluzioni intere. Tale problema fu a lungo trascurato anche per la sua formulazione un po’ enigmatica; si chiedeva infatti di «dare un procedimento col quale poter decidere, mediante un numero finito di operazioni, se l’equazione è risolubile in numeri razionali interi».

La questione fu infine risolta nel 1970 in termini negativi, ma poté essere formulata in modo più preciso e generale solo quando la teoria degli algoritmi, sviluppata negli anni Trenta da Alonzo Church e Alan Turing, permise di studiare la logica dei processi ricorsivi.
In questo campo di ricerca la principale difficoltà che si incontra riguarda la necessità di fornire una definizione corretta e inattaccabile a espressioni come: «metodo» e «procedura effettiva». Su queste idee Turing lavorò a lungo fino al 1936, come di consueto in modo isolato e indipendente, fino alla formulazione del suo metodo innovativo il cui punto fondamentale consiste nella riduzione del processo di deduzione del risultato a una serie di operazioni atomiche così elementari da poter essere meccanizzate. Se si raggiunge il risultato attraverso un numero finito di passi vuol dire che esso è «computabile». In [1] Turing, dopo aver definito i numeri computabili e aver mostrato come gli stessi concetti si applichino a enti più complessi (funzioni, predicati e così via), passa a dimostrare la possibilità teorica di una macchina universale di computazione.

 

Incompletezza dei sistemi formali

Il X problema si trasformò negli anni, tanto da non essere più riconoscibile nella formulazione originaria, in quello della «decidibilità» delle proposizioni di un sistema formale; nelle parole di Hilbert: «qualsiasi problema ben posto può essere risolto o riuscendo a dare la risposta alla questione posta o mostrando l’impossibilità di una soluzione, quindi la necessità dell’insuccesso di ogni tentativo».
Un sistema formale si dice «completo» se ogni proposizione esprimibile coi suoi simboli risulta formalmente «decidibile«» a partire dagli assiomi, cioè per ogni proposizione A esiste una catena finita di inferenze che, iniziando con alcuni assiomi e sviluppandosi secondo le regole del calcolo logico, termina con la proposizione A o con la proposizione NON A.
Un sistema formale si dice «coerente» se non può essere dimostrato nulla di contraddittorio, cioè se non è possibile dedurre un teorema che contraddice un altro teorema o un postulato. Ora si dà il caso che la proposizione che esprime la coerenza del sistema sia una di quelle «indecidibili» nel sistema stesso. In altre parole, si può ottenere una dimostrazione di coerenza per un sistema S solo facendo ricorso a mezzi di inferenza che non sono formalizzabili in S stesso.
Perciò siamo costretti a ricorrere a un meta-sistema i cui elementi formali siano le proposizioni di S, ma così facendo dovremmo ricorrere a un meta-meta-sistema e, da questa catena ricorsiva infinita, non esiste via d’uscita che ci permetta di tornare al punto di partenza.

Nel 1931 Gödel dimostrò l’incompletezza di ogni sistema formale abbastanza ricco da contenere l’aritmetica, dando così una risposta negativa all’ipotesi formulata da Hilbert. [Immagine a destra: Kurt Gödel (1906-1978) e Albert Einstein (1879-1955)]
Questa dimostrazione segna un momento rivoluzionario nella logica matematica ma soprattutto nella filosofia, cioè nel modo di percepire i rapporti tra matematica e realtà empirica e occupa un posto paragonabile a quello della relatività di Einstein nella fisica. Con però una differenza importante: l’opera di Gödel, seppure centrale per i fondamenti della matematica e ormai entrata a far parte della cultura corrente, non ha avuto una grande influenza sulla pratica della matematica.

 

 

 

La macchina universale di Turing

 

Il mondo delle macchine, cioè dei manufatti che forniscono in modo autonomo un prodotto fruibile, non mai ha cessato di affascinare il genere umano, tanto più se i prodotti sono caratterizzati da aspetti simbolici invece che materiali come le informazioni.
L’idea di una macchina calcolatrice è nata nel Seicento, ma solo nel secolo XIX Charles Babbage, pittoresco personaggio londinese, concepì un progetto rivoluzionario, la Macchina Analitica, che purtroppo non fu mai costruita per mancanza di tempo e risorse con irrimediabile delusione del suo inventore. [Immagine a sinistra: Charles Babbage (1791-1871)]
Essa era controllata da un programma contenuto in schede perforate, soluzione questa, ispirata dal famoso telaio Jacquard che era in grado di tessere disegni molto complessi sotto il controllo di schede. [Immagine a destra: Modello della macchina di Babbage]
La Macchina universale di Turing trae invece ispirazione dalla telescrivente della quale è una versione più estesa; infatti è costituita da un nastro suddiviso in cellette che può muoversi indefinitamente di una casella alla volta in entrambe le direzioni e da un dispositivo che può leggere, cancellare o scrivere un nuovo simbolo, piuttosto che scrivere soltanto un simbolo in modo indelebile. È chiaro che vi è un’infinità di macchine di Turing, ciascuna corrispondente a una differente procedura o metodo di calcolo in base a una diversa «tabella di comportamento» che, in termini moderni, è impossibile non identificare con un programma di computer.

L’analisi di Turing non riguardava il computer che ancora non esisteva, ma si concentrò sul generale processo meccanico di passi consecutivi percorso da un essere umano, mentre esegue un effettivo processo seguendo un insieme fissato di regole (algoritmo), interpretabile senza ambiguità, per raggiungere la soluzione. Non è difficile immaginare una procedura per risolvere un problema aritmetico come eseguire un’addizione, ma in modo analogo si può pensare di affrontare anche problemi non numerici, basta infatti associare ai simboli un diverso significato.
Il risultato fondamentale di Turing è che, per tutto quanto è computabile sia esso un numero o un simbolo, esiste una «macchina», cioè un processo meccanico, che effettivamente lo calcola. Data allora una proposizione matematica formalmente corretta, ci si chiede se esista un metodo per decidere se sia o non sia dimostrabile. Se il metodo esiste allora si può costruire una MT che «calcoli» la decisione. Si può dimostrare formalmente che la definizione di computabilità di Turing, applicata al problema della decidibilità, coincide con le definizioni date da Church e da Gödel ma ha, rispetto a queste, il pregio di essere anche intuitiva.

 

Una descrizione più formale della Macchina di Turing

Una Macchina di Turing (MT) è un dispositivo costituito da:

  1. una unità di controllo che contiene un programma finito;

  2. un nastro potenzialmente infinito diviso in cellette;

  3. una testina che, seguendo le istruzioni contenute nell’unità di controllo, può leggere e scrivere simboli nelle caselle e spostare il nastro a destra o a sinistra.

Alla partenza da una posizione prescelta (per esempio dalla cella non vuota più a sinistra) l’unità di controllo contiene il programma e il nastro contiene un insieme finito di simboli appartenenti a un alfabeto finito. Lo stato della macchina, cioè l’istruzione eseguita e il simbolo letto, determinano il nuovo simbolo da scrivere, il movimento del nastro e la prossima istruzione da eseguire. Se e quando la macchina si ferma, sul nastro si legge il risultato, che è un insieme di simboli dell’alfabeto.
Ora, dato un algoritmo A, codificato dal suo programma, e un numero n, scritto sul nastro in un codice opportuno, se la macchina si arresta il suo risultato è interpretato come fA (n).
Nonostante la potenza del concetto di procedura effettiva, molti problemi sono indecidibili, in particolare non esiste una procedura effettiva per stabilire se un algoritmo
A prima o poi si arresti se viene avviato su un nastro arbitrario.

 

Seguendo Turing chiamiamo allora numero computabile un numero reale (considerato come un decimale infinito) per il quale esista una MT che lo calcoli. Le MT sono numerabili, perciò possono essere ordinate assegnando ad esse un numero identificativo crescente. I numeri identificativi delle MT che calcolano numeri computabili sono detti soddisfacenti. Con il tradizionale metodo della diagonale usato da Cantor si può dimostrare che non esiste una MT in grado di decidere se un numero è o non è soddisfacente, cioè se la macchina corrispondente calcola un numero computabile.

 

Metodo della «diagonale»

Il prototipo è la dimostrazione tanto semplice quanto elegante di Cantor, della non numerabilità dei numeri reali che voglio riassumere in poche righe.
Partiamo dall’ipotesi che i numeri reali compresi fra 0 e 1 siano numerabili, possiamo allora elencarli uno di seguito all’altro. Immaginiamo in questo modo di riempire un foglio di larghezza e lunghezza infinita, perché sia le cifre della rappresentazione decimale sia i numeri sono infiniti.
Ora, spostandoci di una riga alla volta costruiamo un nuovo numero che nella posizione corrispondente a quella della diagonale principale ha un valore decimale diverso da quello che leggiamo in questa.
Così proseguendo un passo alla volta costruiamo un numero che non può avere un corrispondente nella tabella iniziale, perciò l’ipotesi da cui siamo partiti è falsa.

 

Infatti, supponiamo che esista una MT in grado di decidere se l’identificativo di ogni altra macchina è soddisfacente, allora possiamo costruire una nuova MT con il seguente comportamento: essa cambia il contenuto della N-sima posizione del numero computato dalla macchina di numero soddisfacente N. Così mentre la macchina procede costruisce effettivamente un numero reale computabile che deve essere per costruzione diverso da tutti quelli computati da macchine identificate da numeri soddisfacenti. La nostra macchina dovrebbe allora avere un identificativo soddisfacente e contemporaneamente non averlo perché non appartiene all’elenco; questa contraddizione falsifica l’ipotesi che la macchina in grado di decidere possa essere costruita.
Un algoritmo e il programma che lo realizza hanno dimensione finita anche se il risultato dell’esecuzione è potenzialmente infinito; si pensi per esempio all’algoritmo per calcolare il numero e che, racchiuso in poche istruzioni, produce il risultato con la voluta approssimazione.

Dato un numero reale, la successione delle sue cifre può apparire caotica, ma celare una certa regolarità che sarebbe perciò incapsulabile in un programma finito oppure, ed è vero per la maggior parte dei numeri, il programma dovrebbe essere necessariamente infinito per contenere in modo esplicito il numero stesso.
Turing ha aperto nuove aree di esplorazione sulle questioni riguardanti la decidibilità, in particolare sul problema dell’arresto di un programma. Anche se nella pratica si affrontano problemi generalmente computabili, non c’è modo di escludere a priori la possibilità che un algoritmo non si arresti per qualche valore dei dati di ingresso; non esiste infatti per tutti i programmi un limite superiore per il numero di istruzioni che possono eseguire. La non decidibilità della terminazione, ovvero la sua non computabilità, è un altro punto di vista dell’incompletezza dell’aritmetica.

 

 

Il test di Turing

 

Nel suo articolo più famoso [2], pubblicato su Mind nel 1950, Turing affronta un problema centrale che è tuttora oggetto di ricerca sia nelle scienze cognitive sia nell’Intelligenza Artificiale: quello della macchina che mostra un comportamento intelligente.
Non possiamo sottrarci alla domanda posta in apertura: «può una macchina pensare?» che procura in chi la formula una certa sensazione di vertigine. In altri termini come può l’intelligenza nascere da un processo disciplinato fatto da operazioni elementari ripetitive eseguite meccanicamente? Del resto anche gli esseri biologici, che evitiamo di chiamare «macchine» data la connotazione artificiale che diamo generalmente a questo termine, presentano aspetti analoghi; si pensi per esempio ai meccanismi elementari e ai processi cellulari del cervello di per sé privi di intelligenza, ma che sono all’origine dell’organizzazione simbolica cognitiva.
Animali «semplici» quali l’aplysia (lumaca di mare studiata da Eric R. Kandel, premio Nobel nel 2000 per la medicina) possiedono una corrispondenza neurone-funzione, che li rende adeguati per uno studio dei processi elementari che si ritrovano anche in organismi più evoluti. Come poi tali processi si organizzino per produrre la creatività del pensiero umano è un altro discorso che ovviamente non tocchiamo.
Se è possibile produrre un’intelligenza aggregando processi elementari si può in teoria costruirla anche partendo da un substrato hardware non necessariamente biologico, del resto alcuni passi sono stati compiuti, per esempio con macchine che, benché specializzate e prive di coscienza e sensibilità affettiva, emulano processi mentali e sono in grado di giocare partite a scacchi da campioni.
L’approccio di Turing al problema dell’intelligenza è ancora una volta concreto e pragmatico anche se, visto a distanza di tempo, può forse contenere qualche ingenuità che non diminuisce però la fondatezza del suo punto di vista (per un’analisi dettagliata vedi per esempio [3]).
A molti anni dalla sua stesura, la leggerezza e profondità dell’articolo lo lasciano leggere ancora con diletto, tanto che me lo immagino recitato come dialogo in teatro. Che io sappia finora è solo la vita di Turing, soprattutto riletta attraverso il racconto della madre, che è stata trasposta in spettacolo. Turing evita di affrontare in modo analitico discussioni sulla natura del pensiero, della mente e della coscienza dando invece un criterio in termini esterni. La sua giustificazione è che uno giudica che gli altri esseri umani pensano in base a osservazioni esterne, se perciò un essere umano e un computer competono per convincere un giudice imparziale, usando solo messaggi testuali, su chi sia l’essere umano e se il computer risulta vincitore, allora gli si deve accreditare una forma di intelligenza.

 

Turing stesso introduce il problema

Il problema si può descrivere nei termini di un gioco che chiameremo «gioco di imitazione».
Vi partecipano tre personaggi: un uomo (A), una donna (B) e un intervistatore (C) che può essere di uno qualunque dei due sessi.
L’intervistatore si trova in un’abitazione separata da quella in cui risiedono le altre due persone. Lo scopo del gioco da parte dell’intervistatore è di determinare chi degli altri due personaggi è l’uomo e chi è la donna.
L’intervistatore li identifica con i simboli X e Y e alla fine del gioco dovrà dire «X è A e Y è B» oppure «X è B e Y è A».

Il nostro autore, ben conscio della tempesta di opposizioni che avrebbe sollevato, analizza in modo dettagliato e ironico le obiezioni all’idea che le macchine possano pensare. L’intento del gioco di imitazione, è sicuramente provocatorio dato che è relativamente ingenuo anche perché limitato da assunzioni sul linguaggio e cultura e perché ignora il pensiero animale o extra-terrestre non riconducibile a comunicazione verbale.
È inoltre curioso il fatto che l’articolo apparve in una rivista di filosofia: Turing non era un filosofo ma essenzialmente un matematico che volle offrire alla filosofia una riflessione illuminante su un nuovo campo di ricerca in cui si era avventurato fra i primi.

 

 

Conclusioni

 

L’eredità di Turing è molto più vasta di quanto possa sembrare da quanto detto sopra, in particolare le sue competenze (oltre che sui sistemi non lineari) di chimica e biologia gli permisero di affrontare la morfogenesi [4] cioè i meccanismi che possono determinare la struttura anatomica di un organismo vivente.
Sistemi originariamente omogenei possono sviluppare una determinata struttura partendo da una instabilità dell’equilibrio che può sorgere a causa di disturbi casuali. Tali meccanismi sono molto complessi e hanno richiamato l’attenzione dei ricercatori solo decenni dopo il lavoro seminale di Turing pubblicato nel 1952. [Immagine a destra: Memorial Alan Turing a Manchester]
Sappiamo, solo indirettamente perché non esistono suoi scritti, che nell’ultimo periodo di vita, le riflessioni di Turing avevano come oggetto la Meccanica Quantistica, altro campo delle sue competenze nel quale si muoveva con disinvoltura. Ma noi posteri possiamo solo avere qualche suggestiva idea del tipo: si prefigurava forse un computer quantico o pensava a una forma di incomputabilità del processo di riduzione della teoria dei quanti che possa anche influenzare le azioni mentali? Qui però entriamo in un campo che può essere solo soggettivo.
Alan Turing appartiene secondo me a quella esigua schiera di Grandi del passato che sono fonte inesauribile di ispirazione per il futuro, nel senso che possiamo continuare a discutere con loro nella nostra mente e trarre qualche indicazione dalle loro immaginarie risposte.

 

 

Vai al PDF dell’articolo

 

 

Paolo Borghese
(Docente di Informatica presso la Facoltà di Ingegneria dell’Università degli Studi di Bergamo)

 

Indicazioni Bibliografiche

  1. A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Maths. Soc., ser. 2, 42: 230-265.

  2. A. M. Turing, Computing machinery and intelligence, Mind, 50: 433-460.

  3. G. O. Longo, Il test di Turing, storia e significato, Mondo Digitale, 29: 11-24.

  4. A. M. Turing, The Chemical Basis of Morphogenesis, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, Vol. 237, No. 641. (Aug. 14, 1952), pp. 37-72.

 

Indicazioni Sitografiche

  1. www.turing.org.uk/turing/: Guida al sito web dedicato a Alan Turing (1912-1954)

  2. http://plato.stanford.edu/entries/turing/: Qui si trova anche una approfondita bibliografia

  3. www.abelard.org/turpap2/tp2-ie.asp

  4. http://en.wikipedia.org/wiki/Turing_test

  5. http://en.wikipedia.org/wiki/Alan_Turing

  6. www.torinoscienza.it/personaggi/alan_turing_19826

  7. www.nemesi.net/turing.htm

 

 

Libri

  1. UK paperback: Alan Turing: the Enigma, ISBN 0-09-911641-3 (Vintage, Random House, London.). Translation into Italian by David Mezzacapa, Storia di un Enigma, Bollati Boringhieri, Torino 1983 (Premio Giovanni Comisso, nel 1992).

  2. D. R. Hofstadter, Gödel, Escher, Bach – Un’eterna ghirlanda brillante, Adelphi, Milano 1992. In questo libro si parla anche di Turing; ne raccomando la lettura in quanto lo considero una brillante e moderna introduzione ai problemi del pensiero e quindi anche alla lettura delle opere originali di Turing.

 

 

 

 

© Pubblicato sul n° 45 di Emmeciquadro




© RIPRODUZIONE RISERVATA

I commenti dei lettori