Library

TM · Recursively enumerable

0ⁿ1ⁿ by crossing off

The Turing machine Hopcroft, Motwani and Ullman build first: change the leftmost 0 to X, walk right to the leftmost 1 and change it to Y, walk back, repeat. When the 0s run out, only Y’s may remain before the blank.

q0q1q3q2q40 → X, RY → Y, R0 → 0, RY → Y, R1 → Y, L0 → 0, LY → Y, LX → X, RY → Y, R⊔ → ⊔, R
The machine as drawn — 5 states, 10 transitions.

The author’s examples, run

01 → accept0011 → accept000111 → accept00000001111111 → accept11 → reject1011 → reject100111 → reject10000001111111 → 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.