Turing - La nascita dell'intelligenza artificiale

Mattia Monga, AA.VV., Mattia Monga

• Editore: Pelago
• Anno: 2021
• eBook ISBN: 9791280714985
• Argomento: Storia
• Categoria: Storia della scienza

Alan Turing è celebre per aver contribuito in modo decisivo, durante la seconda guerra mondiale, all'impresa di decifrare i messaggi in codice utilizzati dai tedeschi con la loro macchina Enigma. Ma questa sua attività ha finito per mettere in ombra il suo fondamentale ruolo di padre dell'informatica, in un periodo in cui questa disciplina non aveva ancora un nome e gli elaboratori eseguivano compiti appena superiori a quelli di una calcolatrice meccanica da tavolo. Concentrando le sue ricerche sulla "computabilità", cioè la valutazione della possibilità di far eseguire determinate operazioni a una macchina, a poco più di vent'anni definì i confini teorici dell'informatica presente e futura. Le sue ricerche successive non potevano non investire il campo di quella che in seguito si sarebbe chiamata intelligenza artificiale: il famoso test che porta il suo nome è ancora al centro del dibattito, quanto mai aperto, sulla capacità delle macchine di competere con la mente umana.

FOCUS

L’IMPORTANZA DI TURING

Alan Mathison Turing è universalmente considerato uno dei padri dell’informatica, forse il più rappresentativo. La più importante associazione internazionale di informatici, l’Acm (Association for Computing Machinery), gli ha dedicato il suo premio più prestigioso, che negli ambienti accademici è spesso equiparato a una specie di premio Nobel della disciplina. Eppure certamente Turing non si sarebbe mai sognato di definirsi “informatico”, innanzitutto perché questa parola ancora non esisteva. Insomma Turing non poteva riconoscere nel proprio lavoro i germi di una disciplina largamente autonoma dalle precedenti, in particolare dalla matematica, l’ambito nel quale si era formato. Anche se era certamente consapevole di contribuire al ripensamento dei fondamenti della matematica, morì – in condizioni tragiche – troppo presto per cogliere del tutto la rivoluzione che ha cambiato il modo di concepire e progredire nella scienza nel XX e XXI secolo.

Chiariamo subito, quindi, che il termine “informatica” è posteriore a Turing: in tedesco (Informatik) è attestato dal 1957, grazie a Karl Steinbuch, e in francese (informatique) dal 1962, anno in cui Philippe Dreyfus combina esplicitamente le parole information e automatique. Va detto che in inglese – la lingua materna di Turing e dell’informatica – il termine informatics, che pure esiste, è tuttora poco usato. Si continua a preferire, soprattutto negli Stati Uniti, il termine computer science, che però suggerisce l’idea, ormai ritenuta impropria, che l’informatica si occupi di studiare gli strumenti, gli apparati per il calcolo automatico. Questa piccola controversia linguistica è in realtà essa stessa un sintomo di una caratteristica fondamentale dell’informatica, che si manifesta molto bene proprio nell’opera di Turing:

la commistione continua di elementi concettuali e tecnologici, di pensiero astratto e applicazioni concrete.

L’informatica è infatti lo studio dei processi di calcolo che trasformano (elaborano) l’informazione, ma ciò è intrinsecamente connesso alla nostra capacità di costruire apparati in grado di attuare, in modo prevedibile, questi processi.

I PROCESSI DI CALCOLO

Cosa sono dunque i processi di calcolo e perché il contributo di Turing è fondamentale per la loro comprensione e sviluppo? L’idea di descrivere il metodo per ottenere un risultato risale certamente alle origini del pensiero matematico e tecnico. Anzi possiamo senz’altro dire che la storia della tecnica è proprio la storia di come si fanno le cose. E in matematica la descrizione di come si risolve un problema ha radici molto antiche: alcune delle testimonianze matematiche più remote sono proprio elenchi di problemi risolti e di procedure di risoluzione.

Una delle testimonianze più arcaiche è una tavoletta d’argilla ritrovata in Iraq che gli archeologi datano intorno al 1800 a.C.: spiega come ottenere la lunghezza della diagonale di un quadrato data la lunghezza di uno dei suoi lati (con un risultato approssimato, equivalente alla precisione ottenibile con otto cifre decimali).

