Skip to main content

TM computing f(n) = n + 1

Short answer

The TM scans right to the end of the binary string, then moves left flipping 1s to 0 (carry) until it finds a 0 or blank, writes 1, and halts. For input 10111, the output is 11000 (decimal 24).

Design a TM to compute f(n) = n + 1, where n is a binary string. Show the processing for 10111.

Idea. A binary number n is written with the most significant bit on the left. To add 1, go to the right end, then move left: change each 1 to 0 (carry) until a 0 or the blank is found, and change that to 1.

M = (Q, Σ, Γ, δ, q0, ⊔, F) with Q = {q0, q1, qa}, Σ = {0, 1}, Γ = {0, 1, ⊔}, F = {qa}. (S means the head stays.)

StateReadWriteMoveNext
q00 / 1sameRq0
q0⊔⊔Lq1
q110Lq1
q101Sqa
q1⊔1Sqa
  • q0: scan right to the end of the number.
  • q1: carry state, moving left.
        0,1 → R                1 → 0, L
          ↺                      ↺
 ──► (q0) ── ⊔,⊔ / L ──► (q1) ──0 → 1 (S)──► ((qa))
                                │
                                └── ⊔ → 1 (S) ──► ((qa))

Processing 10111 (n = 23, answer 24 = 11000)

[q0]10111
1[q0]0111
10[q0]111
101[q0]11
1011[q0]1
10111[q0]
1011[q1]1
101[q1]10
10[q1]100
1[q1]0000
1[qa]1000

Reading: q0 scans to the right end, q1 turns the trailing 111 into 000 (carry), then meets 0 and writes 1. The tape holds 11000, i.e. 24.

Special case: for 111 the carry reaches the blank at the left, where q1 writes 1, giving 1000 (7 + 1 = 8).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 4 questions →