venerdì 9 marzo 2012

Caffè Filosofico. Godel e Turing. La nascita del computer e la società dell'informazione




Il 9 maggio 1941 è stato un giorno di svolta all'interno del secondo conflitto mondiale, corrisponde infatti alla data in cui fu catturato dagli inglesi il sottomarino tedesco U-boot U-110. A bordo del mezzo fu trovato uno strano macchinario, soprannominato Enigma, che riceveva regolarmente messaggi criptati da parte dell'esercito tedesco; la decodificazione delle serie numeriche (che cambiava ogni 24 ore circa) tenne impegnate per molto tempo in un progetto segreto le menti più brillanti del Regno Unito, tra cui quella del tormentato matematico Turing.
Il team riuscì a scoprire i segreti dei nemici individuando una falla nel loro sistema, ogni messaggio infatti cominciava con delle informazioni sul meteo e si chiudeva con un saluto formale a Hitler; proprio questi furono allora i punti di partenza per la scoperta di come i codici funzionavano.






Alan Turing e la sua macchina
Turing è definito il padre dell'intelligenza artificiale, in base soprattutto alla teorizzazione dell'omonima macchina. Che cos'è la macchina di Turing e perché è così importante? [...]

Ciò che ha reso la figura di Turing un soggetto perfetto da romanzare è l'intrecciarsi di una vita personale travagliata, un ruolo decisivo nell'esito della Seconda guerra mondiale e le teorie pionieristiche in materia di calcolo digitale.

IL NUOVO TESTAMENTO DELL'ERA DIGITALE. 
Proprio grazie a queste teorie Turing è considerato da molti il padre dell'informatica. Non è del tutto sbagliato definirlo così, perché, per dirla con le parole di George Dyson nel suo saggio La cattedrale di Turing (Codice Edizioni), Alan Turing si colloca fra il Vecchio e il Nuovo Testamento dei profeti del calcolo digitale. Funge cioè da spartiacque tra coloro che hanno fornito la logica (Leibniz in testa) e coloro che hanno poi costruito le macchine (John Von Neumann).

LA MACCHINA DI TURING. Il lavoro più noto di Turing è On Computable Numbers del 1936, nel quale il matematico presenta la sua macchina di calcolo logico, poi definita macchina di Turing. 
«Una macchina di Turing», spiega Carlo Cellucci, professore emerito di filosofia alla Sapienza di Roma, «non è una macchina fisica ma un modello di una macchina ideale consistente in: A) un nastro infinito in entrambe le direzioni, diviso in caselle ciascuna delle quali può contenere il simbolo 0 oppure il simbolo 1. Il nastro rappresenta la memoria della macchina; B) una testina che può leggere il simbolo, 0 oppure 1, contenuto in una casella e scrivere un simbolo in una casella, e può muoversi lungo il nastro, una casella per volta.»
Si tratta soltanto di un modello teorico, poiché prevede un tempo e uno spazio (cioè il nastro) infiniti. Per farvi un'idea però qui sotto potete vederne un prototipo realizzato da Mike Davey e utilizzato nell'introduzione del film The Imitation Game:


Secondo Turing sarebbe stato possibile inventare una macchina che potesse essere utilizzata per qualsiasi sequenza computabile. La novità di questa teoria, secondo Dyson, è che si dimostrava che una macchina poteva essere codificata come un numero e viceversa, introducendo il concetto di ciò che oggi chiameremmo software.

TURING "PADRE" DEL COMPUTER? 
Chi conosce o ha sentito parlare del matematico inglese lo definisce spesso così. 
Turing sicuramente «stimolò il progetto di realizzazione di un computer», conferma il professor Cellucci, «ma i computer reali non si basano sul suo modello perché sarebbero estremamente lenti e inefficienti. I computer reali si basano invece su un modello ideato da un altro logico, John von Neumann». Quest'ultimo tra l'altro conobbe Turing all'università di Princeton e dopo il dottorato gli propose un posto come suo assistente. Il matematico rifiutò l'offerta e fece ritorno in Inghilterra, dove partecipò al programma di decrittazione dei codici con i quali i tedeschi comunicavano ai sommergibili gli obiettivi militari da colpire, il famoso sistema Enigma. John Von Neuman invece, nel 1953, realizzò con un gruppo di fisici e ingegneri il primo calcolatore programmabile.

TURING VISIONARIO? 
Secondo Cellucci «Turing è stato un visionario nel senso che immaginò un modello di macchina capace di effettuare calcoli di ogni genere, ed immaginò macchine intelligenti dotate di capacità superiori a quelle dei computer attuali. Come tanti visionari, però, Turing era più a suo agio con i sogni che con la realtà. Infatti, quando si passò alla realizzazione dei primi computer reali, il suo contributo non fu di primo piano».

