Library

TM · Recursively enumerable

Copy a string: w ↦ w#w

Each symbol of w is marked as copied (a becomes X, b becomes Y), carried to the end of the tape and written there; the separator is laid down by the first trip. At the end the marks are turned back into letters. Every copy costs a round trip, so the whole job takes time proportional to n².

nextcarryAcarryBunmarkdonepastAputAhomepastBputBa → X, Rb → Y, R# → #, L⊔ → #, Sa → a, Rb → b, R# → #, R⊔ → #, Ra → a, Rb → b, R⊔ → a, L⊔ → a, La → a, Rb → b, R# → #, R⊔ → #, Ra → a, Rb → b, R⊔ → b, L⊔ → b, La → a, Lb → b, L# → #, LX → X, RY → Y, RX → a, LY → b, La → a, Sb → b, S
The machine as drawn — 10 states, 29 transitions.

The author’s examples, run

ε → acceptaabba → accepta → acceptaaaaaabba → accept

Behaviour

The first steps from a blank tape: one row per step, time running down; the outlined cell is the head.

Halts from a blank tape after 1 steps, leaving 1 non-blank cells.