---
title: "Multitape TM as copying machine"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-multitape-copy"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-multitape-copy
site: BCT Engineering
---

# Multitape TM as copying machine

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2074 Asoj
- Video: [Multitape Turing Machine](https://www.youtube.com/watch?v=CLLutxGVDY4) — Neso 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-multitape-copy
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Design a multitape Turing machine which acts as a copying machine over the alphabet Σ = {0,1}* that transforms the string #10# into #10#10#.

## Short answer

A two-tape TM copies the input #10# from tape 1 to tape 2, repositions both heads, then copies from tape 2 back to tape 1 after the first #, resulting in #10#10#. Phase 1 duplicates w onto tape 2, phase 2 appends it to tape 1.

## Answer

Use a **two-tape** machine. Tape 1 holds the input #10# and also receives the final answer #10#10#. Tape 2 is used as a work tape. Both heads start at the left # (S = stay).

**Idea.**
1. Phase 1: copy w from tape 1 onto tape 2 (also writing # first), moving both heads right together.
2. At the final # of tape 1, rewind head 2 to the start of its copy.
3. Phase 2: step head 1 past the final # and copy w from tape 2 onto the blank cells of tape 1. At the end, write the closing #.

M = ({q0, q1, q2, q3, qa}, {0, 1, #}, {0, 1, #, ⊔}, δ, q0, ⊔, {qa}). Each rule reads (tape 1, tape 2) and writes (tape 1, tape 2) with moves (head 1, head 2).

| State | Read (T1, T2) | Write (T1, T2) | Moves | Next |
|---|---|---|---|---|
| q0 | (#, ⊔) | (#, #) | R, R | q1 |
| q1 | (0, ⊔) | (0, 0) | R, R | q1 |
| q1 | (1, ⊔) | (1, 1) | R, R | q1 |
| q1 | (#, ⊔) | (#, ⊔) | S, L | q2 |
| q2 | (#, 0) or (#, 1) | same | S, L | q2 |
| q2 | (#, #) | (#, #) | R, R | q3 |
| q3 | (⊔, 0) | (0, 0) | R, R | q3 |
| q3 | (⊔, 1) | (1, 1) | R, R | q3 |
| q3 | (⊔, ⊔) | (#, ⊔) | S, S | qa |

#### Run on #10#
```text
After phase 1:  T1: # 1 0 #          T2: # 1 0
                      head1 on 2nd #     head2 after the 0
q1 -> q2: head 2 moves left over 0, 1 to the # of T2
q2 -> q3: head 1 steps right off the # onto a blank,
          head 2 steps onto the 1
q3: copies 1, then 0, to T1 :   T1: # 1 0 # 1 0
q3 sees (⊔, ⊔): writes # :      T1: # 1 0 # 1 0 #   -> halt
```
Final tape 1: **#10#10#**. The machine takes about 3|w| steps.

## Check yourself

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

1. What is tape 2 used for?
   A. Holds the final answer
   B. A work tape holding a copy of w
   C. Stores the state
   D. Nothing
   Answer: B. w is copied onto tape 2, then copied back onto tape 1 after the final #. (Key point: Tape roles)

2. What happens in phase 1?
   A. w is copied from tape 1 to tape 2 with both heads moving right
   B. w is erased
   C. Head 2 moves left
   D. A # is added
   Answer: A. Both heads move right together while tape 2 receives a copy. (Key point: Phase 1)

3. How is #10#10# completed?
   A. Head 2 is rewound, then w is copied from tape 2 to blank cells of tape 1 and a closing # written
   B. Tape 1 is duplicated
   C. The tapes are swapped
   D. Head 1 is rewound
   Answer: A. After rewinding head 2, w is appended after the first # of tape 1 and a final # is written. (Key point: Phase 2)

4. About how many steps does it take?
   A. About 3|w|
   B. About |w|^2
   C. 2^|w|
   D. |w|!
   Answer: A. Copy forward, rewind and copy back give linear time. (Key point: Efficiency)

## Related in Theory of Computation

- [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 configuration; TM for palindromes](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-config-palindrome) — Theory of Computation, chapter 4
- [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
- [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

## Related in other subjects

- [Check string consists of alphabet only](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Astring-alphabet-check) — Computer Programming, chapter 7
- [Insulator discs per string, 180 MW over 200 km](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Ainsulator-discs-180mw-200km) — Transmission and Distribution System Design, chapter 3
- [Initial line design for 200 MW over 120 km](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aline-design-200mw-120km) — Transmission and Distribution System Design, chapter 2
- [String efficiency: 66 kV, 4 discs, 10%](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Astring-efficiency-66kv-4-discs) — Power System Analysis I, chapter 2, asked 2×