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.

유형 상태 다이어그램표준 OMG UML 2.5.1 §14 + Harel (1987) statechart엔진 schematex-state업데이트됨 2026. 9. 24.

요청 내용

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

그렇다면Add a reject state for an input symbol other than 0 or 1.Change the final move from stay to move right.

이 도면에 담긴 내용

그 이면의 의사결정을 읽어 보세요.

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.

모든 상태 다이어그램 템플릿 보기 →

자주 묻는 질문

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.