I Premi Turing: John Warner Backus

Uno dei più celebri e utilizzati linguaggi di programmazione è stato (ed è) sicuramente il FORTRAN. Non poteva non aggiudicarsi il Premio Turing uno come John Warner Backus, creatore non solo del FORTRAN, ma anche, assieme al danese Peter Naur, di una fortunata notazione per definire le sintassi di linguaggi formali.
Nato a Filadelfia il 3 dicembre 1924, Backus non fu certo uno studente modello. Nel 1942 si iscrisse a chimica all'Università della Virginia, ma a causa della sua scarsa performance venne espulso dopo pochi mesi. Dopo un periodo di arruolamento nell'esercito, Backus frequentò alcuni corsi universitari di medicina, ma anche in questo caso non li portò a termine, trovando gli argomenti di studio poco stimolanti. Per di più, in questo periodo gli venne diagnosticato un tumore osseo al cranio, che fortunatamente gli fu rimosso senza gravi conseguenze.
Il giovane John si trasferì a New York, con idee molto confuse sul suo futuro. Cominciò a interessarsi di elettronica e, conseguentemente, di matematica. Si iscrisse quindi alla Columbia University e nel 1949 si laureò. L'anno dopo entrò alla IBM, dove il suo primo compito fu scrivere programmi per il Selective Sequence Electronic Calculator (SSEC).
Finalmente aveva trovato la sua strada.
Uno dei principali utilizzi del SSEC era il calcolo di tabelle di effemeridi astronomiche. Le tecniche di programmazione ideate da Backus in quegli anni sarebbero state impiegate anni dopo dalla NASA per il programma Apollo.
A quei tempi, scrivere programmi informatici significava inanellare, una dopo l'altra, migliaia di istruzioni a livello macchina. Un lavoro estremamente difficile, ad alto rischio di errori. Per facilitare il compito, nel 1953 Backus inventò Speedcoding, il primo linguaggio di alto livello della storia: le operazioni sui numeri a virgola mobile potevano essere descritte in una forma più semplice e veloce.

Un IBM 704 in uso alla NASA nel 1957

La IBM aveva lanciato nel 1954 il modello 704, il primo computer prodotto in serie dotato di una unità di calcolo in virgola mobile, e Backus si offrì di creare un linguaggio che avrebbe reso facile programmarlo.
Gli fu assegnato un team di dieci programmatori, che dopo un anno produsse una prima versione delle specifiche del linguaggio IBM Mathematical FORmula TRANslating System, ovvero del FORTRAN.
Il primo compilatore FORTRAN venne ufficialmente rilasciato nel 1957: consisteva di più di 25.000 righe di codice macchina, e venne incluso in tutti i modelli 704 venduti dalla IBM in quegli anni.
Col passare degli anni il FORTRAN venne progressivamente perfezionato e si guadagnò presto la posizione del linguaggio di programmazione più utilizzato per le applicazioni scientifiche.

Uno dei linguaggi che furono sviluppati sulla base del FORTRAN fu l'ALGOL: Backus prese parte alle riunioni di definizione, e fu nell'ambito di questo progetto che lo stesso Backus propose l'utilizzo della forma che prende il suo nome e quello del collega danese Peter Naur. La forma di Backus-Naur è una notazione formale per descrivere qualsiasi linguaggio di programmazione libero dal contesto, ed è particolarmente utile nello sviluppo di nuovi compilatori.

Fu grazie a questi straordinari risultati che John Backus fu insignito nel 1977 del Premio Turing.
Nella lezione che tenne in occasione della consegna del premio, Backus affermò:

I linguaggi di programmazione sembrano oggi in difficoltà. Ogni nuovo linguaggio incorpora, con qualche piccolo miglioramento, tutte le caratteristiche dei suoi predecessori e qualcuna di nuova. [...] Ogni nuovo linguaggio sostiene di avere nuove e affascinanti caratteristiche... ma la verità è che pochi linguaggi rendono la programmazione abbastanza economica e affidabile da giustificare il costo di produrre e imparare nuovi linguaggi.

Sulla base di questa sua affermazione, Backus indicò un nuovo paradigma di programmazione, denominato "function-level", che avrebbe dovuto sostituire il tradizionale approccio "value-level".
La programmazione "function-level" non va confusa con la programmazione funzionale (quella che si ritrova nel Lisp, ma anche in R, Wolfram Mathematica e Python). Nel paradigma tradizionale (value-level) si scrive un programma che viene applicato ai dati di input in modo da produrre una successione di valori intermedi che, alla fine, culmina nel valore finale desiderato. Nel paradigma function-level, invece, si parte da un programma iniziale che è sempre lo stesso per ogni computazione, e si applicano alcune operazioni "program-forming", o "funzionali", che producono una successione di programmi intermedi, fino a culminare nel programma finale desiderato.
Sempre nel 1977 Backus propose un esempio di linguaggio "function-level", chiamato FP, che rimane il prototipo dei linguaggi di questa categoria. Negli ultimi anni della sua carriera cercò di sviluppare un successore di FP, denominato FL. La fortuna di questo paradigma fu tuttavia molto modesta, e rimase confinata nell'ambito accademico-didattico.
Backus terminò la sua lunga carriera in IBM nel 1991, e morì nel marzo del 2007, trent'anni dopo aver ricevuto il premio Turing.

I Premi Turing: Michael Rabin e Dana Scott

Michael Rabin

La serie dedicata agli informatici che hanno vinto il Premio Turing prosegue con una lentezza geologica: perdonatemi. Ma, come sa bene chi li studia, i fenomeni geologici procedono con inesorabile costanza: si va adagio, ma non ci si ferma.

Nel 1959, Michael Rabin e Dana Scott scrissero un articolo intitolato “Finite Automata and Their Decision Problem”, con il quale nasceva un nuovo settore dell’informatica teorica: lo studio degli automi non deterministici.

Un automa non deterministico è una variante, o meglio una generalizzazione, del classico concetto di automa a stati finiti (deterministico). Un automa a stati finiti (deterministico) è un’astrazione con la quale è possibile descrivere il comportamento di molti sistemi reali. Più nello specifico, esso è costituito da:
- un insieme finito I dei possibili input (o ingressi) del sistema;
- un insieme finito O dei possibili output (o uscite) del sistema;
- un insieme finito S dei possibili stati del sistema;
- una "funzione di transizione" f, che stabilisce univocamente quale dei possibili stati del sistema sarà il prossimo, noti lo stato attuale e l'input attuale;
- una "funzione degli output" g, che stabilisce qual è l'output del sistema, noti lo stato attuale e l'input attuale.

