Library

ITM · Recursively enumerable

A checkerboard pyramid

It builds a widening triangle of alternating cells and never repeats a configuration, so no cycle detector can catch it. The halting segment method can: it looks at only a few cells around the head and shows, by searching backwards through every way they could have looked, that no such window can ever lead to the missing transition.

ABC⊔ → ⊔, R1 → ⊔, L⊔ → ⊔, L1 → 1, R⊔ → 1, L
The machine as drawn — 3 states, 5 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: a halting segment — no configuration that leads to a halt is reachable.

Standard format0RB0LC_0LC1RA_1LA---View on bbchallenge.org ↗