- 2074 Asoj
Multitape TM as copying machine
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.
Design a multitape Turing machine which acts as a copying machine over the alphabet Σ = {0,1}* that transforms the string #10# into #10#10#.
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.
- Phase 1: copy w from tape 1 onto tape 2 (also writing # first), moving both heads right together.
- At the final # of tape 1, rewind head 2 to the start of its copy.
- 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#
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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Define multitape Turing machine · Theory of Computation, chapter 4
- What is a Turing machine; its operation · Theory of Computation, chapter 4
- How a universal Turing machine works · Theory of Computation, chapter 5
- TM configuration; TM for palindromes · Theory of Computation, chapter 4
- TM for aⁿcbⁿ (single tape, deterministic) · Theory of Computation, chapter 4
- Two-tape TM as binary adder · Theory of Computation, chapter 4
- Check string consists of alphabet only · Computer Programming, chapter 7
- Insulator discs per string, 180 MW over 200 km · Transmission and Distribution System Design, chapter 3
- Initial line design for 200 MW over 120 km · Transmission and Distribution System Design, chapter 2
- String efficiency: 66 kV, 4 discs, 10% · Power System Analysis I, chapter 2 · asked 2×