Visto che siamo in periodo di feste di fine anno, consideriamo un kit di luci per un albero di Natale: immaginiamo che vi sia un interruttore che, premuto una prima volta, accende le luci in una modalità fissa, e, premuto una seconda volta, attivi la modalità intermittente. Se premiamo l’interruttore una terza volta, le luci si spengono, e il ciclo può essere riavviato.
Il sistema preso ad esempio è molto semplice: ha un solo input possibile (la pressione dell'interruttore), due output (le luci fisse e le luci intermittenti) e tre stati, che possiamo denominare rispettivamente “S” (spento), “F” (fisso), “I” (intermittente). L’automa a stati finiti (deterministico) che descrive il nostro luccicante sistema può essere quindi disegnato come segue:

Nel grafo sono rappresentate, in modo abbastanza autoesplicativo, le funzioni di transizione e delle uscite.

Ora vi chiedo un ulteriore sforzo di immaginazione (coraggio, abbiamo quasi finito, poi resta la parte più semplice e biografica del post): supponiamo che la funzione di transizione, anziché "produrre" come valore uno dei possibili stati del sistema, "produca" una collezione di stati futuri, cioè un sottoinsieme di S. Il risultato sarà un automa a stati finiti non deterministico.
Calma, ragazzi: com'è possibile che la funzione di transizione determini più stati futuri, anziché uno solo? Proprio così: il sistema si può trovare, nello stesso istante, in diversi stati contemporanei, un po' come il gatto di Schrödinger che è vivo e morto nello stesso tempo. Questa è la differenza, o meglio la generalizzazione, rispetto al caso tradizionale deterministico.

Dana Scott

Naturalmente la versione non deterministica è più astratta e meno intuitiva da digerire rispetto alla sua omologa deterministica. Tuttavia, credetemi, questo modello matematico si presta a modellare molte situazioni reali per le quali la versione deterministica sarebbe troppo poco espressiva.

I due ideatori della nozione di automa a stati finiti non deterministico, ovvero Rabin e Scott, provenivano da contesti diversi. Rabin era nato nel 1931 a Breslavia, città allora appartenente alla Germania, oggi alla Polonia, ed era figlio di un rabbino ebreo. All'età di quattro anni si trasferì con la famiglia nel Mandato britannico della Palestina, dove ebbe l'opportunità di coltivare il suo talento per la matematica studiando nella migliore scuola superiore di Haifa e poi, dal 1949, presso l'Università Ebraica di Gerusalemme. Si laureò nel 1953 e conseguì il dottorato nel 1956.
Scott, invece, era nato a Berkeley, in California, nel 1932. Frequentò la prestigiosa Università della sua città studiando logica e filosofia e ottenendo la laurea nel 1954. Trasferitosi a Princeton, ricevette il PhD nel 1958, sotto la supervisione del celebre matematico Alonzo Church. Subito dopo ottenne un incarico di insegnamento presso l'Università di Chicago.

Nel 1959 la IBM organizzò, nei pressi di New York, un workshop estivo al quale invitò un gruppo ristretto di giovani e promettenti ricercatori. Tra i cervelli selezionati c'erano sia Rabin che Scott: fu così che i destini dei due studiosi si incrociarono.
Probabilmente i due non avrebbero mai pensato che, grazie all'articolo scritto in quell'estate newyorkese, avrebbero fondato una nuova branca dell’informatica teorica e avrebbero vinto, diciassette anni dopo, il premio più prestigioso dedicato alla computer science.
L'importanza del loro concetto di automa non deterministico non venne riconosciuta subito. Tuttavia, dopo il fatidico 1959, la carriera dei due scienziati fu piuttosto rapida. Rabin tornò all'Università di Gerusalemme, dove a soli 29 anni divenne professore associato e capo dell'Istituto di Matematica. Quattro anni dopo era professore ordinario. Scott ottenne un posto a Berkeley, si spostò qualche anno dopo a Stanford e poi a Princeton.

Negli anni successivi Rabin e Scott si occuparono non soltanto di automi non deterministici ma anche di altri temi dell'informatica teorica. Scott divenne un guru nel campo della logica matematica, specialmente per quanto riguarda le logiche non classiche e la semantica denotazionale. Rabin, invece, contribuì in modo determinante allo studio degli automi probabilistici, agli algoritmi di confronto tra stringhe (pattern matching), alla crittografia e alla sicurezza informatica. Trasferitosi nel 1975 al MIT come visiting professor, ideò assieme a Gary Miller un fondamentale procedimento, basato sull'ipotesi di Riemann generalizzata, per determinare velocemente se un numero è primo o no.

I premi Turing: Alan Newell e Herbert Simon

Che l'intelligenza artificiale sia un campo di ricerca estremamente complesso, posto all'intersezione tra discipline tra loro molto diverse come informatica, matematica, ingegneria, psicologia e filosofia, è cosa ben nota. Non deve stupire, quindi, che tra i maggiori studiosi di questa materia vi siano stati non soltanto matematici e informatici puri, ma anche scienziati eclettici il cui background includeva ambiti apparentemente eterodossi come la psicologia.
Alan Newell e Herbert Simon sono stati un ottimo esempio di questa categoria. Nel 1975, per la prima volta dalla nascita del premio Turing, il prestigioso riconoscimento venne assegnato a due ricercatori anziché uno solo, e la scelta ricadde su questi due americani.
Newell si laureò in matematica a Stanford nel 1949, e lavorò alla RAND Corporation per progetti legati all'aeronautica militare. Pochi anni dopo cominciò ad appassionarsi ad una disciplina che stava muovendo i suoi primissimi passi: l'intelligenza artificiale. Un campo così nuovo che non aveva ancora un nome, visto che la fortunata espressione venne coniata solo al celebre seminario del Darmouth College del 1956. In quegli anni scrisse "The Chess Machine: An Example of Dealing with a Complex Task by Adaptation", uno dei primi libri della storia dell'intelligenza artificiale.
Qui entra in scena Herbert Simon, di 11 anni più vecchio di Newell. Simon si era laureato nel 1936 in scienze politiche, aveva conseguito il dottorato nella stessa materia nel 1943, e aveva iniziato una brillante carriera universitaria in diverse università, occupandosi di scienze politiche ed economia.
I suoi interessi di ricerca, tuttavia, spaziavano anche in molti altri ambiti, dalla psicologia all'informatica, dalla sociologia alla filosofia. Dopo aver letto il libro di Newell, Simon ricontattò il giovane scienziato che aveva conosciuto qualche anno prima a Pittsburgh, e i due cominciarono a collaborare conseguendo alcuni dei risultati più importanti della storia della nascente intelligenza artificiale.
Il "Logic Theorist", da loro realizzato nel 1956 con l'aiuto del programmatore J. C. Shaw, fu il primo programma "intelligente" mai scritto: si dimostrò in grado di dimostrare alcuni dei teoremi enunciati nei Principia Mathematica di Russell e Whitehead, in alcuni casi attraverso dimostrazioni originali.
Altri settori di ricerca studiati da Newell furono l'elaborazione di liste e lo sviluppo di euristiche.
Al seminario del Darmouth College, oltre a Marvin Minsky (da pochi giorni scomparso) e a John McCarthy, già premi Turing rispettivamente nel 1969 e nel 1971, c'erano anche loro, Newell e Simon.
Negli anni successivi la magnifica coppia implementò, sempre in collaborazione con Shaw, un altro programma di intelligenza artificiale, denominato "General Problem Solver": era capace di risolvere problemi di geometria e di giocare a scacchi.
Sia il "Logic Theorist" che il "General Problem Solver" erano scritti in un particolare linguaggio di programmazione ideato dagli stessi Newell e Simon: l'Information Processing Language (IPL).
Nonostante fossimo agli albori della programmazione, questo linguaggio consentiva già alcuni costrutti e meccanismi avanzati, come la gestione di liste, l'allocazione dinamica della memoria, i tipi di dati, le funzioni passate come argomenti, la ricorsione, e molti altri.
Newell continuò, negli anni successivi, a fornire importanti contributi nel campo dell'intelligenza artificiale, ma si occupò anche di psicologia e di modelli cognitivi.
Il suo amico Simon fece anche di più: scrisse di psicologia, di sociologia, di economia, di pedagogia, di scienza del management. Il tema unificante che lo affascinava era il processo cognitivo della decisione.
Il percorso straordinario di questo scienziato così poliedrico culminò nel 1978 con il premio Nobel per l'Economia, ricevuto per aver descritto il concetto di decisione organizzativa in un contesto di incertezza.
Che io sappia, si tratta ad oggi dell'unica persona ad aver vinto il premio Turing e anche il premio Nobel.

I premi Turing: Donald Knuth

Ricordo che ai tempi dell'università mi imbattevo di continuo in articoli o libri di informatica che, nella bibliografia, immancabilmente citavano uno dei testi sacri di questa disciplina: The Art of Computer Programming (in italiano L'arte della programmazione), dell'informatico americano Donald Knuth.
Probabilmente contagiato da questa usanza, anch'io alla fine decisi di inserire il sacro titolo nella bibliografia della mia tesi, come potete vedere nella figura qui a fianco.
Donald Knuth ha festeggiato proprio l'altro ieri, 10 gennaio, il suo settantasettesimo compleanno. Quando a Padova trovavo il suo libro citato ovunque, l'insigne ricercatore era appena più che cinquantenne: e io che me lo figuravo come un accademico decrepito, se non addirittura già defunto!
The Art of Computer Programming (spesso citata come TAOCP) è una monografia in più volumi, riguardante la teoria degli algoritmi e la loro analisi. Nei piani iniziali di Knuth, cioè attorno al 1962, doveva diventare un libro singolo in dodici capitoli. Negli anni successivi, però, il progetto si ampliò moltissimo, al punto che l'autore decise di strutturare la monografia in ben sette volumi. I primi tre uscirono rispettivamente nel 1968, nel 1969 e nel 1973. Si dovette attendere il 2005 per vedere una prima edizione del quarto volume (che venne completato nel 2011). L'opera è quindi tuttora largamente incompleta, e nuovi volumi sono attesi per i prossimi anni.