Notissima nel mondo occidentale è poi l’Aritmetica di Diofanto (III secolo a.C.) un vero e proprio catalogo di problemi numerici. Ma ancor prima Euclide (IV secolo a.C.), nel libro VII dei suoi Elementi dà una procedura per calcolare il massimo comun divisore fra due numeri interi positivi. Questa procedura è oggi nota col nome di “Algoritmo di Euclide” e algoritmo risulta essere la parola chiave dell’informatica. Una parola che ci arriva dall’arabo medievale perché le descrizioni dettagliate dei procedimenti di calcolo hanno avuto un grande influsso proprio a partire dal Medioevo.

In particolare un trattato sulla risoluzione di problemi con metodi “algebrici”, scritto (a Baghdad) dal matematico arabo Abū Ja‘far Muhammad ibn Mūsā al-Khwārizmī (circa 825), dal cui nome (che letteralmente significa Padre di Ja‘far, Muhammad, figlio di Mūsā, nativo di Khwārizmī, l’attuale città di Khiva in Uzbekistan) si fa derivare il termine algoritmo.

Anche algebra è una parola che deriva dallo stesso testo, che infatti introduce «regole di riduzione e comparazione» (Kitāb al-jabr wa al-muqābala) per risolvere problemi numerici. Le traduzioni latine del Kitāb al-jabr wa al-muqābala (Liber algebrae et almuchabala) circolano molto in Europa a partire dal XII secolo (grazie a Roberto di Chester e Gerardo da Cremona) e sono senz’altro l’ispirazione per un’altra opera fondamentale: il Liber abbaci di Leonardo Pisano (conosciuto anche come Fibonacci, vedi volume in questa collana), in cui si descrivono procedimenti numerici utili per ottenere i risultati usando manipolazioni di cifre, in contrasto con l’allora abituale rappresentazione romana, che costringeva all’uso dell’abaco, con le sue evidenti limitazioni.

Notiamo anche che si tratta di cifre arabe, o meglio indiane, come ancora le chiama il Fibonacci, introdotte in Occidente proprio da un’altra opera di al-Khwārizmī, nota nella traduzione latina come Algoritmi de numero Indorum.

TURING E L’EFFETTIVA CALCOLABILITÀ

Proprio riflettendo sul lavoro di al-Khwārizmī o di Fibonacci possiamo iniziare a capire davvero il contributo innovativo di Alan Turing. Fino a gran parte del XIX secolo a molti matematici le descrizioni (gli algoritmi) come quelle di Euclide, Fibonacci ecc. sembravano tutto sommato soddisfacenti, visto che in pratica si era in grado di ripetere i procedimenti descritti. Ma l’ansia di precisione che attraversa la matematica all’alba del XX secolo rende quel “tutto sommato” un’approssimazione deludente. Nel 1910-13 il logico e filosofo Bertrand Russell e il matematico e filosofo Alfred North Whitehead pubblicano duemila pagine (i Principia Mathematica) per spiegare che cosa significhi esattamente che 1 + 1 = 2.

Nel 1928 il matematico tedesco David Hilbert e il suo studente Wilhelm Ackermann formulano esplicitamente la sfida dell’Entscheidungsproblem (Entscheidung in tedesco significa decisione, determinazione): dato un enunciato della logica del prim’ordine (in pratica le proposizioni usate abitualmente in matematica, affermazioni del tipo “se n è un numero intero positivo dispari, allora n diviso 2 dà resto 1”), esiste una “procedura effettiva” capace di stabilire se esso è dimostrabile o confutabile, cioè se è effettivamente derivabile da un determinato insieme di proposizioni assunte come vere (assiomi)? Si cerca quindi un algoritmo. E perché esso sia soddisfacente deve essere una procedura che può essere (almeno in linea di principio) effettivamente portata a termine.

È in questa temperie che Turing nel 1936 (all’età di ventiquattro anni) dà il suo primo contributo On Computable Numbers, with an Application to the Entscheidungsproblem, che rimarrà anche quello più iconico e influente: per affrontare l’Entscheidungsproblem dovrà innanzitutto chiarire che cosa bisogna intendere esattamente per “procedura effettiva”, altrimenti saremmo da capo nell’ambito delle soluzioni inaccettabili per il rigore matematico del tempo.

