Michael O. Rabin

Prix

1. 1976

   prix Turing

   Informatique

   for their joint paper ' Finite automata and their decision problem', which introduced the idea of nondeterministic machines