--- title: "Two-tape TM as binary adder" subject: "Theory of Computation" chapter: 4 key: "semester_3/theory_of_computation:tm-two-tape-binary-adder" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-two-tape-binary-adder site: BCT Engineering --- # Two-tape TM as binary adder Theory of Computation · Chapter 4: Turing Machine - Asked in: 2073 Shrawan - Video: [Turing Machine for addition of two numbers || GATECSE || TOC](https://www.youtube.com/watch?v=KoAXrBCPkRs) — THE GATEHUB - 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-two-tape-binary-adder - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4 ## Question Design a two tape Turing machine that acts as a binary adder. ## Short answer The TM positions both tape heads at the least significant bits, then adds digit by digit with a carry state. It writes the sum bit on tape 1, updates carry, and moves left, halting when both tapes are blank, writing a final carry if 1. ## Answer **Setup.** Tape 1 holds binary number A and tape 2 holds binary number B (most significant digit on the left, blanks elsewhere), each head starting on the leftmost digit. The sum is written on tape 1 (overwriting A); tape 2 is unchanged. S means the head stays. **Idea.** Add from the least significant digit, as in school arithmetic, carrying through the state. A blank counts as 0. 1. Phase 1 (state q0): move each head to the right end of its own number (a head that already sees a blank stays). 2. Phase 2 (states c0, c1 = carry 0 or 1): read (x, y), compute s = x + y + carry; write s mod 2 on tape 1; the new carry is s div 2; move both heads left (head 2 stays when on a blank). 3. When both heads read blank: if the carry is 1, write 1 on tape 1; halt. M has states {q0, c0, c1, qa} and tape alphabet {0, 1, ⊔}. Rules (digit x on tape 1, y on tape 2): | State | (x, y) | Write on T1 | Moves | Next state | |---|---|---|---|---| | q0 | (0/1, 0/1) | same | R, R | q0 | | q0 | (0/1, ⊔) | same | R, S | q0 | | q0 | (⊔, 0/1) | same | S, R | q0 | | q0 | (⊔, ⊔) | same | L, L | c0 | | c0 | (0,0) | 0 | L, L | c0 | | c0 | (0,1) or (1,0) | 1 | L, L | c0 | | c0 | (1,1) | 0 | L, L | c1 | | c1 | (0,0) | 1 | L, L | c0 | | c1 | (0,1) or (1,0) | 0 | L, L | c1 | | c1 | (1,1) | 1 | L, L | c1 | | c0 | (⊔,⊔) | – | S, S | qa | | c1 | (⊔,⊔) | 1 | S, S | qa | In the c0/c1 digit rows a blank is treated as 0 (for example (⊔,1) behaves as (0,1)), and head 2 stays instead of moving left once it reads a blank. ```text ──► (q0) ──(both ⊔) L,L──► (c0) ◄──► (c1) ↺ moves heads │ │ to the right ends └─(⊔,⊔)─► ((qa)) ``` #### Example: 101 + 11 (5 + 3 = 8) ```text digit x y carry write new carry 1 1 1 0 0 1 2 0 1 1 0 1 3 1 ⊔ 1 0 1 end ⊔ ⊔ 1 1 (write carry) ``` Tape 1 becomes **1000** = 8. First q0 runs both heads to the right ends; each row above is then one move of the adder states. The machine runs in about 2·max(|A|, |B|) steps. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why does the adder start from the right end? A. Addition begins at the least significant digit B. The most significant digit is on the right C. To count digits D. To erase B Answer: A. Carries propagate from the least significant digit, as in school arithmetic. (Key point: Direction) 2. What do states c0 and c1 represent? A. Carry 0 and carry 1 B. Tape 1 and tape 2 C. Accept and reject D. Digit 0 and 1 Answer: A. The carry is remembered in the control state. (Key point: Carry states) 3. In state c1 reading (1,1), what is written and the next state? A. 0 and c0 B. 1 and c1 C. 1 and c0 D. 0 and c1 Answer: B. 1 + 1 + 1 = 3, so write 1 and carry 1. (Key point: Rule) 4. When both heads read blank in c1, what happens? A. Writes 1 on tape 1 and halts B. Rejects C. Writes 0 D. Moves left Answer: A. The final carry becomes the leading digit; 101 + 11 gives 1000. (Key point: End) ## Related in Theory of Computation - [TM for aⁿcbⁿ (single tape, deterministic)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-an-c-bn) — Theory of Computation, chapter 4 - [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 - [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 ## Related in other subjects - [3-bit multiplier with binary parallel adder](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Abinary-multiplier-3bit) — Digital Logic, chapter 5 - [Short note: binary parallel adder](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Ashort-note-binary-parallel-adder) — Digital Logic, chapter 5 - [Two 4-bit parallel adder](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Aparallel-adder-4bit) — Digital Logic, chapter 5 - [4-bit multiplier with parallel adder](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Abinary-multiplier-4bit) — Digital Logic, chapter 5