Library

ITM · Recursively enumerable

Irregular growth, closed under n-grams

Four states that grow their tape in an uneven, almost fractal pattern. The n-gram method from the Coq proof of BB(5) collects every short window of tape that can appear on either side of the head, closes that set under the machine’s moves, and finds no window in which the halting transition can fire.

ABCD⊔ → ⊔, R⊔ → ⊔, R1 → 1, L⊔ → 1, R1 → 1, R⊔ → 1, L1 → ⊔, L
The machine as drawn — 4 states, 7 transitions.

Behaviour

The first steps from a blank tape: one row per step, time running down; the outlined cell is the head.

Never halts from a blank tape. Proven: n-gram CPS — the windows around the head form a closed set with no halt.

Standard format0RB---_0RC1LC_1RD1RA_1LB0LDView on bbchallenge.org ↗