---
title: "TM computing f(n) = n + 1"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-increment-binary"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-increment-binary
site: BCT Engineering
---

# TM computing f(n) = n + 1

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Chaitra
- Video: [Design Turing Machine | Compute Function | f(n)=n+1 | TOC | TAFL | Automata](https://www.youtube.com/watch?v=6wvJO8da0qA) — CSE ACADEMY
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-increment-binary
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

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

## 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).

## Answer

**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.)

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | 0 / 1 | same | R | q0 |
| q0 | ⊔ | ⊔ | L | q1 |
| q1 | 1 | 0 | L | q1 |
| q1 | 0 | 1 | S | qa |
| q1 | ⊔ | 1 | S | qa |

- q0: scan right to the end of the number.
- q1: carry state, moving left.

```text
        0,1 → R                1 → 0, L
          ↺                      ↺
 ──► (q0) ── ⊔,⊔ / L ──► (q1) ──0 → 1 (S)──► ((qa))
                                │
                                └── ⊔ → 1 (S) ──► ((qa))
```

#### Processing 10111 (n = 23, answer 24 = 11000)
```text
[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).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does the TM compute n + 1?
   A. Scan left to the start and add 1 there
   B. Append a 1 at the right end
   C. Go to the right end, then move left changing 1s to 0s until a 0 or blank is found and change it to 1
   D. Change every 0 to 1
   Answer: C. This is binary carry propagation: trailing 1s become 0 and the first 0 (or blank) becomes 1. (Key point: Strategy)

2. What does state q0 do?
   A. Scans right to the end of the number
   B. Propagates the carry
   C. Accepts
   D. Erases the input
   Answer: A. q0 moves right over all digits until a blank, then switches to q1 moving left. (Key point: Role of q0)

3. What is on the tape after processing 10111?
   A. 11000
   B. 10000
   C. 11111
   D. 10110
   Answer: A. 10111 is 23; adding 1 gives 24 = 11000: trailing 111 become 000 and the 0 becomes 1. (Key point: Result for 10111)

4. For input 111, what does q1 do on reaching the left blank?
   A. Rejects
   B. Writes 1 there, giving 1000
   C. Writes 0 there
   D. Moves right again
   Answer: B. The carry runs past all 1s to the blank, which becomes 1: 7 + 1 = 8 = 1000. (Key point: Special case)

## Related in Theory of Computation

- [TM that doubles a binary number](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-doubles-binary) — Theory of Computation, chapter 4
- [Two-tape TM as binary adder](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-two-tape-binary-adder) — Theory of Computation, chapter 4
- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4
- [TM for f(w) = wwᴿ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-f-w-wwr) — Theory of Computation, chapter 4
- [TM for equal numbers of x, y, z](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-equal-xyz) — Theory of Computation, chapter 4
- [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4

## Related in other subjects

- [Significance of convolution; compute convolution](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aconvolution-significance-compute) — Digital Signal Analysis and Processing, chapter 1
- [DIF-FFT butterfly; compute X(2) and X(1)](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adifft-x2-x1-only) — Digital Signal Analysis and Processing, chapter 7
- [5-disc string at 66 kV: nearest and farthest disc](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Afive-discs-66kv-distribution) — Power System Analysis I, chapter 2
- [Coding efficiency: binary, Shannon-Fano and Huffman](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Acoding-efficiency-binary-sf-huffman) — Communication Systems, chapter 6