Definition
Plain language
A simple abstract machine that's always in one of a fixed set of states and jumps between them based on its input.
As stated in the literature
A computational model with a finite set of states and transition rules over inputs; used as a controlled deterministic state-tracking task to probe whether models can reliably simulate sequential computation.
Also called: finite-state machines
Why it matters: It matters as a clean, controlled task for testing whether a model can faithfully simulate step-by-step computation.
For example, a turnstile is a finite-state machine: it sits in 'locked' until a coin flips it to 'unlocked', and a push flips it back.
Heard on the show
“Simulating a little finite-state machine.”Episode 108 — The Reasoning Cliff: Why Thinking Longer Makes Models Worse at Exact Step-by-Step Tasks