---
title: "TM that doubles a binary number"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-doubles-binary"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-doubles-binary
site: BCT Engineering
---

# TM that doubles a binary number

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2071 Chaitra
- 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-doubles-binary
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Design a Turing machine that reads a binary string and doubles the number represented by that string. A binary number is doubled if a 0 is added on the right end of the number.

## Short answer

Doubling a binary number appends a 0 on the right. The TM moves right over digits until a blank, writes 0, and halts. For input 101, output is 1010 (decimal 10).

## Answer

**Idea.** Doubling a binary number appends a 0 on the right. So the machine moves right over the digits to the first blank, writes 0 there and halts.

M = ({q0, qa}, {0, 1}, {0, 1, ⊔}, δ, q0, ⊔, {qa}), with S = stay.

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | 0 | 0 | R | q0 |
| q0 | 1 | 1 | R | q0 |
| q0 | ⊔ | 0 | S | qa |

```text
   0/0,R   1/1,R
      ↺
 ──► (q0) ── ⊔/0,S ──► ((qa))
```

#### Example: input 101 (decimal 5, doubled 10 = 1010)
```text
[q0]101   -> 1[q0]01 -> 10[q0]1 -> 101[q0]⊔
-> 101[qa]0      tape: 1010   (decimal 10)
```
The machine halts with 1010 on the tape. For the empty input it writes 0, which is also correct since 2 × 0 = 0. The machine runs in n + 1 steps for an input of length n.

## Check yourself

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

1. Why does appending a 0 double a binary number?
   A. Shifting left by one bit multiplies the value by 2
   B. It adds 2
   C. It adds the number to itself bitwise
   D. It reverses the bits
   Answer: A. Writing a 0 on the right shifts every bit one place left, which multiplies by 2. (Key point: Key idea)

2. What does state q0 do on reading 0 or 1?
   A. Writes 0 and stops
   B. Rewrites the same symbol and moves right
   C. Moves left
   D. Changes 1 to 0
   Answer: B. q0 scans right over the digits unchanged until it reaches the first blank. (Key point: Machine behaviour)

3. What happens on reading the blank in q0?
   A. Writes 0, stays and goes to qa
   B. Moves left
   C. Rejects
   D. Writes 1
   Answer: A. The blank is replaced by 0 and the machine halts in qa. (Key point: Final move)

4. For input 101 the tape at the end is
   A. 1010
   B. 1011
   C. 110
   D. 10100
   Answer: A. 5 doubled is 10, which is 1010. (Key point: Result)

## Related in Theory of Computation

- [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
- [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
- [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4
- [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4
- [How a universal Turing machine works](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Auniversal-tm-example) — Theory of Computation, chapter 5
- [TM computing f(n) = n + 1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-increment-binary) — Theory of Computation, chapter 4

## Related in other subjects

- [Choice of number of poles in DC machine](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Adc-number-of-poles) — Electric Machine Design, chapter 5, asked 8×
- [Number conversions 33 to binary etc.](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Anumber-conversion-2067-chaitra) — Basic Electronics Engineering, chapter 6
- [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×