01 · A life in computing
The person behind the work
Michael Rabin helped establish the mathematical foundations of automata and algorithms. His joint work with Dana Scott showed how nondeterministic finite machines could recognize the same languages as deterministic ones. He later pioneered randomized algorithms and made important contributions to cryptography. His long association with the Hebrew University of Jerusalem included research leadership and service as rector, alongside a later professorship at Harvard.
The contribution, explained
Michael Rabin and Dana Scott studied finite automata: machines whose behaviour can be described using a finite collection of states. Nondeterminism allows several possible next moves. A string is accepted if some allowed path reaches an accepting state. For finite automata, this expressive-looking model can be converted into a deterministic one.
Why it matters
Automata theory underlies tools for recognising patterns, analysing languages and reasoning about computational models.