Library

TM · Recursively enumerable

Which binary number is smaller? x#y

Two binary numbers of the same length; accept when the first is smaller. The machine compares them digit by digit from the most significant end, crossing off as it goes. The first difference decides the answer, but it keeps crossing in pairs after that, because the lengths still have to match.

ucug0ug1uh0bubduh1bu2dcdgdenddhbd2accX → X, R0 → X, R1 → X, R0 → 0, R1 → 1, R# → #, RX → X, R0 → X, L1 → X, L0 → 0, R1 → 1, R# → #, RX → X, R1 → X, L0 → 0, L1 → 1, LX → X, L# → #, L0 → 0, L1 → 1, LX → X, RX → X, R0 → X, R1 → X, R# → #, R0 → 0, R1 → 1, R# → #, RX → X, R0 → X, L1 → X, L0 → 0, L1 → 1, LX → X, L# → #, L0 → 0, L1 → 1, LX → X, RX → X, R⊔ → ⊔, S
The machine as drawn — 14 states, 40 transitions.

The author’s examples, run

0#1 → accept001#010 → accept00#11 → accept000011#110011 → accept1#1 → reject101#010 → reject#0#11 → reject#00011#110011 → 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.