Michael O. Rabin: L'uomo che ha reso i computer a proprio agio con il caso

Intorno ai dieci o undici anni, nella Palestina sotto mandato britannico, Michael Rabin risolse un problema di geometria che aveva messo in difficoltà studenti molto più grandi di lui — un piccolo segno precoce di una mente che avrebbe trascorso il resto del secolo a trovare percorsi eleganti e inaspettati attraverso problemi che tutti gli altri presumevano richiedessero una certezza assoluta. La mossa distintiva di Rabin, ripetuta nella teoria degli automi, nella crittografia e nella teoria dei numeri, è stata quella di notare che dare a una macchina il permesso di indovinare, o di lanciare una moneta, poteva renderla più potente anziché meno affidabile — un'idea considerata quasi eretica quando la propose per la prima volta.

Da Breslavia a una famiglia rabbinica in Palestina

Rabin è nato il 1° settembre 1931 a Breslavia, allora in Germania e oggi Wrocław, in Polonia. Suo padre, un rabbino, trasferì la famiglia in Palestina nel 1935, prima del peggio di ciò che stava per accadere in Europa. Ha frequentato la Hebrew Reali School di Haifa, studiando sotto il matematico Elisha Netanyahu, che in seguito divenne professore al Technion, e già da adolescente lavorava a seminari di matematica avanzata. Ha conseguito un master in matematica presso l'Università Ebraica di Gerusalemme nel 1953, con una tesi che ha risolto un problema aperto originariamente posto da Emmy Noether, prima di trasferirsi negli Stati Uniti per un dottorato a Princeton, completato nel 1957 sotto la guida del logico Alonzo Church.

Una macchina che può indovinare

Il primo articolo importante di Rabin, scritto con Dana Scott e pubblicato nel 1959 come "Finite Automata and Their Decision Problems", ha introdotto il concetto di automa a stati finiti non deterministico — una macchina teorica che, incontrando un input, poteva effettivamente ramificarsi in più copie di se stessa e perseguire diversi percorsi computazionali possibili contemporaneamente. L'articolo ha dimostrato che queste macchine non deterministiche erano, nonostante sembrassero molto più potenti, esattamente equivalenti in ciò che potevano calcolare alle normali macchine deterministiche, un risultato fondamentale che ha rimodellato il modo in cui l'informatica pensa alla computazione stessa. L'Association for Computing Machinery ha assegnato a Rabin e Scott il Turing Award nel 1976 specificamente per quell'articolo — il più alto riconoscimento dell'informatica, per un lavoro teorico scritto quando Rabin non aveva ancora trent'anni.

Insegnare al caso a essere affidabile

Rabin è tornato più volte a un'idea correlata e più strana: che iniettare deliberatamente casualità in un calcolo potesse renderlo più veloce o più semplice, senza renderlo inaffidabile. Ai Bell Labs intorno al 1960 ha introdotto automi probabilistici che usavano il lancio di monete per decidere le transizioni di stato, dimostrando che potevano rappresentare determinati linguaggi con un numero di stati esponenzialmente inferiore rispetto a qualsiasi macchina deterministica. Quell'intuizione è maturata, nel 1975, nel test di primalità di Miller-Rabin, un algoritmo randomizzato — basato sul precedente lavoro deterministico di Gary Miller — per determinare se un numero enorme è primo, abbastanza veloce e affidabile da sostenere i sistemi di crittografia utilizzati su Internet oggi; la versione di Rabin ha notevolmente rimosso la dipendenza di Miller dall'ipotesi di Riemann generalizzata non dimostrata. Il premio Kanellakis del 2003 ha riconosciuto il contributo condiviso di Miller, Rabin, Robert Solovay e Volker Strassen a questa linea di lavoro.

Serrature costruite con la matematica difficile

