Library

TM · Recursively enumerable

Say every letter twice

ab becomes aabb. There is no room to insert a letter in place, so the machine builds the answer beyond a # at the right: for each letter, mark it, carry it to the end and write it twice. Then it wipes out the original and the # — what is left is the doubled word.

nextcarryAcarryBwipedonepastAfirstAputAhomepastBfirstBputBa → X, Rb → Y, R# → ⊔, L⊔ → ⊔, Sa → a, Rb → b, R# → #, R⊔ → #, R⊔ → a, Ra → a, Rb → b, R⊔ → a, R⊔ → a, La → a, Rb → b, R# → #, R⊔ → #, R⊔ → b, Ra → a, Rb → b, R⊔ → b, R⊔ → b, La → a, Lb → b, L# → #, LX → X, RY → Y, RX → ⊔, LY → ⊔, L⊔ → ⊔, S
The machine as drawn — 12 states, 30 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 0 non-blank cells.