È certo però che a soli 24 anni scrisse uno dei trattati più brillanti e innovativi della sua epoca, influendo sugli studi di chi poi avrebbe effettivamente realizzato la "macchina universale".








Piergiorgio Odifreddi racconta
Godel e Turing. La nascita del computer e la società dell'informazione


Pag. 20
Se la frase fosse dimostrabile, poiché il sistema dimostra solo cose vere, sarebbe vera. Ma essa dice “io non sono dimostrabile”, e allora non dovrebbe essere dimostrabile. L’ipotesi che questa frase sia dimostrabile fa sì che essa sia vera, e dunque non dimostrabile. Ma allora, l’ipotesi è sbagliata, e la frase non può essere dimostrabile; ma questo è appunto ciò che essa dice, e dunque è vera.
Sembra un gioco di prestigio, sul quale naturalmente vi invito a riflettere, a meditare. Perché, detta così, sembra semplicemente un gioco di parole, e non la dimostrazione di un teorema. Vi invito, cioè, a meditare sul fatto che la frase «io non sono dimostrabile» non può essere dimostrabile in un sistema che dimostra solo verità, perché altrimenti sarebbe falsa. E allora non è dimostrabile, ma poiché dice appunto di non essere dimostrabile, è vera.
E allora, che cosa abbiamo trovato? Abbiamo un'affermazione che è vera, ma non dimostrabile: dunque un esempio di incompletezza del sistema. Ora, come mai questo non è vero già per la logica, ma solo per la matematica? Perché il succo, il nucleo della dimostrazione di Godel consiste nel far vedere che questa frase, che dice di se stessa di non essere dimostrabile, si può rendere precisa, ma soltanto trascrivendola in linguaggio matematico, attraverso un meccanismo che si chiama oggi «godelizzazione», per ovvi motivi.
La godelizzazione è un modo per trascrivere frasi del linguaggio in formule aritmetiche, e dunque matematiche. Ed è così che questo ragionamento linguistico e filosofico, che assomigliava molto ai vecchi paradossi da una parte e ai ragionamenti di Kant dall'altra, diventa un ragionamento matematico. Però, per poter fare la trascrizione, c'è bisogno di avere almeno i numeri nel proprio sistema. Non lo si può fare nella sola logica, che è troppo debole. Ma questa debolezza risulta essere una forza, perché diventa la difesa contro l ‘incompletezza: è per questo motivo, che Godel ha potuto dimostrare nel 1930 il teorema di completezza per la logica.
Ma non appena c'è un minimo di matematica, non appena c'è un pò dell'aritmetica dei numeri dentro il sistema, allora si può riprodurre questo nuovo teorema di Godel del 1931, ed ecco che la matematica risulta invece essere incompleta. Abbiamo quindi, da una parte, la completezza della logica, e dall'altra parte, l'incompletezza della matematica.
Una drammatica vicenda
Sono sicuro che dopo aver sentito questo abbozzo di dimostrazione del teorema di Godel, la maggior parte di voi avrà la testa che gira. Questo è ciò che succede sempre, agli inizi, non appena si vedono i paradossi in generale, ma soprattutto questi «quasi sofismi» matematici in particolare. Ma non bisogna spaventarsi, ovviamente: sono cose sottili, complesse, complicate, sulle quali bisogna meditare.
E colui che ci meditò nella maniera più approfondita fu un giovane inglese che si chiamava Alan Turing. Nel 1936, quindi pochi anni dopo la dimostrazione del teorema di Godel, Turing dovette scrivere la sua tesi di laurea: aveva solo ventiquattro anni, e questo dimostra che la matematica è effettivamente, come disse una volta Godfrey Hardy, uno «sport da giovani».
Alan Turing cercò di capire quello che Godei aveva fatto, e per farlo scrisse una tesi che divenne il fondamento di quello che stiamo cercando di raccontare: la storia dell’informatica moderna. Turing è un personaggio meraviglioso, un personaggio sul quale è addirittura stato fatto un film, Enigma, che racconta una piccola parte della sua vita. La storia risale ai primi anni Quaranta, durante i quali Turing fu a capo di un laboratorio a Bletchley cui si riuscirono a decifrare i codici segreti nazisti. Questi codici erano ottenuti attraverso una macchina che si chiamava, appunto, Enigma. E il film racconta la storia dell'Enigma, di questa macchina a rotori che il team guidato da Turing riuscì a decodificare. E questa decodifica diede agli inglesi e agli alleati un vantaggio essenziale nel corso della guerra. Turing ebbe una fine piuttosto tragica, a soli quarantadue anni. Era omosessuale, in un periodo in cui erra l'omosessualità era proibita, anche fra adulti consenzienti. Nei primi anni Cinquanta, una sera egli rimorchiò un ragazzino, se lo portò a casa, e la mattina dopo scoprì che il ragazzino gli aveva rubato dei soprammobili in casa. Turing, molto ingenuamente, andò a denunciare il furto, e disse che credeva che a commetterlo fosse stato il ragazzino che aveva rimorchiato. Così confessò lui stesso un crimine, e fu arrestato, processato e condannato. Ma essendo un eroe di guerra, anche se all'epoca la cosa non era ancora di dominio pubblico, il governo permise al tribunale di offrirgli un'alternativa. Invece di una pena detentiva, gli fu offerta una cura di ormoni femminili, che Turing accettò di fare, ma che gli fece, tra l’altro, crescere il seno e cadere la barba. E lui, a un certo punto, decise che ne aveva abbastanza dell'Inghilterra e dei suoi pregiudizi, e si suicidò.
Però era molto legato alla madre. E non v olendo che lei venisse a sapere, o potesse pensare, che lui si era suicidato, scelse una via molto strana. Decise di fare come Biancaneve: intinse una mela nel veleno, e la mangiò. Fece quindi apparire il suo suicidio come un incidente. Ed è proprio questa mela a cui manca un morso, che è oggi diventata il simbolo della Apple: la si vede su tutti i gadget della Apple, e ricorda il morso che ha provocato la morte di Turing.
La macchina di Turing
Che cosa fece questo personaggio singolare, che risponde al nome di Alan Turing, per meritarsi un posto nella storia dell'informatica, ed essere ricordato obliquamente nel simbolo di una delle maggiori aziende di computer?
Abbiamo accennato al fatto che Turing si mise a studiare il teorema di Godel, il teorema di incompletezza della matematica, e cercò di capirlo a modo suo. Questo teorema parlava di sistemi matematici, e quindi di formule, assiomi, regole di deduzione ecc.: tutte cose molto poco intuitive, allora come ora. Turing cercò di riformulare il teorema di Godel in una forma più intuitiva, e lo fece inventandosi un particolare tipo di macchina.
Egli iniziò chiedendosi come sarebbe possibile descrivere una macchina in grado di fare dei calcoli, e per la quale valesse un analogo del teorema di Godel. E così facendo arrivò semplicemente a fare sulla carta un progetto di quello che oggi noi chiamiamo «computer», ma che gli informatici chiamano «macchina di Turing universale».
TURING NOTÒ CHE QUANDO IN UN SISTEMA FORMALE SI PROCEDE DAGLI ASSIOMI MEDIANTE LE REGOLE, LO SI FA EFFETTIVAMENTE IN MANIERA MECCANICA: CIOÈ, L'UOMO CHE STA DERIVANDO DEI TEOREMI, STA LAVORANDO COME UNA MACCHINA. E che cosa dovrebbe saper fare una macchina, per essere in grado di simulare ciò che sta facendo l'uomo mentre esegue deduzioni meccaniche e formali?
Dovrebbe, anzitutto, avere qualche cosa su cui scrivere, e con cui scrivere. E allora Turing decise che la sua macchina doveva avere una testina in grado di stampare delle lettere, o di cancellarle. Doveva avere un pezzo di carta, che lui si immaginò come un nastro infinito. E doveva saper compiere un certo numero di operazioni, quali saper leggere un simbolo, muovere la testina a destra o a sinistra lungo il nastro, cancellare, riscrivere altri simboli ecc.
Finora, una specie di macchina da scrivere sarebbe in grado di compiere operazioni simili. Ma la cosa fondamentale che Turing capì è che, oltre a questo armamentario che oggi noi chiameremmo hardware, cioè oltre alla macchina fisica, ci doveva essere qualche cosa che invece oggi noi chiamiamo software, cioè un programma.
Un programma è una serie di istruzioni che dicono alla macchina, che sta leggendo un simbolo e si trova in un certo stato interno, che cosa deve fare: per esempio, scrivere un altro simbolo, spostarsi a destra o a sinistra ecc. Le possibili azioni sono un numero finito, e un insieme finito di istruzioni di questo genere Turing lo chiamò appunto un programma.
L'osservazione fondamentale è che una macchina anche banale, come quella che abbiamo appena descritto, in grado soltanto di scrivere e leggere su un nastro un numero finito di simboli, e di trovarsi in un insieme finito di stati interni, è in grado di eseguire qualunque programma, e dunque di fare tutto ciò che fa un matematico quando calcola. Perché Turing capì che questi programmi, benché a prima vista rudimentali, erano in grado di descrivere qualunque operazione meccanica, qualunque funzione calcolabile, qualunque algoritmo informatico.
Ora, poiché questi programmi sono oggetti finiti, analoghi a un testo composto di frasi di un linguaggio, si possono mettere in ordine alfabetico: dunque, è possibile enumerarli, metterli in lista. E l'idea della macchina universale di Turing, alla quale arriveremo tra poco, è semplicemente questa: che l'hardware rimane fisso e costante, mentre a cambiare è il software, cioè il particolare programma che viene scelto dalla lista.
A questo punto, Turing cominciò a porsi delle domande di tipo metamatematico. A chiedersi, per esempio: «Siamo in grado, vedendo il programma, di capire se prima o poi si fermerà, su un dato input, oppure no?». Ed è riformulando appunto il ragionamento del teorema di Godel, che TURING RIUSCÌ A DIMOSTRARE CHE CI SONO DELLE ATTIVITÀ CHE UNA MACCHINA DI TURING NON È IN GRADO DI FARE.
Queste attività che una macchina di Turing non può compiere, sono limitazioni delle macchine, e costituiscono l'analogo delle limitazioni dei sistemi formali che Godel aveva dimostrato esistere per la matematica. E queste limitazioni, a loro volta, costituivano l'analogo delle limitazioni della ragion pura che Kant aveva individuato nella filosofìa.
Ci sono dunque tre tipi diversi di limitazioni: quelle della ragion pura di Kant, quelle dei sistemi matematici
Pag. 25
[…]
Pag. 32 
Godel e Turing. La nascita del computer e la società dell'informazione
il percorso che essa ha compiuto durante quel tempo. Poiché von Neumann diede immediatamente la risposta, gli dissero: «Ah! Conoscevi il trucco!». Ma lui rispose: «Che trucco? Ho semplicemente calcolato la serie infinita dei percorsi della mosca, avanti e indietro».
Si raccontano su di lui moltissimi altri aneddoti, ma che cosa fece veramente von Neumann per la storia dell'informatica? Nel 1945 entrò a lavorare a due prototipi di calcolatori elettronici che si stavano costruendo all'epoca: l'EDVAC e l'ENIAC. E portò con sé un enorme bagaglio tecnico, che tra le tante cose conteneva anche un bel po' di logica matematica.
Von Neumann era presente nel 1930, quando Godel aveva fatto l'annuncio dei suoi risultati a un famoso convegno, e li capì immediatamente. Nel giro di un paio di settimane, con la sua proverbiale velocità, disse addirittura a Godel come si potevano migliorare questi risultati.
Von Neumann aveva anche conosciuto Turing, quando questi era andato a studiare a Princeton per un paio d'anni, tra il 1936 e il 1938. Quindi von Neumann sapeva benissimo quale fosse il problema teorico che un computer doveva risolvereDoveva essere una macchina universale, cioè essere in grado di prendere dei programmi, decodificarli, simularli e restituire gli stessi output che questi programmi avrebbero restituito se avessero eseguito questi compiti individualmente. E l'implementazione di questi aspetti fu appunto il contributo fondamentale che egli diede all'informatica, con la cosiddetta «architettura di von Neumann»
Il computer fu dunque realizzato mettendo insieme due ingredienti. Da una parte, la scatola nera, realizzata attraverso l'algebra di Boole in astratto, e i circuiti elettrici, o le reti neurali, in concreto. E dall'altra parte, la programmabilità, grazie all'idea astratta di macchina universale di Turing, e l'implementazione concreta dell'architettura di von Neumann.
Nel 1945 nacque così il primo vero computer universale, che fu appunto l'ENIAC: in quel momento è nata l'informatica. Quello che è successo dopo è stato semplicemente un «mettere i puntini sulle i» di questa grande impresa intellettuale, che abbiamo raccontato partendo da Leibniz e arrivando fino a oggi.
Cosa non può fare un computer
Abbiamo dunque raccontato una lunga storia. Una storia che è partita nel 1200, coi tentativi di Lullo di costruire una grande arte, la Ars Magna, E continuata nel 1666 col sogno di Leibniz della Ars combinatoria, della caratteristica universale. Ed è poi esplosa in rapida successione, nel corso di un solo secolo, tra metà Ottocento e metà Novecento, attraverso l'algebra di Boole, i teoremi di Godel, la macchina universale di Turing, i circuiti elettrici di Shannon, le reti neurali di McCul-loch e Pitts e l'architettura di von Neumann.
Dall'ENIAC a oggi sono passati più di cinquant'anni, e l'informatica è ormai fiorita, o esplosa. Ma i computer che essa offre al mercato e ai consumatori, sono tutte e sole macchine universali. I miglioramenti che ci sono stati dal 1945 a oggi, non sono teorici, ma solo tecnologici. Le macchine diventano sempre più veloci, sempre più piccole, sempre meno care.
Ma dal punto di vista delle loro potenzialità di calcolo, non hanno fatto passi avanti, perché più di quanto fa una macchina universale, non si può fare. I computer del 1945 sapevano fare tutte e sole le cose che sanno fare i nostri computer: cioè, calcolare le funzioni calcolabili. Sembra quasi un gioco di parole, ma le funzioni calcolabili oggi si possono definire all'inverso, dicendo semplicemente che sono le funzioni che uno qualunque dei nostri computer che abbiamo sulla scrivania è in grado di calcolare.
Naturalmente c'è un piccolo trucco: stiamo parlando dei computer come se fossero macchine di Turing universali, ma ricorderete che il nastro della macchina di Turing in realtà era un nastro infinito. Le nostre macchine non hanno una memoria veramente infinita: ce l'hanno «potenzialmente» infinita, perché può essere espansa quanto si vuole. Dunque, i computer sono solo macchine universali «potenziali».
Per concludere, possiamo però cercare di rispondere a un interrogativo che si pose lo stesso Turing nel 1950, pochi anni prima di morire: quali sono i limiti delle macchine universali, dei computer? Sappiamo che le macchine universali di Turing possono calcolare tutte le funzioni calcolabili, ma il nostro problema ora è: che cos'è veramente calcolabile?
Uno dei grandi problemi che Turing si pose, alla fine della sua breve vita, fu quello dell'«intelligenza artificiale». Fino a che punto è possibile simulare il pensiero umano, attraverso una macchina come il computer? Questa, naturalmente, è una domanda alla quale non si è data ancora una risposta definitiva. L'Intelligenza Artificiale è un'impresa che dura ormai anch'essa da più di cinquant'anni, e molti risultati sono stati ottenuti. Per esempio, si sono riusciti a fare dei programmi di scacchi che ormai battono sistematicamente i campioni del mondo. Quindi le macchine sono oggi in grado di giocare a scacchi meglio degli scacchisti stessi.
Pag. 35

