Library

TM · Recursively enumerable

Proper subtraction: m ∸ n

Input 0ᵐ10ⁿ; output 0^max(m−n, 0). Each round erases a 0 from the front of m and cancels one 0 of n, marking it X. When n runs out, the last erased 0 is put back and the marks and the 1 are cleared; when m runs out first, the answer is 0 and everything goes.

q0q1wipeq2q3q4q5done0 → ⊔, R1 → ⊔, R0 → 0, R1 → 1, RX → X, R0 → X, L⊔ → ⊔, L0 → 0, L1 → 1, LX → X, L⊔ → ⊔, RX → ⊔, L1 → ⊔, L0 → 0, L⊔ → 0, S0 → ⊔, RX → ⊔, R⊔ → ⊔, S
The machine as drawn — 8 states, 18 transitions.

The author’s examples, run

1 → accept0010 → accept01 → accept000000010 → accept0 → reject1010 → reject11 → reject100000010 → 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.