1976 · Theory & algorithms

Many possible paths, one precise model

Nondeterministic automata made branching computation mathematically tractable.

Dana Scott · Michael Rabin

1976Turing Award

Visual guide

The prize, pictured

Open full-size ↗Download poster ↓中文版海报 ↗

Many possible paths, one precise model: Nondeterministic automata made branching computation mathematically tractable. — Original AI-generated infographic by Curionode. Read the text version below for the full explanation.

Read the poster text

Read
Take the next input symbol.
Branch
Follow allowed state transitions.
Accept
Check whether a path succeeds.

Automata theory underlies tools for recognising patterns, analysing languages and reasoning about computational models.

Nondeterminism is a mathematical model, not a claim that a physical computer gets unlimited parallel work for free.

01 · The idea

In everyday language

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.

02 · The people

Who brought the idea to life?

Dana Scott

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.

Read the biography ↗

Michael Rabin

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.

Read the biography ↗

03 · Read further