Dal punto di vista della matematica, le macchine ormai sono in grado di dimostrare teoremi. Anche se non hanno ancora dimostrato dei grandissimi teoremi da sole, sono state essenziali nel permettere la dimostrazione di alcuni grandi teoremi. Un esempio fra tutti è il famoso «teorema dei quattro colori»: il fatto, cioè, che bastano quattro colori per colorare le nazioni di una carta geografica, in modo tale che queste nazioni non abbiano mai lo stesso colore se sono confinanti. Il teorema fu dimostrato a metà degli anni Settanta, usando un numero enorme di ore di computer, circa 2000, a Urbana-Champaign.
C'è però una cosa che, sorprendentemente, si è dimostrata molto difficile, ed è forse impossibile, da far fare alle macchine: simulare ciò che noi facciamo con la nostra sensorialità, col nostro corpo. Gli stoici definivano l'uomo come «un animale razionale». Quando l'Intelligenza Artificiale incominciò, si pensava che simulare le attività animali sarebbe stato molto facile, e simulare invece l'attività tipicamente umana, cioè la razionalità, sarebbe stato molto difficile.
Oggi si è scoperto, sorprendentemente appunto, che è vero esattamente il contrario. E facile per le macchine, o perlomeno è possibile, simulare la nostra parte razionale. E invece molto difficile far simulare a un computer, a una macchina, cose che noi facciamo automaticamente, e che fanno benissimo anche gli animali: per esempio, riconoscere le forme.
Qualunque animale riconosce il suo padrone, semplicemente in base a delle impressioni sensoriali. Ma le macchine ancora hanno enormi difficoltà a riconoscere le facce, a fare quella che in gergo viene chiamata pattern recognition. E questa è una scoperta filosoficamente interessante: le macchine sembrano essere in grado di fare ciò che è tipicamente umano, e male ciò che è tipicamente animale.
Si assiste così a un completo capovolgimento della filosofia cartesiana, che pensava che gli animali fossero delle pure macchine, e che l’uomo fosse qualche cosa di più. Oggi noi stiamo scoprendo che gli animali non sono affatto delle macchine, e che noi ci distinguiamo da loro solo per il fatto di avere una macchina nel cervello. In altre parole, l’informatica ci ha insegnato c e l’uomo non è altro che un “animale dotato di un computer”.





Elenco blog personale