Seguendo le orme del padre, organista dilettante, anche il giovane Donald studiò musica, e da ragazzo suonava l'organo in chiesa alla domenica. Una sua passione giovanile era inventare cruciverba, che poi pubblicava nel giornalino della scuola. A quattordici anni vinse un concorso sponsorizzato da una ditta di dolciumi. La sfida era formare il maggior numero possibile di parole con le lettere di "Ziegler's Giant Bar": Donald ne trovò ben 4500, mentre i giudici stessi ne avevano soltanto 2500 nella loro lista di riferimento.
Oltre che dalla musica e dall'enigmistica, Donald era fortemente attratto dalla fisica e dalla matematica, e per molto tempo fu incerto su quale sarebbe stata la sua strada. Un bel giorno decise che sarebbe diventato un fisico, ma nemmeno questa si rivelò essere la scelta definitiva: alla fine cambiò facoltà e si iscrisse a matematica (la musica è tuttavia rimasta un suo grande amore: oggi trascorre molto tempo suonando un organo a canne che è stato installato nella propria abitazione).

Knuth ottenne il dottorato in matematica nel 1963, al California Institute of Technology, dove subito dopo fu assunto come professore associato. In quegli anni ricevette la proposta di scrivere un libro sui compilatori, e fu questo l'assist che lo portò a redigere il suo celebre e monumentale trattato.
Lavorò poi per la NSA (National Security Agency), e nel 1968 divenne professore alla Stanford University.
Gli anni successivi lo videro destinatario di una lunga serie di importanti premi: oltre al premio Turing, vinto nel 1974, Knuth fu insignito del Grace Murray Hopper Award, della National Medal of Science, del John von Neumann Medal e del prestigioso Premio Kyōto.
Nel 1992 Knuth si ritirò dall'insegnamento: di tanto in tanto tiene ancora lezioni informali, che lui ama chiamare "computer musings" (meditazioni informatiche"). Citando la sua celebre opera, la Stanford University lo ha insignito del titolo di "Professor Emeritus of The Art of Computer Programming".

Il contributo principale di Knuth, riversato in TAOCP e motivo dell'assegnazione del premio Turing, riguarda soprattutto la teoria degli algoritmi e la loro analisi. Cosa significa analizzare un algoritmo? Essenzialmente determinare la quantità di risorse (tempo e spazio di memoria) necessarie per eseguire l'algoritmo stesso su un computer. Naturalmente, la quantità di risorse necessarie dipende dalla mole di dati che vengono dati in ingresso all'algoritmo: tuttavia, è di solito possibile stabilire una funzione che lega queste due grandezze, cosicché si scopre che esistono algoritmi la cui funzione cresce molto rapidamente e algoritmi per i quali la funzione si mantiene invece su livelli bassi anche per grandi quantità di dati in ingresso. Si dice che gli algoritmi del primo tipo hanno un'alta complessità, mentre quelli del secondo tipo, caratterizzati da una complessità più bassa, si rivelano quelli preferibili per la risoluzione di problemi.
Nel suo trattato Knuth considera in dettaglio molti problemi computazionale, fornendo indicazioni sugli algoritmi utilizzabili per risolverli e sistematizzando le tecniche matematiche rigorose per l'analisi della complessità.

Oltre che per queste fondamentali ricerche, Knuth è noto anche per avere creato il sistema tipografico TeX, adatto alla composizione di testi matematici e scientifici. Da questo sistema, Leslie Lamport,  vincitore del premio Turing nel 2013, derivò il popolare linguaggio di markup LaTeX.
Restando sempre nell'ambito tipografico, Knuth inventò anche METAFONT, un linguaggio di programmazione usato per definire font vettoriali.
Un altro merito di Knuth è legato alla cosiddetta "literate programming", un approccio alla programmazione in cui il programma viene descritto utilizzando una lingua naturale come l'italiano, inframezzando qua e là porzioni di codice: il contrario di quello che fanno solitamente i programmatori, che producono lunghi file di codice con qualche commento in linguaggio naturale ogni tanto.
Knuth, inoltre, è sempre stato un fiero oppositore del concetto di brevetto nel capo del software.

