Turing Machine for Unary Increment

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.

種類 状態遷移図規格 OMG UML 2.5.1 §14 + Harel (1987) statechartエンジン schematex-state更新日 2026/9/24

依頼内容

“Draw a Turing machine for unary increment: in q0, read 1, write 1, and move right; on blank B, write 1, stay, and enter accepting qa.”

次はこちらChange the machine to erase the final unary 1 instead.Add a rejecting state for an input symbol 0.

この図に含まれるもの

図の背後にある意思決定を読み解く。

01Scan state

q0 preserves each unary mark while moving right.

02Blank detection

B marks the end of the current number.

03Halting write

qa is reached after the new final 1 is written.

Use this machine to introduce the read/write/move notation of a Turing machine.

状態遷移図のテンプレートをすべて見る →

よくある質問

What does 1/1,R mean?

Read 1, write 1 back to the tape, then move the head one cell right.

Why does the machine write on B?

The first blank marks the end of the unary number, so writing 1 there appends one unit.

What does S mean?

S means stay; the tape head does not move after that transition.