01 · A life in computing
The person behind the work
Dana Scott is a logician whose research connected mathematical logic with the foundations of programming. With Michael Rabin he introduced nondeterministic finite automata and proved their relationship to deterministic machines. His later collaboration with Christopher Strachey helped develop denotational semantics, giving mathematical meanings to programs. His career spanned several universities; he was at Oxford when the joint 1976 Turing Award recognized the automata work.
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.