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.

Tipo Diagramma degli statiStandard OMG UML 2.5.1 §14 + Harel (1987) statechartMotore schematex-stateAggiornato 24/09/2026

La richiesta

“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.”

Prova alloraChange the machine to erase the final unary 1 instead.Add a rejecting state for an input symbol 0.

Cosa contiene questo disegno

Leggi le decisioni che ne stanno alla base.

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.

Sfoglia tutti i modelli di tipo diagramma degli stati →

FAQ

Domande frequenti

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.