Turing machine for binary increment
This machine increments a binary number by one. State qScan moves right over the input until it reaches a blank B immediately after the final digit. It then moves one cell left and enters qCarry. In qCarry, every trailing 1 is replaced by 0 while the head moves left, carrying the addition toward the most significant bit. When it finds a 0, the machine writes 1 and accepts. If it instead finds a blank, the original word consisted entirely of 1s, so it writes a new leading 1. For example, 1011 becomes 1100 and 111 becomes 1000. Each edge label makes the tape operation explicit.
Open it in the AI editor with a prompt pre-filled — keep what works, change what doesn't.
Scenario
Binary carry propagation
Key decisions
- Right scan: qScan finds the right edge of the binary word.
- Carry loop: every trailing 1 becomes 0 while the carry moves left.
- Overflow case: a blank becomes 1 when the input contains only 1s.
When to reuse this
Use this state pattern to explain how a Turing machine implements binary addition one tape cell at a time.
Frequently asked questions
Why are trailing 1s changed to 0?
What happens to 111?
Why does qScan move right first?
More computability theory examples
Try the diagram makers.
Tweak it with chat, export PNG/SVG, or fork it for your own use case.