Automata and Turing machines
A Turing machine has a reputation for being an abstract, intricate thing. These three pages argue the opposite: the whole point of the model is that something this small — a handful of states, a transition table a reader can read on one screen — is already enough to compute a function or decide a language. The first page adds one to a binary number, carry and all, with just three states and six rules. The second decides whether a string reads the same forwards and backwards, which costs noticeably more machine for a noticeably harder kind of task. The third page has no tape at all — a deterministic finite automaton deciding whether a binary number is a multiple of three — which is the clearest way to see what a tape actually buys a Turing machine over a language acceptor with no scratch space.
- Binary incrementerA three-state, six-rule Turing machine that adds one to a binary number on its own tape: scan right to the end, then carry left.O(n)O(n)
- Binary palindrome checkerAn eight-state, 28-rule Turing machine deciding whether a binary string reads the same forwards and backwards, by repeatedly marking and comparing its two ends.O(n²)O(n)
- Divisible by threeA three-state DFA deciding whether a binary number is a multiple of three, with no tape at all beyond the input itself.O(n)O(1)
Automata built directly from a pattern, by a construction algorithm rather than by hand, are inRegular expressions. The bits a tape symbol is ultimately made of are inBits, floats, text and encodings.