Ma al si là dei suoi risultati nell'ambito della ricerca informatica, Donald Knuth è celebre per la sua poliedricità, per il suo umorismo e per certe scelte per così dire bizzarre.
Per cominciare, non usa più la posta elettronica dal 1990: lui stesso afferma di averla utilizzata solo per 15 anni, a partire dal 1975. In questa pagina spiega le ragioni della sua scelta.

Per ogni errore scovato nei suoi libri, Knuth riconosce un premio di 256 penny, cioè, come dice lui, un "dollaro esadecimale".
I numeri di versione del sistema TeX tendono asintoticamente al valore di π. Dopo la versione 3, sono stati assegnati via via i valori 3.1, 3.14, 3.141 e così via.
Per il sistema METAFONT il meccanismo è lo stesso, ma la versione limite è il numero e. Knuth ha affermato che gli eventuali bug ancora presenti al momento della sua morte saranno promossi a funzionalità, e le versioni saranno fissate ai valori π ed e.
Infine, Knuth è anche uno studioso della Bibbia, e autore di un bizzarro libro in cui analizza il testo sacro prendendo in esame soltanto il sedicesimo versetto del terzo capitolo di ciascun libro. Se volete ascoltare Knuth parlare della Bibbia, recatevi il prossimo 8 marzo nella prima chiesa luterana di Palo Alto: sentirete il padre dell'arte della programmazione raccontare il suo progetto di scrivere una complessa opera per organo basata sull'Apocalisse di San Giovanni.

I premi Turing: Charles Bachman

Charles Bachman (da http://amturing.acm.org)

Che cos'è l'informatica?  Cercate il termine su un qualsiasi dizionario: con ogni probabilità, troverete definizioni del tipo "La scienza che si occupa dell’ordinamento, del trattamento e della trasmissione delle informazioni per mezzo dell’elaborazione elettronica" (questa è tratta dal Le Monnier).

In ogni caso, è pressoché certo che all'interno della definizione troviate la parola  "informazione" (lo stesso vocabolo "informatica" è la contrazione di "informazione automatica"). Se gli informatici hanno soprattutto a che fare con informazioni, è evidente che uno delle loro necessità principali sia quella di immagazzinare queste informazioni da qualche parte.

I database (o le “basi di dati”, se preferite la dizione italiana, ormai un po’ desueta), sono una delle più importanti risposte escogitate per soddisfare questo bisogno. Esistono molti tipi di database, ma la categoria di gran lunga più utilizzata è quella dei database relazionali. 

Uno dei primi ricercatori a occuparsi dell’argomento fu l’americano Charles Bachman, classe 1924, premio Turing 1973. 

Il padre di Charles era un allenatore di squadre universitarie di football, e negli anni dell’infanzia di Charles si spostò molto tra gli atenei americani, portando con sé la famiglia. Nel 1944 Charles si arruolò nell’esercito e combatté fino alla fine della guerra nel teatro del Pacifico. Nel 1950 si laureò in ingegneria meccanica presso l’Università della Pennsylvania. Negli anni successivi fu ingaggiato da una compagnia chimica per lavorare su alcuni problemi di ricerca operativa, e fu in questa occasione che ebbe le sue prime esperienze con i computer. 

Da allora in poi, il suo percorso di ricerca e sviluppo si svolse interamente presso aziende piuttosto che in ambito accademico. Nel 1960, presso la General Electric, cominciò la sua lunga e onorata carriera di ricercatore nell’ambito dei database progettando IDS ("Integrated Data Store"), uno dei primi e più famosi sistemi di gestione di dati della storia.

IDS implementava una serie di tecnologie innovative che rappresentarono per molti anni il punto di riferimento nell'ambito dei database. Ci volle molto tempo prima di vedere emergere altri sistemi che potessero competere con quello progettato da Bachman.

Charles Bachman

Il contributo più noto di Bachman riguarda però i diagrammi che portano il suo nome: schemi utilizzati per descrivere la struttura di un database relazionale come una rete che collega tra di loro diverse “relazioni”. Una relazione è un insieme di “tuple” (d₁, d₂, ..., d_n), ciascuna delle quali è una sequenza di m attributi (dove m è un numero naturale). I valori ammessi per gli attributi di una tupla possono appartenere a insiemi diversi, ma la sequenza di domini ammessi è la stessa per tutte le tuple di una stessa relazione.

Il modo più intuitivo per raffigurarci mentalmente una relazione è vederla come una tabella: le sue tuple sono le righe, mentre gli attributi (ciascuno con il suo dominio) che compongono le tuple corrispondono alle colonne. Una relazione serve astrattamente per rappresentare un’entità, e più concretamente per contenere dei dati. Per esempio, una relazione “Impiegati” potrebbe servire per descrivere gli impiegati di un’azienda, ciascuno corrispondente a una tupla, e ciascuna tupla potrebbe essere formata da una sequenza di attributi (nome, cognome, numero di matricola, mansione, stipendio, e così via). 

In un database, e qui tocchiamo il punto critico, vi sono sempre dei legami tra una relazione e l’altra. Supponiamo che oltre alla relazione “Impiegati” il database contenga una relazione “Dipartimenti”: è naturale pensare che tra le due relazioni sussista un legame, allo scopo di stabilire a quale dipartimento appartiene ciascun impiegato, cioè a quale tupla della relazione “Dipartimenti” sia associata ogni tupla della relazione “Impiegati”.

Le figure qui a fianco sono tratte da uno degli articoli fondamentali di Bachman, intitolato Data structure diagrams, e pubblicato nel 1969.

Le due relazioni (o entità) “Dipartimenti” e “Impiegati” sono mostrate come rettangoli che vengono poi collegati tra di loro. La freccia serve a indicare graficamente tale collegamento, e rappresenta l'idea che ogni impiegato è assegnato a uno dei dipartimenti.

In generale, i collegamenti tra entità possono essere caratterizzati da diversi tipi di cardinalità: il tipo più comune è quello 1 a n (un dipartimento contiene n impiegati), ma esistono anche collegamenti 1 a 1, e n a n.

Charles Bachman fu così, verso la fine degli anni Sessanta, uno dei pionieri dei diagrammi che descrivono la struttura di un database relazionale. 

A partire dal 1976, soprattutto in seguito ai lavori dell'informatico Peter Chen, i modelli di questo tipo vengono chiamati “diagrammi entità-relazioni”, o diagrammi E-R. Ma attenzione: qui la parola “relazione” indica i legami tra le relazioni (come quello tra impiegati e dipartimenti), e non le relazioni stesse, che invece sono denominate “entità”. Questa confusione terminologica è stata fonte di mille fraintendimenti. Si noti però che in inglese i termini sono ben distinti: “relation” è l’insieme di tuple che corrisponde a un entità e viene implementato da una tabella, e “relationship” è l’associazione che lega due relazioni, o due entità o tabelle.

Il premio Turing fu assegnato a Charles Bachman nel 1973 per i suoi “eccezionali contributi alla tecnologia dei database”. Le sue ricerche pionieristiche riguardanti la modellizzazione dei database sono state, in effetti, di enorme importanza per lo sviluppo dei potentissimi sistemi oggi disponibili.

Nella storia del prestigioso riconoscimento, Bachman fu il primo vincitore privo di un dottorato, il primo ingegnere (e non matematico), e il primo ricercatore industriale non accademico.

Pare che dopo essere stato insignito, Bachman si interessò molto alla vita di Alan Turing, e fece persino la conoscenza di Sara Turing, l'anziana madre del grande matematico.

I premi Turing: Edsger Dijkstra

Siete i soddisfatti possessori di un'auto sportiva fiammante con l'ultimo modello di navigatore satellitare touchscreen a bordo? Non vi separereste mai dal vostro smartphone e in particolare dall'app di navigazione, che ormai usate anche per percorrere strade ormai ben conosciute? Prima di intraprendere un viaggio qualsiasi, consultate sempre Google Maps e date un'occhiata al luogo di destinazione utilizzando Street View? Be', se è così, sappiate che la persona che dovete ringraziare più di ogni altra non è né l'amministratore delegato dell'azienda costruttrice della vostra macchina, né quello della compagnia che ha prodotto il vostro telefono, e nemmeno i fondatori di Google.

No, il vero artefice delle meraviglie che amate tanto è un signore olandese nato a Rotterdam nel 1930 e scomparso dodici anni fa.
Il suo nome, Edsger Wybe Dijkstra, è noto a tutti gli informatici per il celebre algoritmo che, in modo molto semplice ed elegante, consente di determinare il percorso più breve esistente tra un punto di partenza e un punto di arrivo su una rete di strade.

Figlio di un chimico e di una matematica, al liceo Edsger eccelleva in tutte le materie scientifiche, ma curiosamente era intenzionato a iscriversi alla facoltà di giurisprudenza. Furono i suoi genitori e i suoi insegnanti a convincerlo (per nostra fortuna, verrebbe da dire) a dedicarsi agli studi scientifici, e fu così che studiò fisica teorica all'università di Leida.
Nel 1951 frequentò un corso di programmazione a Cambridge, in Inghilterra. Per il giovane Edsger fu un'esperienza entusiasmante, che lo segnò in modo decisivo: pochi mesi dopo iniziò a lavorare come programmatore al Dipartimento di Informatica del Mathematical Centre di Amsterdam.
Nel 1956 si laureò in fisica, e nello stesso anno ideò il famoso algoritmo del cammino minimo, che sarebbe stato pubblicato tre anni dopo nell'articolo A note on two problems in connection with graphs (il secondo problema trattato, per la cronaca, era un'altra questione di teoria dei grafi: il problema del minimo albero ricoprente).
Sempre nel 1959 ottenne il Ph.D. all'Università di Amsterdam per la sua tesi intitolata Communication with an automatic computer.

