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.