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.)