Library

ITM · Recursively enumerable

A binary counter that never stops

It counts in binary on its tape, so its blocks double in width and its run never repeats — the classic shape no cycle detector can settle. The finite automata reduction proves it: it finds a regular language that contains every configuration from which the machine could halt and is closed under stepping backwards, and the blank tape is not in it.

ABC⊔ → ⊔, R1 → ⊔, L⊔ → 1, R⊔ → 1, L1 → 1, R
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: finite automata reduction — an automaton recognises every way to halt, and not the start.

Standard format0RB0LA_1RC---_1LA1RBView on bbchallenge.org ↗