Pare che quando Dijkstra si sposò, nel 1957, la burocrazia olandese non accettò che venisse scritta la misteriosa parola "programmatore" nella casella dedicata alla professione: così il neo-sposo optò per la più comprensibile dicitura "fisico teorico". Altri tempi.
Negli anni successivi, Dijkstra fu l'artefice di molte altre innovazioni cruciali per la storia del'informatica moderna: contribuì in modo determinante allo sviluppo del linguaggio ALGOL-60, e vi introdusse un costrutto apposito per la ricorsione; fu il primo a utilizzare il termine "stack", oggi comunissimo tra tutti gli informatici.
Nel 1962 divenne professore di matematica all'Università di Tecnologia di Eindhoven. Dieci anni dopo vinse il prestigioso premio Turing. Nel 1973 fu nominato Research Fellow alla Burroughs Corporation. Dal 1983 al 1999 insegnò informatica all'Università di Austin, in Texas.

Dijkstra è oggi considerato uno dei mostri sacri della storia della teoria degli algoritmi e della programmazione strutturata, e scrisse numerosi libri e articoli su questi temi.
Molteplici sono le sue scoperte, al di là del celebre algoritmo del cammino minimo: tra queste citerò l'algoritmo "shunting-yard", utilizzato per analizzare espressioni matematiche in notazione infissa, il pionieristico sistema operativo "THE", che supportava il multitasking ed era elegantemente strutturato come una "pila" di strati, il famoso algoritmo del banchiere e il geniale concetto di "semaforo", croci e delizie di ogni studente dei corsi di sistemi operativi.
Fu sempre Dijkstra a rendersi conto che, nei linguaggi di programmazione di alto livello, l'istruzione GOTO (che permette di saltare da una riga a un'altra all'interno di un programma) non è compatibile con una buona strutturazione del programma: nel 1968 scrisse l'articolo A case against the GO TO statement, che sosteneva questa tesi. Un altro settore di ricerca approfondito dall'informatico olandese fu quello della verifica formale della correttezza degli algoritmi.
Per tutti questi fondamentali contributi Dijkstra fu insignito del premio Turing nel 1972: ma certamente il suo elegante algoritmo del cammino minimo rappresentò il suo successo maggiore e il motivo della sua elevatissima reputazione nel mondo dell'informatica. Come funziona questo celebre algoritmo?

Immaginiamo di avere un grafo come quello illustrato in figura, formato da nodi e da archi. Ogni arco è contraddistinto da un valore numerico chiamato peso.
Un grafo come questo potrebbe rappresentare una rete di strade percorribili per viaggiare da un punto all'altro. In questo caso il peso di un arco sarà indicativo della lunghezza della tratta stradale che l'arco rappresenta, oppure del tempo necessario a percorrerla.
Supponiamo di voler applicare l'algoritmo di Dijkstra per spostarci dal punto A al punto F.
Il metodo di Dijkstra mantiene, in ogni istante dell'esecuzione, tre insiemi distinti di nodi della rete:
l'insieme V dei nodi visitati, l'insieme F dei nodi di frontiera, e l'insieme S dei nodi sconosciuti.
Per ogni nodo z, l'algoritmo tiene traccia di un valore (provvisorio) di distanza dal punto di partenza, d_z, e del predecessore (provvisorio) del nodo stesso, p_z.
All'inizio l'insieme V è vuoto, F è formato dal solo nodo di partenza A, e tutti gli altri nodi sono in S. Tutte le distanze d_z sono inizialmente considerate infinite (ad eccezione di quella del nodo di partenza A, posta a zero), e i predecessori p_z vengono considerati ignoti.
L'algoritmo consiste nel ripetere a ciclo continuo la seguente serie di operazioni. Si sceglie dall'insieme F il (o un) nodo z con distanza d_z minima, si sposta il nodo z nell'insieme V, e si spostano in F tutti i nodi ancora sconosciuti che sono successori di z (cioè che sono collegati a z). Per ciascuno di questi nodi successori viene calcolato un possibile nuovo valore della distanza, pari a d_z + a, dove a è il peso dell'arco che collega z con il nodo considerato. Se questo possibile nuovo valore è minore del precedente, esso viene "ufficializzato", e il predecessore del nodo viene aggiornato a z. In caso contrario, non succede nulla, e si passa al successivo dei nodi successori.

Da cs-exhibitions.uni-klu.ac.at

