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.

Type Diagramme d’étatsNorme OMG UML 2.5.1 §14 + Harel (1987) statechartMoteur schematex-stateMis à jour 24/09/2026

La demande

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

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

Ce que contient ce dessin

Comprenez les décisions qui le sous-tendent.

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.

Voir tous les modèles de diagramme d’états →

FAQ

Questions fréquentes

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.