Skip to main content

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.

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

StateRead (T1, T2)Write (T1, T2)MovesNext
q0(#, ⊔)(#, #)R, Rq1
q1(0, ⊔)(0, 0)R, Rq1
q1(1, ⊔)(1, 1)R, Rq1
q1(#, ⊔)(#, ⊔)S, Lq2
q2(#, 0) or (#, 1)sameS, Lq2
q2(#, #)(#, #)R, Rq3
q3(⊔, 0)(0, 0)R, Rq3
q3(⊔, 1)(1, 1)R, Rq3
q3(⊔, ⊔)(#, ⊔)S, Sqa

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)

All Theory of Computation chapter 4 questions →