Sul tema aveva lavorato anche il matematico e logico austriaco Kurt Gödel, già molto famoso per i suoi teoremi di incompletezza che avevano arrecato un grave colpo alle speranze di Hilbert (e di molta della comunità matematica dell’epoca) che per ogni domanda matematica dovesse necessariamente esistere una risposta accessibile allo studio sistematico. Negli anni dal 1931 al 1935 Gödel e poi il matematico statunitense Stephen Kleene avevano formulato una teoria delle funzioni ricorsive che avrebbe dovuto appunto chiarire il concetto di effettiva calcolabilità di una funzione.

La teoria, per quanto elegante e in realtà effettiva, era però troppo astratta per chiarire davvero l’idea intuitiva di calcolo o procedura: lo stesso Gödel non ne fu mai pienamente soddisfatto e in quel periodo altri continuarono a lavorare a formulazioni alternative. Fra questi, il matematico e logico statunitense Alonzo Church che a questo scopo nel 1930 aveva proposto il suo “λ-calcolo”, dimostrato, però, essere incoerente nel 1935: una nuova versione del 1936 anticiperà di qualche mese il lavoro di Turing, risolvendo negativamente l’Entscheidungsproblem, ma ancora una volta con un approccio piuttosto astratto, più adatto alle dimostrazioni che a immediati sviluppi tecnologici (che poi, peraltro, ci saranno: il λ-calcolo è un altro “fiume carsico” che riemerge continuamente nell’informatica).

LE MACCHINE DI TURING

Turing affronta il problema (del tutto indipendentemente da Church che diventerà il suo relatore in un successivo percorso di dottorato a Princeton) in una maniera molto diversa dagli approcci di Gödel, Kleene e Church: infatti decide di modellare esplicitamente l’esecutore della procedura, quello che nel gergo informatico corrente viene chiamato interprete. L’approccio è davvero sorprendentemente originale, con quella commistione fra puro pensiero e tecnica che dicevamo essere caratteristica propria dell’informatica.

L’interprete di Turing infatti “mima” un generico esecutore meccanico, cioè un dispositivo in grado di compiere solo operazioni ritenute talmente elementari da poter essere facilmente compiute da macchine elettromeccaniche (o, per quel che conta nel modello, sfruttando qualsiasi altra tecnologia).

Se pure già a partire dal Settecento è possibile reperire esempi di macchine utilizzabili per calcoli specifici, va detto che nessuno strumento reale dall’applicabilità generale immaginata da Turing esisteva nel 1936. Turing così modella l’esecutore di una procedura con una “macchina” (a-macchina, per macchina automatica, nella terminologia di Turing), cioè un dispositivo che agisce in base a elementari o comunque ben comprese leggi fisiche.

La Macchina di Turing è un’astrazione, con idealizzazioni che la rendono un limite cui le realizzazioni concrete possono solo tendere (per esempio si presuppone una disponibilità infinita di supporto alla memorizzazione – una striscia di carta, un nastro magnetico –, che però è utilizzata in ogni momento in quantità limitate), ma è concepita per risultare il più possibile concreta e verosimile all’intuizione: proprio per questo il suo impatto trascenderà l’universo delle dimostrazioni matematiche per fornire diretta ispirazione per la realizzazione di manufatti ingegneristici efficaci, cui lo stesso Turing contribuirà direttamente.

La macchina di Turing “calcola” sostanzialmente grazie alla sua capacità di riconoscere simboli predefiniti (scritti e letti su di un “nastro” che li conserva in sequenza) e mantenere traccia dello stato in cui opera: il suo funzionamento è guidato da un insieme di regole che stabiliscono cosa fare per ogni combinazione possibile di simboli e stati, determinando quale simbolo scrivere e come variare lo stato corrente.

Una macchina di Turing si fonda quindi su concetti ideali, ma la sua descrizione è assolutamente concreta e può essere simulata con una matita e una quantità finita (magari molto grande) di carta: con un po’ di pazienza il funzionamento si segue facilmente (una descrizione dettagliata delle macchine di Turing è nel capitolo Pagine scelte).

Per Turing, dunque, le a-macchine sono un buon modello per “l’effettiva calcolabilità”: intuitivo eppure suscettibile di una trattazione matematica rigorosa. Ma che cosa si può davvero calcolare con le macchine di Turing? È facile immaginare come usarle per fare alcuni semplici calcoli, come la somma di due numeri di una cifra (inizialmente sul nastro).

Ma la domanda cui vuole rispondere Turing è: cosa è possibile calcolare con queste macchine? E cosa invece non lo è?

LA MACCHINA DI TURING UNIVERSALE

