Turing machine for unary increment
This Turing machine adds one to a number written in unary. A unary input of 111 represents three. Starting in q0, the head reads each 1, writes 1 back unchanged and moves right. When it reaches the first blank cell B, it writes a new 1 and enters accepting state qa. The final tape therefore contains 1111, which represents four. Its two transitions show the standard information on a Turing machine edge: the tape symbol read, the symbol written and the head motion. S means stay on the current cell. Although this is a very small machine, it is a complete computation with an explicit halting condition.
Open it in the AI editor with a prompt pre-filled — keep what works, change what doesn't.
Scenario
Unary arithmetic
Key decisions
- Scan state: q0 preserves each unary mark while moving right.
- Blank detection: B marks the end of the current number.
- Halting write: qa is reached after the new final 1 is written.
When to reuse this
Use this machine to introduce the read/write/move notation of a Turing machine.
Frequently asked questions
What does 1/1,R mean?
Why does the machine write on B?
What does S mean?
More computability theory examples
Try the diagram makers.
Tweak it with chat, export PNG/SVG, or fork it for your own use case.