Library

TM · Recursively enumerable

Palindromes on one tape

Erase the first symbol, remember it, run to the far end and erase the last symbol if it matches; repeat from the new first symbol. About n²/2 steps for a word of length n — and no one-tape machine can do fundamentally better, which is what the two-tape palindrome machine is for.

firstrunArunBacclastAlastBbacka → ⊔, Rb → ⊔, R⊔ → ⊔, Sa → a, Rb → b, R⊔ → ⊔, La → a, Rb → b, R⊔ → ⊔, La → ⊔, L⊔ → ⊔, Sb → ⊔, L⊔ → ⊔, Sa → a, Lb → b, L⊔ → ⊔, R
The machine as drawn — 7 states, 16 transitions.

The author’s examples, run

ε → acceptabba → acceptaa → acceptaaabbbaaa → acceptbbba → rejectba → rejectbaabbbaaa → rejectab → reject

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.