Library

TM · Recursively enumerable

Sort the 0s before the 1s

Whenever a 0 follows a 1, the two swap, and the 0 keeps moving left while there is a 1 in front of it — insertion sort, one cell at a time. Each 0 walks past every 1 to its left, so the machine takes about as many steps as there are out-of-order pairs.

scanseen1doneput0checkfixstepL0 → 0, R1 → 1, R⊔ → ⊔, S1 → 1, R0 → 1, L⊔ → ⊔, S1 → 0, L1 → 0, R0 → 0, R0 → 1, L0 → 0, L
The machine as drawn — 7 states, 11 transitions.

The author’s examples, run

ε → accept00110 → accept0 → accept000000110 → 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.