La crittografia di Rabin è andata oltre il test dei numeri primi. Nel 1978 ha ideato il crittosistema di Rabin, notevole come primo schema di crittografia asimmetrica la cui sicurezza poteva essere dimostrata matematicamente equivalente alla difficoltà di fattorizzare grandi numeri interi — una garanzia più forte di quanto la maggior parte dei crittosistemi dell'epoca potesse vantare. Nel 1981 ha formalizzato l'oblivious transfer, un protocollo crittografico che consente di inviare informazioni in modo che il mittente non possa sapere se il destinatario le abbia effettivamente ottenute, che è diventato un elemento costitutivo per il calcolo multipartitico sicuro. Nel 1987, con Richard Karp, ha co-sviluppato l'algoritmo di ricerca di stringhe Rabin-Karp, una tecnica di rolling hash ancora insegnata nei corsi di algoritmi universitari per la sua efficienza nel trovare un pattern all'interno di un grande corpo di testo.

Una carriera divisa tra due paesi

La vita accademica di Rabin si è svolta su binari paralleli tra Israele e Stati Uniti. All'Università Ebraica di Gerusalemme è passato da docente senior a professore ordinario all'inizio dei trent'anni, ha presieduto l'Istituto di Matematica ed è stato rettore dell'università dal 1972 al 1975. Negli Stati Uniti ha ricoperto la Gordon McKay Professorship e poi la Thomas J. Watson Sr. Professorship ad Harvard dal 1981 in poi, insieme a incarichi di visiting professor al MIT, Berkeley e Columbia. È stato eletto membro della U.S. National Academy of Sciences, dell'American Academy of Arts and Sciences, dell'American Philosophical Society, dell'Accademia francese delle scienze e della Royal Society, e ha vinto il Premio Israele nel 1995 e il Premio Dan David nel 2010, oltre a onorificenze tra cui l'IEEE Charles Babbage Award e il premio Dijkstra.

Perché Michael è chiamato un genio

Il caso di Rabin come genio si basa su una firma riconoscibile in una carriera di cinquant'anni: identificare ripetutamente che un problema che si presumeva richiedesse certezza poteva invece essere risolto più velocemente, o reso più potente, introducendo deliberatamente casualità o non determinismo — un'intuizione che all'inizio colpì i contemporanei come un errore di categoria, poiché la casualità era ampiamente trattata come il nemico del calcolo affidabile piuttosto che come una risorsa. Quell'intuizione, applicata indipendentemente alla teoria degli automi, ai test di primalità e alla progettazione di protocolli crittografici, ha prodotto risultati che, presi singolarmente, segnerebbero una carriera sostanziale; produrne diversi è ciò che il comitato del Turing Award e la serie di premi successivi Kanellakis, Babbage e Dijkstra stavano esplicitamente onorando. Ci sono pochi contro-casi seri nel registro: a differenza di alcuni vincitori del Turing la cui reputazione poggia su un solo articolo, quella di Rabin è costruita su risultati verificati indipendentemente e ancora utilizzati nel corso dei decenni — il test di Miller-Rabin viene eseguito oggi all'interno di librerie crittografiche, non solo nei libri di testo. Se c'è un avvertimento, è solo che il suo articolo singolo più famoso, con Scott, è nato da un vero partenariato, un promemoria che anche l'intuizione individuale più acuta in questo campo è solitamente arrivata attraverso la collaborazione piuttosto che attraverso il genio solitario.

Eredità

Rabin è morto il 14 aprile 2026, a novantaquattro anni, avendo trascorso i suoi ultimi anni ancora associato sia ad Harvard che all'Università Ebraica come professore emerito in entrambe. Sua figlia, Tal Rabin, è diventata una distinta crittografa a pieno titolo, portando la particolare fascinazione della famiglia per la casualità e la segretezza in una nuova generazione. Gli algoritmi che portano il suo nome — Miller-Rabin, Rabin-Karp, il crittosistema di Rabin — rimangono in uso attivo e quotidiano ovunque un computer debba testare un numero, cercare una stringa o mantenere un segreto, un raro caso di informatica teorica fondamentale che svolge ancora un lavoro quotidiano visibile decenni dopo essere stato scritto.