Library

Collection · 13 machines · curated by @thethinkmachine

Nondeterminism: the power to guess

Machines that guess and then check: where the end is, which letter repeats, where the middle of a palindrome lies, which items add up to the target. Some guesses save exponentially many states, some add real power, and some only make a machine easier to write.

Essay

2 min read · 1 figure

A nondeterministic machine may have several moves available and accepts if some sequence of choices leads to acceptance. It is easiest to think of it as guessing — and always guessing right, when there is a right guess. Whether that ability adds anything depends on the machine, and the answer is different at every level.

Machine Does guessing add power? What it can cost to remove
finite automaton no exponentially many states
pushdown automaton yes —
Büchi automaton yes —
co-Büchi, parity, weak no many states
Turing machine no possibly exponential time — the P versus NP question

Finite automata: smaller, not stronger

The third symbol from the end guesses where the end is. Some letter occurs twice guesses which letter and where it first appears. A square of length 4 guesses where it starts. Every NFA can be determinised by the subset construction — a state of the DFA is the set of states the NFA could be in — and sometimes all 2ⁿ subsets are needed. Lengths divisible by 3 or 5 guesses which cycle to run, at a cost of 3 + 5 states where the DFA needs 15.

Pushdown automata: genuinely stronger

An even palindrome needs the machine to guess the middle; no deterministic pushdown automaton recognises the even palindromes. aⁱbʲcᵏ with i = j or j = k needs it to guess which pair to match, and the language is inherently ambiguous: every grammar for it has strings with two parse trees.

Transducers: looking ahead

A finite transducer that guesses can act on information it has not read yet, as long as the wrong guesses die. Replacing the last letter bets on every letter being the last; thousands separators bets on the length mod 3. One branch survives, and its output is the answer.

ω-automata: the one surprise

For infinite words, guessing adds power to Büchi automata and to nothing else. Eventually always b must guess when the a’s have stopped, and no deterministic Büchi automaton can do without the guess.

Turing machines: certificates

A nondeterministic Turing machine decides nothing that a deterministic one cannot — it can be simulated by trying every branch. The question is how long that takes. Subset sum and compositeness are decided in a few passes once the right items or the right factor are guessed; trying every guess is exponential. Whether that is ever necessary is the P versus NP problem.

Figure 1. Guess the end, guess the middle, guess the subset.

The machines