Quando i nodi successori sono terminati, si ripete la serie di operazioni allo stesso modo, e si prosegue così finché il nodo di destinazione F non risulta visitato, o finché l'insieme di frontiera non si svuota completamente. In quest'ultimo caso avremo capito che F non è raggiungibile partendo da A, altrimenti alla fine avremo compilato per tutti i nodi del grafo i valori di distanza e i predecessori.
Lascio ai lettori l'onore e l'onere di applicare il metodo illustrato al grafo in figura: vedrete che tutto sommato è divertente.

Dijkstra è famoso anche per una sua curiosa abitudine: amava scrivere, con la sua inseparabile penna stilografica, brevi memorie scientifiche, lettere e resoconti a mano, e le etichettava con il prefisso "EWD" (le sue iniziali) seguito da un numero d'ordine. L'archivio dell'Università del Texas ha catalogato più di 1300 documenti “EWD".
Un altro particolare passatempo di Dijkstra era quello di raccontare, anche all'interno dei suoi "EWD", le vicende di un'azienda immaginaria, la Mathematics Inc., il cui business era quello di provare teoremi matematici e poi metterli sul mercato, mantenendo però segreta la dimostrazione. Secondo i fantasiosi racconti di Dijkstra, nel catalogo dei prodotti della società vi era anche l'ipotesi di Riemann: uno dei principali problemi che l‘azienda doveva fronteggiare era la riscossione delle royalties dai matematici che utilizzavano l'ipotesi di Riemann come base di partenza per dimostrare altri teoremi. 

I premi Turing: John McCarthy

Del vincitore del premio Turing del 1971, lo "Zio" John McCarthy, ho già parlato in un mio precedente post, che scrissi in occasione della sua scomparsa quasi tre anni fa.
Ricordavo, in quel breve articolo, la sua figura di padre dell'intelligenza artificiale (fu lui a utilizzare per primo questa espressione, nel 1955), di creatore del linguaggio di programmazione Lisp (1958), di ideatore di tecniche o paradigmi informatici estremamente attuali, come il "time-sharing" della potenza di calcolo e il concetto del software some servizio (1957), e la garbage collection (1959).
E soprattutto descrivevo una sua curiosa creatura matematica: la famosa "funzione 91" di McCarthy, che, grazie alla sua definizione ricorsiva, restituisce sempre 91 per valori minori di 102 dell'argomento.

Ma i meriti dello "Zio" vanno anche oltre.
Nato a Boston nel 1927 da padre di origine irlandese e madre lituana di religione ebrea, durante l'infanzia si trasferì frequentemente con la famiglia, trovando infine dimora pressoché definitiva a Los Angeles.

Da www.computerhistory.org

Grazie alla sua intelligenza eccezionale e alla sua propensione per la matematica, si diplomò con due anni di anticipo. Si laureò al California Institute of Technology, dove le lezioni di John von Neumann lo affascinarono e indirizzarono il corso successivo delle sue ricerche, e ottenne il dottorato in matematica a Princeton. Dopo alcune esperienze accademiche a Princeton, alla Stanford University, al Dartmouth College, e al MIT, nel 1962 divenne professore a Stanford, dove rimase fino al raggiungimento della pensione, nel 2000.
Il suo interesse per l'intelligenza artificiale lo portò a organizzare, già nel 1956, il primo congresso internazionale sull'argomento. Tra i partecipanti c'era Marvin Minsky, che sarebbe divenuto pochi anni dopo collega di McCarthy al MIT.

Da www.computerhistory.org

Nel suo periodo al MIT, lo "Zio" contribuì allo sviluppo di ALGOL, uno dei più importanti tra i primi linguaggi di programmazione. Nel 1958 descrisse "Advice Taker", un modello astratto di programma che può essere considerato il primo sistema completo di intelligenza artificiale: attraverso una definizione formale della conoscenza, era in grado di apprendere nuove informazioni, dedurre nuove verità e formulare piani per svolgere attività complesse.

Il genio di McCarthy andò anche al di là dell'ambito matematico e informatico: pare che nel 1982 lo scienziato abbia progettato uno speciale ascensore spaziale chiamato "fontana spaziale", basato su una torre altissima anziché, come nello schema tradizionale, su un satellite collegato a terra da un cavo.

McCarthy fu uno strenuo sostenitore dell'importanza della matematica e dell'insegnamento della matematica. La sua "signature" sui forum di Usenet recitava così: "Colui che rifiuta di fare di conto è destinato a parlare a vanvera".

I premi Turing: James H. Wilkinson

Chi di voi ha studiato calcolo numerico all’università? Ricordate quei curiosi algoritmi utilizzabili per trovare soluzioni approssimate a svariati problemi di analisi matematica? Per esempio, i metodi per risolvere sistemi di equazioni differenziali alle derivate parziali, o per calcolare gli autovalori di una matrice?
Uno dei più importanti pionieri di questa branca della matematica applicata fu James Wilkinson. Tra gli anni quaranta e cinquanta fu tra i più brillanti esploratori delle metodologie di analisi numerica implementabili sui calcolatori.
Grazie agli sforzi di Wilkinson e di altri matematici dell’epoca si comprese che una procedura adatta a determinare “a mano” soluzioni esatte a problemi matematici, una volta trasferita pari pari in un programma informatico, può spesso portare a risultati del tutto errati.
Per i suoi contributi in questo ambito, Wilkinson fu insignito del Premio Turing nel 1970.

Nato nella cittadina inglese di Strood nel 1919, Wilkinson si laureò in matematica all'università di Cambridge, a meno di 20 anni e con pieni voti. Nel 1940 fu assunto come ricercatore presso il Mathematics Laboratory della stessa città, e tre anni dopo al centro di ricerca di Fort Halstead.
La sua occupazione in questi istituti di ricerca consisteva nell'escogitare tecniche numeriche di calcolo delle soluzioni di equazioni differenziali alle derivate parziali. Considerando che in quegli anni era in corso la seconda guerra mondiale, non sorprende che il principale ambito d'applicazione di questi studi fosse la balistica.
Proprio sul finire del conflitto, nel 1945, Wilkinson conobbe e sposò una sua collega, Heather Nora Ware.

La versione "pilota" di ACE (1950)

Anche una volta finita la guerra, Wilkinson si trasferì al National Physical Laboratory di Teddington, dove rimase fino al suo pensionamento, avvenuto nel 1980.
Qui continuò ad occuparsi di calcoli legati agli armamenti, ma aggiunse ai suoi settori applicativi anche l’aerodinamica supersonica.
Non poteva immaginare che un giorno avrebbe vinto un prestigioso premio intitolato alla memoria del suo primo capo: Alan Turing. Sotto la direzione del pioniere dell'informatica teorica, infatti, Wilkinson contribuì alla costruzione dell'Automatic Computing Engine (ACE), il primo computer elettronico del Regno Unito, che divenne operativo nel 1950. In particolare Wilkinson fu il progettista del modulo preposto alle moltiplicazioni.
ACE rappresentò un ulteriore passo avanti nella storia della computazione britannica dopo l'EDSAC, realizzato da Maurice Wilkes, premio Turing nel 1967, sempre sulla base degli studi teorici del grande Alan.
Questo computer d'altri tempi conteneva 7000 valvole termoioniche, 70000 resistenze, 10000 capacità, 5 milioni di giunzioni saldate. Era in grado di gestire le subroutine e implementava un rudimentale linguaggio di programmazione, chiamato Abbreviated Computer Instructions.

