Library

TM · Recursively enumerable

Reverse a string

Take the last symbol of w, erase it, and write it after a # at the far end; repeat until w is gone, then remove the #. The first symbol is marked at the start (A or B) so the machine can tell when it is copying the last one — a one-way tape has no other way to know where its left end is.

starttoEnddonetakegoAgoBlastAlastBoutAretoutBendAfinendBa → A, Rb → B, R⊔ → ⊔, Sa → a, Rb → b, R⊔ → #, La → ⊔, Rb → ⊔, RA → ⊔, RB → ⊔, R⊔ → ⊔, L⊔ → ⊔, R# → #, Ra → a, Rb → b, R⊔ → a, L⊔ → ⊔, R# → #, Ra → a, Rb → b, R⊔ → b, La → a, Lb → b, L# → #, L⊔ → ⊔, R# → #, Ra → a, Rb → b, R⊔ → a, L⊔ → ⊔, R# → #, Ra → a, Rb → b, R⊔ → b, La → a, Lb → b, L# → ⊔, S
The machine as drawn — 14 states, 37 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.