Library

NDTM · Recursively enumerable

Is n composite? Guess a factor

Accepts 1ⁿ exactly when n is composite: the machine guesses a factor p, then verifies it by dealing the remaining 1s into rounds of p. Primality by nondeterministic elimination.

seedguess pnext Xcross 1last cro…reset ru…any 1s l…acc1 → #, R1 → X, R1 → X, R1 → 1, LD → D, Lx → x, LX → x, R# → #, Rx → x, RD → D, R1 → D, Lx → x, RD → D, R1 → D, LD → D, Lx → X, L# → #, RX → X, RD → D, R1 → 1, L⊔ → ⊔, S
The machine as drawn — 8 states, 21 transitions.

The author’s examples, run

1111 → accept111111 → accept111111111 → accept11111 → reject1111111 → reject