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.