/machines/1RB0LA_0RC1RD_0LD1RE_1LA0RB_0RD1RF_1RC---/proof.md · raw

1RB0LA_0RC1RD_0LD1RE_1LA0RB_0RD1RF_1RC---: never halts

0. Picture

The left end of the tape is a binary counter. To its right is a row of 5-cell blocks. The head bounces between the counter and the right edge, adding 1 to the counter on every visit to it.

Each full cycle doubles the counter range. The block counts after a cycle are an affine function of the counts before it, and the function has two branches, chosen by the parity of a count. The proof finds a hexagon in the scaled block counts that both branches map into itself.

1. Notation and families

Tapes are written in directed-head notation. L <S R means the head is in state S on the last cell of L. L S> R means the head is in state S on the first cell of R.

word meaning
C_k(n) n in k binary digits, MSB first, digit 1 = 1010, digit 0 = 0010 (requires 2^(k-1) ≤ n < 2^k)
A = 00111, B = 10111, front 111 blocks as they look left of the head ("left form")
A' = 00101, B' = 00001 the same blocks right of a moving head ("right form")
<A 001, 001 E> the moving head. It always carries the 3 cells 001 (TM4's hL = (A,[0;0;1]), hR = (E,<[0;0;1]))

The families below are the right-edge visits in state C. Simulation found that 4,711 of 4,722 such visits up to step 1e9 have one of these two shapes; the other 11 are the start and mid-conversion visits.

P(k,n,X,z)   := 0^inf C_k(n) A^X B^z 00 C> 0^inf                 X,z >= 0
Q(k,n,x,y,z) := 0^inf C_k(n) A^x 111 A^y B^z 00 C> 0^inf         x >= 1; y,z >= 0

2. Rule table (busycoq comment-block style)

1RB0LA_0RC1RD_0LD1RE_1LA0RB_0RD1RF_1RC---

C_k(n): n in k bits MSB first, 1 -> 1010, 0 -> 0010;   A = 00111, B = 10111
P(k,n,X,z)   := 0^inf C_k(n) A^X B^z 00 C> 0^inf
Q(k,n,x,y,z) := 0^inf C_k(n) A^x 111 A^y B^z 00 C> 0^inf                    (x >= 1)

R1  P(k,n,X,z)      --> P(k,n+1,X,z+1)                     n+1 <= 2^k-1
R2  P(k,2^k-1,X,z)  --> Q(k+1,2^k+1,1,X-2,z+1)             X >= 2
R3  Q(k,n,x,y+2,z)  --> Q(k,n+3,x+2,y,z+1)                 n+3 <= 2^k-1
R4  Q(k,n,x,0,z)    --> P(k,n+z+2,x+z+1,0)                 n+z+2  <= 2^k-1
R5  Q(k,n,x,1,z)    --> P(k,n+2z+7,x+z+4,0)                n+2z+7 <= 2^k-1
R5o Q(k,n,x,1,z)    --> Q(k+1,2^k+1+3m,1+2m,x+z+2-2m,0)    m := n+2z+7-2^k >= 0,  x+z+2-2m >= 1,  3m <= 2^k-2

remark (true, never used): R4o Q(k,n,x,0,z) --> Q(k+1,2^k+1+3m,1+2m,x+z-1-2m,0),
                           m := n+z+2-2^k >= 0, x+z-1-2m >= 1, 3m <= 2^k-2

steps: R1 32X+32z+16t(n)+47,  R2 32X+32z+16k+61,  R3 96x+32y+32z+16(t(n)+t(n+1)+t(n+2))+197
       (t(n) = number of trailing 1 bits of n)

cycle (N = 2^k):  S(k,Y,Z) := Q(k+1, N+1+3m, 1+2m, Y-2m, Z+m),  m = max(0,-Z)
  (S(k,.) is the first right-edge visit after the counter grows to k+1 digits; its counter
   lies in [N,2N) and overflows at 2N)
  S(k,2j,Z)   -->+ S(k+1, 3j+Z,   N-3-4j-Z)      via R3^(j-m), R4, R1^(N-4-2Y-Z), R2
  S(k,2j+1,Z) -->+ S(k+1, 3j+3+Z, N-8-5j-2Z)     via R3^(j-m), then R5, R1^*, R2  or  R5o
invariant (N >= 64):  8Y >= N, 8Y <= 3N, 3Z <= N, 8Z >= -N, 4Y+2Z >= N, 20Y+16Z <= 9N
start: c0 -->(17215) S(6,16,0) = Q(7,65,1,16,0)

Every case is covered. For P: n < 2^k-1 uses R1, and n = 2^k-1 uses R2 (X ≥ 2 holds; see §4). For Q: y ≥ 2 uses R3. y = 0 uses R4: on the invariant the counter never overflows during an even conversion (§4), so R4o is never needed. y = 1 uses R5 if the counter does not overflow during the conversion, and R5o if it does. The domain conditions that the run must satisfy (no overflow inside a Q phase, R2's X ≥ 2, no overflow in an even conversion, and the R5o conditions) are exactly what the invariant in §4 guarantees. Outside those domains, the overflow chain of §3.3 fails to apply on every one of the 677 small instances tried (check_proof.py §3c). This shows the conditions matter, not that they are necessary. One out-of-domain instance even halts: Q(4,8,400,0,180) (from the card).

3. Proofs of the rules

3.1 Shift rules (level 0)

Each rule below is a fixed finite run. In the formal proof, each is one es (check_proof.py §1 executes each on its window exactly). Rules marked 0^inf need blank tape on that side. All others hold for every context.

rule statement steps
ENDL 00 C> 0^inf → <A 001 0^inf 7
AL 00111 <A 001 → <A 001 00101 25
BL 10111 <A 001 → <A 001 00001 9
AR 001 E> 00101 → 00111 001 E> 7
BR 001 E> 00001 → 10111 001 E> 23
ENDR 001 E> 0^inf → 10111 00 C> 0^inf 22
D1L 1010 <A 001 → <A 001 0101 (carry through a 1 digit) 12
FLIP 0010 <A 001 → 1010 001 E> (0 digit becomes 1; turn) 18
D0R 001 E> 0101 → 0010 001 E> (carried digit restored as 0) 4
OVL 0^inf <A 001 01 → 0^inf 1010 001 E> (counter overflow) 12
OVR 001 E> 01 00101 → 0010 <A 001 101 (new digit and new front) 10
FL 00111 111 <A 001 → <A 001 001 00001 (front, leftward) 28
FR1 001 E> 001 00001 → 00111 <A 001 001 13
FR2 001 E> 001 00101 → 00111 <A 001 101 13
FR3 001 E> 101 00101 → 00111 111 001 E> (front passes) 10
FR4 001 E> 101 00001 → <A 001 001 00101 36
FE0 001 E> 001 0^inf → 00111 00 C> 0^inf 6
FE1 001 E> 101 0^inf → <A 001 001 001 0^inf 36
FE2 001 E> 001 001 0^inf → 00111 <A 001 1 0^inf 13
FE3 001 E> 1 0^inf → <A 001 0011 0^inf 36
FE4 001 E> 0011 0^inf → 00111 <A 001 001 0^inf 25

3.2 Repeated rules (level 1, ind)

The counter gains a digit: 2 of its 4 cells come from the blank left side and 2 from the right. The 13 cells 001 A' A' become the 11 cells A 111 001, which are the new front. - QC (one front step). For every right word G, with x ≥ 1, y ≥ 2, and n+3 ≤ 2^k-1:

C_k(n) A^x 111 A^y <A 001 G -AL^y-> C_k(n) A^x 111 <A 001 A'^y G -FL-> C_k(n) A^(x-1) <A 001 001 B' A'^y G front now "001 B'" -AL^(x-1),CTR,AR^(x-1),FR1-> C_k(n+1) A^x <A 001 001 A'^y G front "001" -AL^x,CTR,AR^x,FR2-> C_k(n+2) A^(x+1) <A 001 101 A'^(y-1) G front "101" -AL^(x+1),CTR,AR^(x+1),FR3-> C_k(n+3) A^(x+2) 111 001 E> A'^(y-2) G front back in left form -AR^(y-2)-> C_k(n+3) A^(x+2) 111 A^(y-2) 001 E> G

So the front is a 3-state gadget: it reflects the head twice, lets it through on the third visit, and ends up two blocks further right.

3.3 Macro rules

Conversion (R4, R5, R5o; R4o as a remark). The derivation below treats both parities at once, because the argument is the same. The proof only needs the overflow case for y = 1 (R5o): §4 shows that on the invariant an even conversion never overflows. Start from Q(k,n,x,y,z) with y ∈ {0,1}. Applying ENDL, BL^z, AL^y, FL gives 0^inf C_k(n) A^(x-1) <A 001 G_1, where the old front plus the B blocks now form a gadget:

So there are T = z+2 (even) or 2z+7 (odd) hits. Every hit except the last is a reflection 001 E> G_t → A^(δ_t) <A 001 G_(t+1). Here δ_t = 1 for FR1, FR2, FE2 and FE4, and δ_t = 0 for FR4, FE1 and FE3. The last hit, FE0, ends at the right edge and adds one more A; count it as δ_T = 1. In total, Σ_t δ_t = z+2 (even) or z+5 (odd).

4. Coverage, invariant, progress

Cycle states. Let N = 2^k and m = max(0,-Z). Define S(k,Y,Z) := Q(k+1, N+1+3m, 1+2m, Y-2m, Z+m). S(k,·) is the first right-edge visit after the counter grows to k+1 digits: its counter lies in [N,2N) and overflows at 2N. (So S's index k is one less than the Q/P level k+1; in the cycle lemma, the next overflow is at 2N and the next cycle state is S(k+1,·) at level k+2.)

Cycle lemma. Write F_N(Y,Z) = (Y',Z') for the two branches in §2. Suppose that:

Then S(k,Y,Z) →+ S(k+1,Y',Z').

Proof. Let p = Y mod 2 and j = ⌊Y/2⌋. By (a), j ≥ m.

Invariant. Let R_N be the integer points (Y,Z) with

8Y ≥ N, 8Y ≤ 3N, 3Z ≤ N, 8Z ≥ -N, 4Y+2Z ≥ N, 20Y+16Z ≤ 9N.

In u = Y/N and v = Z/N this is the hexagon R with vertices (1/8,1/4), (1/8,1/3), (11/60,1/3), (3/8,3/32), (3/8,-1/8) and (5/16,-1/8). For N ≥ 64:

An affine map sends the hexagon into itself if it sends the 6 vertices in. The image coordinates are affine in 1/N ∈ (0,1/64], so checking 1/N = 0 and 1/N = 1/64 covers every N ≥ 64. All 6 vertices × 2 branches × 2 values × 6 facets hold, with slack at least 3/128 in the integer-coefficient form above (exact rational check in check_proof.py §5). The minimum is attained by the odd images of the edge u = 1/8 against the facet 4Y+2Z ≥ N, at 1/N = 1/64. For the odd branch that slack is 4u'+2v'-1 = u/2 - 5/(2N), which does not depend on v, so both vertices (1/8,1/4) and (1/8,1/3) tie at 1/16 - 5/128 = 3/128. - (i) and (ii) give (c). Applying (i) at level 2N to the image point gives (c), and Y' ≥ 2N/8 > 0.

The linear parts of the two branches contract: the even branch's eigenvalues have modulus 0.354, and the odd branch's are 0.25 and -0.5. Their fixed points are (2/7,1/7) and (2/9,1/9).

Parity, and why this is not a cryptid. The branch at each level is the parity of Y, a pseudo-random bit; in the real run the sequence is even, odd, even, even, odd, odd, even, …. But R is mapped into itself by both branches, so halting does not depend on the parities. Ground rule 6 does not apply.

Progress. Every macro rule contains ENDL (7 steps), so each cycle takes at least 1 step; in fact it takes Θ(4^k).

Conclusion. The run reaches S(6,16,0), which is in R_64 (the facet 4Y+2Z ≥ N is tight there: 64 = 64). By induction, for every k ≥ 6, the run reaches S(k+1,F(Y,Z)) from S(k,Y,Z), with the invariant holding at each level. So the machine runs forever.

Why F1 is never reached. Every step of the run lies inside one application of the 21 shift rules of §3.1, and each of those was executed exactly on its window. F is entered only by E1 = 1RF. That happens only inside FR3, FR4, FE1 and FE3, where E reads the 1 of a front word 101 or the lone 1 of FE3. Each time, the next cell is 0, so F0 = 1RC runs and F1 (halt) never does (check_proof.py §1 lists the transitions each rule uses).

5. Initial segment

c0 = 0^inf A> 0^inf reaches Q(5,17,1,2,2) = S(4,2,2) in 1,507 steps, by direct simulation (exact). From there the rules give:

Direct simulation also gives c0 -->(17215) Q(7,65,1,16,0). In Rocq, Lemma init: c0 -->* 0inf <* <[1;0;1;0] <* <[0;0;1;0]^^5 <* <[1;0;1;0] <* <[0;0;1;1;1] <* <[1;1;1] <* <[0;0;1;1;1]^^16 <* <[0;0] {{C}}> 0inf. Proof. esx. Qed. compiles in 2.1 s, closed under the global context (checked 2026-10-10, Coq 8.20.1). The induction starts at k = 6 (N = 64), because S(4,…) and S(5,…) are below the N ≥ 64 bound of the invariant.

Check against the real run: starting from step 1,507, applying only these rules reproduces all 36 observe.json history rows from that point on (configuration and exact step number), up to P(15,25768,7028,0) at step 2,318,632,923. The run's cycle states (k,Y,Z) are (6,16,0), (7,24,29), (8,65,48), (9,147,-8), (10,214,155), (11,476,438), (12,1152,655), (13,2383,1134) and (14,4710,-39), all inside R.

6. Mapping to busycoq, and what is new

Templates. SBCv7.v has six solved machines that differ from this one only in F0: TM1 (0LC), TM2 (0RD), TM3 (0LA), TM4 (0RA), TM18 (0LD) and TM37 (1RB). Other files have more (IndSBCv1 nonhalt42 with 1RA, CTLv1 nonhalt22216/nonhalt22724 with 0LB/1LA), but those are decider certificates, not readable templates. TM1–TM4 share the same notations (hR = (E,<[0;0;1]), hL = (A,[0;0;1]), d0, d1) and the same lemma list (LIncs … BigStep, nonhalt); TM18 adds a second particle pair (hR', hL') and TM37 uses different particles. TM4 is used below for those names and its BigStep shape; TM1–TM3 would serve equally well.

TM4 in brief. TM4 uses the Longitudinal library. Its segments are segRLs/sideRLs; its counter is handled by LIncs via BC.Mul2/BC.Incs on tm' (d0 = <[0;0;1;0], d1 = <[1;0;1;0], which are our 0010 and 1010); its right side is a unary counter UC1.Incs on w0/w1/w0'/w1'. TM4's proof has one BigStep per counter overflow, then progress_nonhalt_cond with the one-line invariant Rn ls <= (2^k-1)*2.

What carries over: - the particles: TM4's hR/hL are our 001 E>/<A 001; - the digits; - the counter behaviour: D1L, FLIP, D0R, OVL and OVR never enter F (checked), so CTR and OV up to its final FR3 hold verbatim for TM4's machine; - the overall shape: init, a big step per cycle, and progress_nonhalt_cond with a linear invariant.

What is new: - Blocks. Our F0 = 1RC changes every right-side word. The blocks are 00111/00101 and 10111/00001, not TM4's. - Front gadget. A 3-state front gadget (FL, FR1, FR2, FR3) walks right inside the block row. - Conversion gadget. It has a parity split: even uses FR1 only; odd uses FR1, FR2, (FR4, FR2)^z, then FE1–FE4. - Overflow during an odd conversion (R5o). The new front's QC rounds run interleaved with the old gadget's hits. This is the main new lemma. Only the odd case is needed: on the invariant an even conversion never overflows (§4), so there is no R4o lemma. - Invariant. A two-branch affine cycle map with a 6-facet polygon invariant, instead of TM4's one inequality.

Suggested formalization (IPS style; Longitudinal is not needed).

proof.md busycoq
21 shift rules (§3.1) Lemma AL l r: l <* <[0;0;1;1;1] <{{A}} [0;0;1] *> r -->* l <{{A}} [0;0;1;0;0;1;0;1] *> r. Proof. es. Qed. and the like (left-side words written with <[...]; a 0^inf side is 0inf). All 21 compile with es in this form, 3 s in total (checked 2026-10-10, Coq 8.20.1).
AL^a, BL^z, AR^a, BR^z, D1L^t, D0R^t Statement forall l r, l <* <[0;0;1;1;1]^^a <{{A}} [0;0;1] *> r -->* l <{{A}} [0;0;1] *> [0;0;1;0;1]^^a *> r. gen l r. ind a AL. does not close it: it leaves the reordering goal A'^^a *> A' *> r = A' *> A'^^a *> r. Use induction a as [\|a IH]; intros; [finish \| rewrite !lpow_S, !Str_app_assoc; follow AL; follow IH; rewrite lpow_shift'; finish]. For the rightward rules (AR, BR, D0R) the same with rewrite <-lpow_shift'. Checked for AL, BL and AR (closed under the global context); BR, D1L and D0R follow the same pattern.
CTR, OV the counter as a left side l <* d0 <* d1^^t (generic in the high bits l), so CTR is one induction on t. The value C_k(n) needs a bits-to-side function plus an increment lemma (compare BinaryCounter.v, or TM4's d0^^k <* d1 shapes)
QC, R1–R3 follow chains (mid where useful)
R4, R5 one induction over each hit list: R4 on z (FR1 rounds), R5 on z ((FR4, FR2) pairs)
R5o (the only overflow-during-conversion lemma) for the odd hit list only: one lemma "i rounds before overflow" (CTR rounds) and one "i rounds after overflow" (QC rounds), split at r = 2^k-n. The m = 0 case (overflow round = FE0 round) is what the init uses. No R4o lemma is needed.
cycle lemma R3 by ind; then even: R4, R1 by ind, R2; odd: R5, R1 by ind, R2, or R5o
init esx (above, 2.1 s)
nonhalt multistep_nonhalt with init (17,215 steps), then progress_nonhalt_cond with index (k, Y, Zp, Zm) (Z = Zp - Zm, to avoid negative nats) and P = the six inequalities plus N = 2^k ≥ 64; the arithmetic is lia after splitting Y = 2j or 2j+1 (hypothesis (d) comes from 16(2Y+Z) = (20Y+16Z) + 12Y)

7. Evidence (check_proof.py, 6 s, ALL CHECKS PASSED)

What kind of check each item is: §1, §5 and the initial segment in §6 are exact computations, so they prove those finite claims. Everything else is a range or sample check of a parametric claim (CTR for all k and n, QC for every G, R1–R5o, the cycle lemma) whose proof is the hand derivation in §3–§4.

Gaps. None in the argument as far as I can see. What remains is formalization, and the CTR value bookkeeping (bits to C_k(n)) is the fiddliest part of it. The domain of R5o is a sufficient condition chosen for the cycle lemma; it is not claimed to be necessary.

Review log (Checkpoint B skeptic, 2026-10-10)

The skeptic found the argument sound and raised seven minor gaps. All seven were accepted.

# gap resolution
1 R4o (overflow during an even conversion) never happens on the invariant, but the proof treated it as a needed case and planned an R4o lemma. Accepted. Added hypothesis (d) to the cycle lemma (if Y is even, Z' ≥ 1). §4 (i) derives it: 16(2Y+Z) = (20Y+16Z)+12Y gives 2Y+Z ≤ 27N/32 ≤ N-4, so the even branch is always R4, R1^(N-4-2Y-Z), R2, with Z' ≥ 5N/32-3 > 0. R4o is now a remark in §2. §3.3, §4, the §6 "What is new" list and the §6 plan now name only R5o. check_proof.py now checks max(2u+v) = 27/32 exactly, checks (a)–(d) on all 316,911 integer points (R4o: 0), and tallies the rules in the orbit (R4 7, R5 1, R5o 3, R4o 0), matching the skeptic's counts.
2 The §3.3 "Domain" bullet's "before the last round it is y_f+1" holds only for m ≥ 1, and the m = 0 case (used at S(6,16,0)) was covered only implicitly. Accepted. The Domain bullet now has two cases. If m = 0, round r is the FE0 round, y_f = a_r-1, and y_f ≥ 1 gives a_r ≥ 2 directly. If m ≥ 1, b_T = y_f+1 ≥ 2 and b_(r+1) ≥ b_T gives a_r ≥ 3. Round r's a_r ≥ 2 requirement (OV needs two A') is now stated explicitly. §5 notes that the init's R5o step is the m = 0 case.
3 The header's "every claim is machine-checked" overstated what check_proof.py does. Accepted. The header and the §7 intro now say: finite claims are executed exactly; parametric claims are derived by hand in §3–§4 and checked over ranges and samples. Each §7 item is labelled exact, range or sample. The check_proof.py docstring says the same.
4 "Nearest template TM4" is not unique: TM1/2/3/18 also differ only in F0. Accepted, and extended. A grep of vendor/busycoq/verify finds six SBCv7 modules differing only in F0: TM1, TM2, TM3, TM4, TM18, and also TM37 (1RB), which the skeptic's list missed. The header and §6 now list them all, and say TM4 is used for its hL/hR/d0/d1 names and BigStep shape (TM1–TM3 have identical names and lemma lists). The decider-certificate variants (IndSBCv1, CTLv1) are mentioned as non-templates.
5 gen l r. ind a AL. does not close AL^a; it leaves a reordering goal. Accepted and re-checked in Coq 8.20.1 (scratch dir, outside vendor/). ind a AL fails with "Attempt to save an incomplete proof". The manual induction with rewrite lpow_shift' compiles for AL and BL, and with rewrite <-lpow_shift' for AR. All 21 shift rules compile with es (3 s). init compiles with esx (2.1 s). The §6 table now gives the working proof scripts. The test files are work/rocq-scratch/M4Shift.v and M4Init.v, and the result is logged in atlas/rocq-notes.md.
6 The tightest polygon case is not unique: along u = 1/8 the odd branch's slack is u/2 - 5/(2N), independent of v. Accepted. §4 now names the edge u = 1/8 and the facet 4Y+2Z ≥ N, gives the slack formula, and says both vertices tie at 3/128. check_proof.py §5 now prints every case attaining the minimum (two, as stated).
7 S(k,·) is indexed by N = 2^k but sits at counter level k+1, which may trip a reader. Accepted. §2 and §4 now say S(k,·) is the first right-edge visit after the counter grows to k+1 digits, with its counter in [N,2N) and overflow at 2N.