Library

ITM · Recursively enumerable

Unary remainder: a mod b

Input 1ᵃ#1ᵇ; output 1^(a mod b). Each round crosses off b ones of a, pairing them one at a time with the ones of b; a completed round is subtraction, and b is restored for the next. When a runs out in the middle of a round, the ones crossed in that round are the remainder.

s0s1sbs2findbinbfindaroundinaremconvdone1 → 1, R# → #, R1 → 1, R1 → 1, R⊔ → ⊔, L1 → 1, L# → #, L⊔ → ⊔, R1 → 1, Rx → x, Rz → z, R# → #, Ry → y, R1 → y, L⊔ → ⊔, Ly → y, L# → #, Lz → z, Lx → x, L1 → z, R⊔ → ⊔, Ry → 1, L# → #, Lx → x, Lz → x, L1 → 1, R⊔ → ⊔, Rz → 1, Rx → ⊔, R# → ⊔, Ry → ⊔, R1 → ⊔, R⊔ → ⊔, S
The machine as drawn — 12 states, 33 transitions.

The author’s examples, run

#1 → accept1#11 → accept#11 → accept1#1111111 → accept11 → reject##11 → reject111 → reject##1111111 → 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.