Turing Machine for Binary Increment

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.

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

La richiesta

“Draw a Turing machine that adds one to a binary number: qScan moves right over 0 and 1, moves left on blank B, qCarry changes trailing 1s to 0 while moving left, then changes a 0 or leading blank to 1 and accepts.”

Prova alloraAdd a reject state for an input symbol other than 0 or 1.Change the final move from stay to move right.

Cosa contiene questo disegno

Leggi le decisioni che ne stanno alla base.

01Right scan

qScan finds the right edge of the binary word.

02Carry loop

every trailing 1 becomes 0 while the carry moves left.

03Overflow case

a blank becomes 1 when the input contains only 1s.

Use this state pattern to explain how a Turing machine implements binary addition one tape cell at a time.

Sfoglia tutti i modelli di tipo diagramma degli stati →

FAQ

Domande frequenti

Why are trailing 1s changed to 0?

Adding one to a binary 1 produces 0 with a carry into the digit to its left.

What happens to 111?

The carry runs past the left edge and writes a new 1, producing 1000.

Why does qScan move right first?

Binary addition starts at the least significant digit, which is at the right end of the input.