Skip to main content

TM that doubles a binary 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).

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.

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.

StateReadWriteMoveNext
q000Rq0
q011Rq0
q0⊔0Sqa
   0/0,R   1/1,R
      ↺
 ──► (q0) ── ⊔/0,S ──► ((qa))

Example: input 101 (decimal 5, doubled 10 = 1010)

[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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 4 questions →