---
title: "TM transforming ⊔w⊔ to ⊔ww⊔"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-copy-w-to-ww"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-copy-w-to-ww
site: BCT Engineering
---

# TM transforming ⊔w⊔ to ⊔ww⊔

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Kartik
- 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-copy-w-to-ww
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Construct a Turing machine to transform ⊔w⊔ to ⊔ww⊔. [Exact target string is hard to read in the scan.]

## Short answer

The TM marks the leftmost unmarked symbol of w (0→x, 1→y), goes to the first blank, writes a copy (0→a, 1→b), then returns to the left blank and repeats. After copying all symbols, it converts all marks back to 0/1, yielding ⊔ww⊔.

## Answer

**Interpretation.** The input is ⊔w⊔ with w ∈ {0,1}*; the output is ⊔ww⊔ (the second copy of w follows directly after the first). If instead ⊔w⊔w⊔ is wanted, only the last two phases change slightly.

**Idea.** Process w from left to right. Mark the leftmost unmarked symbol (0 as x, 1 as y), go right to the first blank, and write a copy there (a for 0, b for 1). Rewind to the left blank and repeat. When no unmarked symbol remains, rewind and convert x, a to 0 and y, b to 1.

M: states q0, q1, qA, qB, qR, qF, qC, qa. Tape alphabet {0, 1, x, y, a, b, ⊔}. S = stay.

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | ⊔ | same | R | q1 |
| q1 | x / y | same | R | q1 |
| q1 | 0 | x | R | qA |
| q1 | 1 | y | R | qB |
| q1 | ⊔ | same | S | qa |
| q1 | a / b | same | L | qF |
| qF | x / y | same | L | qF |
| qF | ⊔ | same | R | qC |
| qA | 0 / 1 / x / y / a / b | same | R | qA |
| qA | ⊔ | a | L | qR |
| qB | 0 / 1 / x / y / a / b | same | R | qB |
| qB | ⊔ | b | L | qR |
| qR | 0 / 1 / x / y / a / b | same | L | qR |
| qR | ⊔ | same | R | q1 |
| qC | x / a | 0 | R | qC |
| qC | y / b | 1 | R | qC |
| qC | 0 / 1 | same | R | qC |
| qC | ⊔ | same | S | qa |

- q1: find the leftmost unmarked symbol. qA / qB: carry a 0 / 1 to the end and write a / b. qR: rewind to the left blank.
- When q1 reaches a or b, everything has been copied: qF returns to the left blank, then qC converts the marks.

#### Processing ⊔01⊔
```text
[q0]⊔01
⊔[q1]01
⊔x[qA]1
⊔x1[qA]
⊔x[qR]1a
⊔[qR]x1a
[qR]⊔x1a
⊔[q1]x1a
⊔x[q1]1a
⊔xy[qB]a
⊔xya[qB]
⊔xy[qR]ab
⊔x[qR]yab
⊔[qR]xyab
[qR]⊔xyab
⊔[q1]xyab
⊔x[q1]yab
⊔xy[q1]ab
⊔x[qF]yab
⊔[qF]xyab
[qF]⊔xyab
⊔[qC]xyab
⊔0[qC]yab
⊔01[qC]ab
⊔010[qC]b
⊔0101[qC]
⊔0101[qa]
```

Final tape: ⊔**0101**⊔ = ⊔ww⊔ with w = 01. For w = ε the machine halts at once in qa.

## Check yourself

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

1. How does the machine copy w?
   A. Marks the leftmost unmarked symbol and writes a copy (a or b) at the end
   B. Reverses w
   C. Copies from the right
   D. Uses two tapes
   Answer: A. Each symbol is marked x/y, then copied as a/b at the first blank. (Key point: Strategy)

2. What does qC do?
   A. Converts x, a to 0 and y, b to 1
   B. Deletes marks
   C. Adds a blank
   D. Moves left
   Answer: A. Marks are restored to real digits at the end. (Key point: Final cleanup)

3. For w = 01 the final tape is
   A. blank 0101 blank
   B. blank 0110 blank
   C. blank 01 blank
   D. blank 1010 blank
   Answer: A. The output is w w, so 0101. (Key point: Result)

4. What happens for w = epsilon?
   A. Loops
   B. Halts at once in qa
   C. Rejects
   D. Writes 0
   Answer: B. q1 sees a blank immediately and goes to qa. (Key point: Empty input)

## Related in Theory of Computation

- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4
- [TM for f(w) = wwᴿ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-f-w-wwr) — 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

- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2
- [Interleaving; SSTF, SCAN, C-SCAN order](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ainterleaving-winchester-disk-scheduling) — Operating System, chapter 6
- [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1
- [Soft versus hard magnetic materials](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Asoft-hard-magnetic-materials) — Electric Machine Design, chapter 1, asked 5×