James Wilkinson col premio Turing (da http://amturing.acm.org)

A partire dalla fine degli anni  cinquanta, Wilkinson cominciò a pubblicare numerosi articoli e fu anche l'autore di due libri molto famosi: "Rounding Errors in Algebraic Processes", uscito nel 1963, e "Algebraic Eigenvalue Problem", pubblicato nel 1965.
Sempre in quel periodo cominciò a tenere lezioni al Summer College of Engineering dell'Università del Michigan. Un po' alla volta le sue scoperte nel campo del calcolo numerico diventarono note a un pubblico più vasto, e Wilkinson cominciò a ricevere numerosi premi e riconoscimenti, che culminarono nel 1970 con la vittoria del premio Turing. La motivazione faceva riferimento alle "sue ricerche di analisi numerica che hanno facilitato l'uso dei computer digitali ad alta velocità, con speciale riconoscimento per il suo lavoro nella computazione nell'algebra lineare e nell'analisi degli errori 'all'indietro'".

Che cosa sarà mai questa analisi degli errori "all'indietro" (backward)? Immaginiamo che per un certo problema sia stato escogitato un algoritmo numerico approssimato, in grado di trovare, a partire da un dato di ingresso x, un risultato y*. Ora, tale risultato sarà in generale diverso dalla soluzione esatta y. Mentre l'analisi degli errori "in avanti" (forward) si concentra sulla differenza y* - y, l'analisi backward permette di trovare il dato di ingresso x+Δx tale per cui, risolvendo il problema attraverso la procedura esatta, il risultato sarebbe stato proprio y*. Se si scopre che, per ogni dato di ingresso x, l'errore "all'indietro" Δx è piccolo, allora possiamo dire che l'algoritmo approssimato è "stabile all'indietro", il che fornisce un significativo indice della bontà della metodologia numerica utilizzata.

Il "meglio" degli studi di Wilkinson confluì nel 1971 nel celebre "Handbook for Automatic Computation", scritto insieme a C. Reinsch.
Wilkinson morì nel 1986. Nella lezione che tenne nel 1970 dopo aver ricevuto il Premio Turing, raccontò un interessante lato della personalità del suo maestro:

Turing aveva una forte propensione al ricavare i suoi risultati dai principi primi, e in prima istanza non usava consultare alcun lavoro precedente sull'argomento. Senza dubbio fu grazie a questa sua abitudine che la sua opera acquistò un sapore caratteristico e originale.
Mi sono ricordato di una frase che Beethoven pare abbia pronunciato quando gli fu chiesto se avesse ascoltato una certa opera di Mozart particolarmente famosa. Beethoven rispose di no, e aggiunse: "nemmeno l'ascolterò, altrimenti perderò un po' della mia originalità".

I premi Turing: Marvin Minsky

Senza ombra di dubbio, nell'elenco dei vincitori del premio Turing il nome di Marvin Minsky spicca per la sua celebrità e per l'importanza dei suoi risultati scientifici.
In questa carrellata degli insigniti dal 1966 in poi, Minsky è il primo scienziato attualmente ancora in vita.
Le ricerche di Minsky hanno fornito contributi fondamentali in ambiti molto diversi, tra cui l'informatica teorica, la grafica computerizzata, la filosofia, la psicologia cognitiva, la matematica e  soprattutto l'intelligenza artificiale (in particolare la teoria degli automi, l'apprendimento, la rappresentazione della conoscenza, la visione artificiale e la robotica).

Marvin Minsky nacque a New York nel 1927 da una famiglia ebrea. Studiò matematica ad Harvard, dove conseguì la laurea nel 1950, e a Princeton, dove ottenne il dottorato nel 1954 (John Tukey e John von Neumann facevano parte della commissione d'esame). Dal 1958 ha insegnato al prestigioso Massachusetts Institute of Technology di Boston.
Già nel 1951 Minsky progettò SNARC, una macchina che rappresentava il primo esempio di rete neurale artificiale.

Nel 1960 fondò assieme a John McCarthy (che vincerà il premio Turing due anni dopo di lui) il laboratorio di Intelligenza Artificiale del MIT.
Negli anni successivi fu protagonista di numerose geniali invenzioni, tra cui il primo display grafico indossabile e il microscopio confocale a scansione.

Il premio Turing gli venne consegnato nel 1969, "per il suo ruolo centrale nel creare, plasmare, promuovere e far avanzare il campo dell'intelligenza artificiale".
In quello stesso anno, Minsky aveva pubblicato, insieme all'altro matematico Seymour A. Papert (quello che ideò il LOGO, il linguaggio di programmazione della tartaruga), un libro destinato a rimanere uno dei testi fondamentali nella storia dell'intelligenza artificiale.
Il titolo del volume, "Perceptrons: an introduction to computational geometry", si riferiva al percettrone, un semplice schema di rete neurale artificiale con più ingressi e un‘uscita: il valore dell‘output viene calcolato sulla base di una somma pesata dei valori di input.
In questo lavoro si dimostrava che le macchine basate su questo pattern non erano in grado di risolvere molti problemi: si mostrava, ad esempio, che queste semplici reti non sono nemmeno in grado di implementare una semplice funzione XOR.

http://www.flickr.com/photos/glemak/6241401596/lightbox

Paradossalmente, quindi, Minsky fu acclamato come uno dei giganti dell'intelligenza artificiale proprio per avere indicato i limiti dello schema di rete neurale che fino al 1969 era stato ritenuto estremamente promettente per la soluzione di problemi complessi.
Il periodo che ebbe inizio dopo l'uscita del libro di Minsky e Papert viene talvolta chiamato "inverno dell'intelligenza artificiale", perché l'euforia degli anni Cinquanta e Sessanta fu sostituita da un sentimento di diffidenza e disillusione, e i finanziamenti alle ricerche in questo settore furono radicalmente ridimensionati.

Ma ovviamente Minsky non si limitò a distruggere. Fu l'ideatore di numerosi modelli innovativi nel campo dell'intelligenza artificiale.
E non si limitò certo a questo ambito. Si interessò, ad esempio, di vita extraterrestre, e fu tra gli scienziati che il regista Stanley Kubrik consultò durante le riprese del suo capolavoro "2001: Odissea nello spazio" (viene addirittura citato nel film stesso).
Il suo legame con la fantascienza non si limitò all'incontro con Kubrik. Durante una vacanza a Malibù, suggerì a Michael Crichton la trama di "Jurassic Park". Pare che l'idea originaria di Minsky prevedeva che i dinosauri fossero delle macchine, e successivamente Crichton li concepì come il risultato di una clonazione.

Nel 1988 scrisse un celebre libro intitolato "La società della mente", in cui viene descritta una vasta teoria cognitiva che lui aveva cominciato a sviluppare nei primi anni Settanta.
Oltre al prestigioso Turing, Minsky è stato insignito di molti altri premi e onorificenze. Attualmente è professore emerito al MIT.
Un giorno Isaac Asimov affermò, tra il serio e il faceto: "Solo due persone sono più intelligenti di me. Una è Carl Sagan. L'altra è Marvin Minsky."

I premi Turing: Richard Hamming

Foto di Louis Fabian Bachrach,
tratta da http://amturing.acm.org

Torno a scrivere dei premi Turing (no, non mi ero dimenticato: la serie proseguirà regolarmente) a poche ore dalla notizia del "Royal Pardon" graziosamente accordato dalla regina Elisabetta al padre dell'informatica teorica. Dopo più di sessant'anni. Che dire? Bè, meglio tardi che mai: con Galileo il Vaticano era riuscito a fare molto peggio...

Il premio Turing del 1968 fu assegnato a un matematico americano, Richard Hamming. Il suo nome è legato a molti concetti fondamentali nell'ambito dell'informatica teorica e delle telecomunicazioni: tanto per fare alcuni esempi, il codice di Hamming, la finestra di Hamming, i numeri di Hamming, e soprattutto la distanza di Hamming.
Nato a Chicago nel 1915, Hamming conseguì il dottorato all'università dell'Illinois nel 1942. Diventò professore a Louisville negli anni della guerra, e partecipò al progetto Manhattan mettendo a disposizione la sua competenza nel campo della programmazione dei primi computer elettronici. Il suo lavoro mirava a risolvere al calcolatore alcune equazioni per capire se l'esplosione di una bomba atomica avrebbe incendiato l'atmosfera. Pare che i risultati ottenuti da Hamming, secondo i quali il fenomeno non si sarebbe verificato, siano stati determinanti per la prosecuzione del programma.
Dopo la fine del conflitto, Hamming collaborò con Claude Shannon, padre della teoria dell'informazione, ai Bell Laboratories, e fu professore al City College di New York, e poi al Naval Postgraduate School in California. Morì nel 1998.

Tra tutte le importanti scoperte di Hamming, mi limito a ricordare quella della "sua" distanza. Se abbiamo due sequenze di simboli, cioè, come diciamo noi informatici, due stringhe, a volte è utile stabilire una misura della loro "somiglianza". Per esempio, è evidente che la parola "gatto" è piuttosto simile alla parola "ratto", ma molto lontana dalla parola "lepre". Come possiamo fare, quindi, matematicamente, a stabilire la distanza tra due "parole" qualsiasi?
Nel 1950 Hamming fornì un semplice modo, applicabile se le due parole hanno la stessa lunghezza: basta contare le posizioni alle quali si trovano caratteri diversi nelle due rispettive parole. Nel caso di "gatto" e "ratto" abbiamo una sola posizione di questo tipo, la prima (alla quale troviamo "g" e "r" nelle due parole), mentre nel caso di "gatto" e "lepre" addirittura tutte le lettere sono diverse, cioè abbiamo una distanza uguale a 5.

Detta in altro modo, la distanza di Hamming è pari al numero di sostituzioni che dobbiamo operare per trasformare una stringa nell'altra.
Dato che nella teoria dell'informazione e nell'informatica rivestono particolare significato le stringhe binarie, cioè le sequenze di zeri e uni, la distanza di Hamming viene spesso applicata a questo tipo di "parole".
Per esempio, consideriamo le stringhe binarie di lunghezza 3. Quante ce ne sono? Naturalmente 2 elevato alla 3, ovvero 8. Non è difficile comprendere che queste 8 possibili combinazioni possono essere disposte ai vertici di un cubo, come illustrato nella figura a fianco. A questo punto, per calcolare la distanza tra due di queste stringhe, basta contare i lati che si devono percorrere per passare da un vertice all'altro.
Due esempi: tra la stringa 100 e la stringa 011 c'è una distanza di Hamming di 3 (percorso rosso), mentre per andare dalla stringa 010 alla stringa 111 la distanza è pari a 2 (percorso blu).

Analogamente, per misurare le distanza tra stringhe binarie di lunghezza n, ci serve uno spazio a n dimensioni. Poco importa se facciamo fatica a rappresentarlo graficamente: i matematici non si scompongono più di tanto di fronte a queste difficoltà.
In generale, la distanza di Hamming gode di alcune speciali proprietà. Prima di tutto, la distanza tra due stringhe non è mai negativa. Secondo, due stringhe identiche hanno distanza zero l'una dall'altra. Terzo, la distanza da a a b è uguale alla distanza da b ad a. Infine, se la distanza da a a b è pari a x, e la distanza da b a c è pari a y, allora la distanza da a a c è sicuramente minore di x+y. Quest'ultima proprietà viene chiamata disuguaglianza triangolare, perché, se ci fate caso, il lato di un triangolo è sempre meno lungo della somma degli altri due.
Tutte queste proprietà messe insieme rendono la distanza di Hamming un ottimo meccanismo per misurare la distanza tra due "parole": i matematici esprimono questo concetto dicendo che si tratta di una "metrica" nello spazio delle stringe di lunghezza n.
La distanza di Hamming è molto utilizzata in informatica, in teoria dell'informazione, nelle telecomunicazioni, nella teoria dei codici e nella crittografia (ed ecco che torna alla memoria il grande Turing).

I miei lettori si staranno chiedendo: va bene, ma se dobbiamo confrontare due stringhe di lunghezza diversa? Ottima domanda. A questo scopo la distanza di Hamming non va più bene, e dobbiamo usare quella di Levenshtein, proposta nel 1965 dal russo Vladimir Levenshtein. In questo caso la distanza è pari al numero minimo di modifiche elementari che consentono di trasformare una stringa nell'altra: solo che oltre alla trasformazione di un simbolo in un altro, è permesso anche inserire un nuovo simbolo o cancellare un simbolo.
(Se ci pensate, queste trasformazioni assomigliano molto a quelle della "Pagina della Sfinge" della Settimana Enigmistica: cambio di lettera, aggiunta di lettera, scarto di lettera.)

Concludo questo post con un paio di frasi molto sagge di Richard Hamming:

The purpose of computing is insight, not numbers. 
(Lo scopo della computazione è la comprensione, non i numeri.)

We live in an age of exponential growth in knowledge, and it is increasingly futile to teach only polished theorems and proofs. We must abandon the guided tour through the art gallery of mathematics, and instead teach how to create the mathematics we need. In my opinion, there is no long-term practical alternative.
(Viviamo in un'epoca di crescita esponenziale della conoscenza, ed è sempre più inutile insegnare soltanto bei teoremi e dimostrazioni. Dobbiamo abbandonare l'idea della visita guidata nella galleria d'arte della matematica, e piuttosto insegnare come creare la matematica di cui abbiamo bisogno. A mio parere, non c'è alternativa pratica a lungo termine.)