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.