Library

TM · Recursively enumerable

Two equal halves: w#w

The first machine in Sipser’s chapter on Turing machines. Cross off the first symbol, remember it in the state, cross off its partner after the #, and come back; repeat until the left half is gone. Everything is checked with nothing but a pencil and a lot of walking.

q1q2q3q8q4q5q6q7acc0 → x, R1 → x, R# → #, R0 → 0, R1 → 1, R# → #, R0 → 0, R1 → 1, R# → #, Rx → x, R0 → x, Lx → x, R1 → x, L0 → 0, L1 → 1, Lx → x, L# → #, L0 → 0, L1 → 1, Lx → x, Rx → x, R⊔ → ⊔, R
The machine as drawn — 9 states, 22 transitions.

The author’s examples, run

# → accept01#01 → accept110#110 → accept10011#10011 → accept0 → reject11#01 → reject010#110 → reject00011#10011 → 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.