Binary incrementer
A Turing machine with three states and six transition rules. It scans right past every digit of a binary number to find the first blank cell past it, then walks back left, flipping each trailing 1 to a 0 — the carry — until it meets a 0 (which it flips to 1, absorbing the carry) or runs off the left end of the number entirely, in which case it writes a brand new leading 1 in the blank cell that was waiting there.
When it is the right choice
As the first thing to show anyone who thinks "Turing machine" necessarily means something large or intricate. This one does a real, checkable job — it computes n + 1 in binary, correctly, for every canonical binary number it accepts — with a transition table a reader can read in full on one screen.
How it works
- Start in state q0 with the head at the first digit.
- While reading a 0 or 1, move right, staying in q0, until the first blank cell past the number.
- At that blank, move left and switch to q1: this is where the carry starts.
- While reading a 1 in q1, write 0 and keep moving left — the carry continues.
- The first 0 the carry reaches is flipped to 1, and the machine halts.
- If the carry instead reaches the blank to the left of the very first digit (every digit was a 1), a new leading 1 is written there and the machine halts.
Worth noticing
- The default scenario, 111 → 1000, is the one to watch closely: the carry propagates through every digit, and the tape genuinely needs a cell that was not part of the original input at all. That is the concrete, hand-verifiable version of "a Turing machine’s tape is unbounded".
- The machine has exactly one halting state, qH, and no notion of accept or reject — it computes a function (a new tape), rather than deciding a language the way the other two pages on this tool do.
- Every rule the machine fires is highlighted on the transition table at the same moment it is drawn on the state diagram and the tape, so "which rule just fired" is never a separate fact from "what just happened on the tape".
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)