1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC

From BusyBeaverWiki
Jump to navigation Jump to search

1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (bbch) (bbchallenge ID 36670) is a six-state, two-symbol Turing machine from the list of BB(6) holdouts. It does not halt when started on a blank tape. A machine-checked proof of this was submitted to busycoq in November 2026 (pull request #69) and is still awaiting review. An independent proof in Lean 4 is in the busy-beaver-explorer repository.

The machine keeps a list of numbers on its tape, written as long stretches of the word 01. It sweeps back and forth, taking 3 from the first number and adding to a later one, in one of four repeating patterns. When the first number runs out, the next one takes its place and is roughly twice as big, so the machine is always busy and never reaches its halting transition.

It is the same machine as 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (bbch) started in a different state (see below).

Summary

Result Does not halt (proof submitted, under review)
bbchallenge ID 36670
Behaviour Counter list in 01 blocks; four periodic regimes; epochs that roughly double
First epoch sizes 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, …
Proofs Rocq (busycoq #69, submitted); Lean 4 (busy-beaver-explorer)

Transition table

0 1
A 1RB 0LF
B 1LC 0LA
C 1RA 0RD
D --- 1RE
E 1LA 1RC
F 0LB 0RC

The only halting transition is D reading a 0. State D is entered only from C reading a 1 (0RD), so a halt needs the head, in state C, to see 1 0. In the actual run C always sees 1 1 there.

Behaviour

The tape each time the head reaches the left end, for the first 143,000 steps (one row per visit, two pixels per cell). The fine grey texture is the 01 stretches; the left one shrinks while the ones to its right grow.
The first 600 steps from a blank tape. Time runs downward; black cells are 1s and the coloured pixel is the head.

The tape as a list of numbers

Look at the tape each time state B arrives at the left end. It then reads

B> 00 (01)a 000 (01)b 000 …

that is, a list of numbers a, b, … written as stretches of 01, separated by short words such as 000. (Here (01)a means the word 01 repeated a times, and B> marks the head in state B.)

The head moves across these stretches in long sweeps. Going right it rewrites each 010101 as 011001 (14 steps per copy); going left it turns them back (22 steps per copy). So a sweep across a stretch leaves it unchanged in size, and only the short words between the stretches really change.

Round trips, regimes and epochs

  • Round trip. Each trip of the head to the far end and back takes 3 off the first number a.
  • Regimes. Meanwhile, the rest of the list cycles through one of four periodic patterns, called R0 to R3 below, with periods of 15, 22, 16 and 9 round trips. Over one period the second number b grows by 99, 141, 99 or 57.
  • Epochs. When a is used up (a = 4) the left end is rebuilt, and b (plus a constant) becomes the new first number. After a transient of up to about 150 round trips the list settles into one of the four regimes again.
The four regimes
Regime Period (round trips) a per period b per period
R0 15 −45 +99
R1 22 −66 +141
R2 16 −48 +99
R3 9 −27 +57

Because b grows by about 2.1 to 2.2 for every 1 taken from a, each epoch is about twice as long as the previous one. The first numbers at the starts of the epochs are 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, …

Proof of non-halting

The proof follows the description above. In outline:

  1. Shift rules. The two sweeps (010101 ↔ 011001) are proved once for any number of copies.
  2. 62 templates. The four regimes together have 15 + 22 + 16 + 9 = 62 phases. Each phase is a template B> 00 (01)3k+4 000 (01)3j+β … with two free counts k and j. For each template, a symbolic run shows that it leads to the next template with k one smaller and j larger, for every value of k and j.
  3. Epoch ends. For each template, a symbolic run also handles the case k = 0 (the first number is used up) and shows where the next epoch starts, again for all large enough j.
  4. Start. From the blank tape, the machine reaches one of the templates (regime R1, with a = 118 and b = 496) at step 1,277,431.
  5. Closing the loop. A simple potential (j + 2k + a constant per template) never decreases, so the size condition needed in step 3 always holds. The run therefore goes through the templates forever and never halts.

The symbolic runs are carried out by a checker whose soundness is itself proved, so a wrong number anywhere makes the proof fail rather than giving a false result.

Related machines

Machine Relation Status
1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (bbch) (ID 11019) Same transition table up to renaming the states (A→B, B→C, C→A); that machine is this table started in state C. The two runs are different: no configuration of one appears in the other in the first 107 steps. Does not halt (proof submitted, busycoq #70)

Proof status

  • Rocq (Coq): submitted to busycoq as pull request #69 (November 2026). Not yet reviewed or merged.
  • Lean 4: theorem H36670.nonhalting in holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/lean/Cert.lean of busy-beaver-explorer. The rules and the 62 round trips are checked by Lean's kernel; the start and the 62 epoch ends use native_decide. Checking takes about 5 minutes on one core.
  • An interactive explainer is at busy-beaver-explorer's GitHub Pages.

The proofs were written with the help of an AI assistant (Claude) and checked by the proof assistants named above.

References