Ecco quindi che Turing dimostra innanzitutto che il suo modello è abbastanza potente per calcolare... se stesso! Con una certa fatica (e qualche piccolo errore che verrà corretto nei mesi successivi alla prima pubblicazione), Turing mostra infatti che è possibile scrivere una procedura che esegue una descrizione di una a-macchina, cioè una rappresentazione opportunamente codificata delle sue regole (che, ricordiamo, sono sostanzialmente una matrice simboli/stati) e dell’input cui il calcolo si deve applicare: questa procedura che di fatto interpreta – emula – altre procedure è detta ora Macchina di Turing Universale.

Dal punto di vista logico questa capacità di emulare se stessa è uno dei due punti chiave del modello (l’altro è la sua natura “digitale”: il modello elabora simboli discreti e non rappresentazioni analogiche) ed è un punto di svolta: notiamo infatti che le macchine calcolatrici progettate fino a quel momento non avevano questa caratteristica e potevano quindi compiere solo famiglie “predefinite” di calcoli.

La macchina di Turing universale, potendo invece interpretare tutte le a-macchine, apre le porte a una flessibilità esecutiva senza precedenti.

Il nastro della macchina universale contiene come input iniziale la descrizione di una macchina di Turing (e il rispettivo input): questa descrizione costituisce quindi, come diremmo con il gergo attuale, il programma da interpretare, operando secondo le regole della macchina universale. Con un solo dispositivo fisico, quindi, diventa possibile ottenere qualsiasi macchina logica.

Solo nel 1941 il tedesco Konrad Zuse realizzerà (in Germania, nell’isolamento scientifico che derivava dalla guerra ormai in corso) qualcosa di simile alle capacità previste dai modelli di Turing e la prima macchina “universale” esplicitamente basata sulle idee di Turing verrà inaugurata il 21 giugno 1948: la macchina era la Manchester Small-Scale Experimental Machine, detta “Baby”, la prima macchina al mondo a programma memorizzato che poi evolverà nell’elaboratore Ferranti Mark 1.

Quindi il modello di Turing sembra essere piuttosto potente e generale. Ma ci sono calcoli che non può catturare? La risposta di Turing è sì!

L’argomento usato per dimostrarlo è una “diagonalizzazione” analoga a quella che il matematico tedesco dell’Otto-Novecento Georg Cantor, fondatore della moderna teoria degli insiemi, usò per affermare che l’insieme dei numeri reali è più grande di quello dei numeri interi, mostrando che non è possibile mettere in corrispondenza biunivoca gli elementi dei due insiemi (cosa che è invece, per esempio, possibile fare fra l’insieme dei numeri interi e quello dei numeri pari: n ↔ 2n).

Ecco: nel lavoro On Computable Numbers Turing mostra che l’insieme delle a-macchine è numerabile (dello stesso ordine di infinito, quindi, dei numeri interi) e che perciò inevitabilmente ci saranno calcoli (anch’essi in numero infinito, ma come i numeri reali) che sfuggono alle possibili a-macchine.

L’insieme di ciò che è calcolabile automaticamente, dunque, è inerentemente più piccolo dell’insieme dei calcoli che si possono definire.

Turing passa anche a dare esempi di “numeri” (che poi vuol dire qualsiasi cosa suscettibile di una rappresentazione simbolica) che, pur ben definiti, non si possono calcolare con una a-macchina: in particolare quei numeri che permetterebbero di decidere se una proposizione della logica del prim’ordine è dimostrabile o computabile (l’Entscheidungsproblem). Turing conia un nome preciso per la classe di ciò che è invece ottenibile con le a-macchine: si tratta dei numeri “computabili” del titolo dell’articolo.

È un passaggio chiave, analogo per molti aspetti a quel teorema di incompletezza col quale Gödel nel 1931 aveva distrutto le speranze dei positivisti logici di inizio secolo e che affermava che il sistema formale dei Principia Mathematica, se è coerente, deve anche essere necessariamente incompleto e contenere proposizioni che non possono essere dimostrate all’interno del sistema stesso.

Il sistema formale definito dalle a-macchine, per quanto potente, lascia problemi ben definiti e che p...

Indice dei contenuti

• Collana
• Frontespizio
• Copyright
• Indice
• Il computer teoretico
• PANORAMA
• FOCUS a cura di Mattia Monga
• APPROFONDIMENTI
• Piano dell'opera