/machines/1RB0LF_0RC---_1RD0RA_1LE0RC_0LA0LE_1LE1LB/work/proof.pre-skeptic1.md · raw

1RB0LF_0RC---_1RD0RA_1LE0RC_0LA0LE_1LE1LB: never halts (informal proof, OPEN)

     0    1
A   1RB  0LF
B   0RC  ---        halting transition: B reads 1
C   1RD  0RA
D   1LE  0RC
E   0LA  0LE
F   1LE  1LB

0. Overview

The tape right of the head is a binary counter written in three tokens, 00, 01 and Z = 100. A digit is b Z 01 Z^g, where b is 00 (bit 0) or 01 (bit 1) and g is the gap to the next digit. The head bounces off the left end, and every bounce adds 1 to the counter (rule Inc, §2).

At the right end of the counter there is a block of gap-1 digits (the R block) followed by a finite-state "tail" W. When the counter overflows, the carry runs into the tail. The tail answers in one of two ways, decided by a finite table: - S (silent): the counter wraps to 0 and nothing else happens. - N: the whole left part of the tape freezes into a "wall". The machine then spends a long pause eating the wall two increments at a time (§3), rebuilding every gap exactly and possibly inserting new digits.

The proof has four layers: 1. Window lemmas and the parametric counter rules (§2–§3). 2. The overflow: a right sweep, the tail table, a return sweep whose parity decides N or S, and a parametric rule for the tail's growing end (§4). 3. A finite fact about the tail (TAILFRONT): its 2-bit front unit cycles 10 → 01 → 11 → 00 → 10, and S can only happen at 11 (§4.5). 4. Linear arithmetic on the counter parameters: an interval invariant at normal-mode overflows that holds whatever the tail chooses at each 11 slot (§5).

1. Notation and families

1.1 Tape notation

1.2 The right counter RC and the tail

1.3 Families

2. Window lemmas and the counter

2.1 Window lemmas (check 2: exact result, exit and step count)

name lemma steps
R2 A> 00 → 10 C> 2
R4 C> 100 → 010 C> 3
R6 C> 01 → 10 C> 2
R7 C> 00 → <E 01 3
R3 C> 0110001 → 1001010 C> (a 1-digit) 7
R5 C> 0010001 → <E 0110001 (a 0-digit is set) 3
L1 010 <E → <E 100 3
L2 1001010 <E → <E 0010001 (a processed 1-digit is reset) 17
L3 10 <E → <F 00 2
L3F 10 <F → <E 01 2
L4 100 <F → <F 001 3
UE 10010 <E → <F 00100 5
UF 10010 <F 00 → <E 00100 01 15
PE = UE·UF 1001010010 <E → <E 0010001100 20
PF = UF·UE 1001010010 <F 00 → <F 0010000100 01 20
END 00 <F → <A 01 2
B1 01 <F → 00 A> 3
ENDZX 010010100100 <F → <A 000100011001 22
BN 010010 <F 00 → <A 00010001 16
BS 1001010010010 <E → <E 0010001100100 23
CF1 C> F(1^15) → P1 C> (P1 = the 73-cell image) 73
PEN P1 <E → <E F(100100010001010) 133
PFN P1 <F 00 → <F F(010000100100101) 01 123

Shift rules, by induction from R4, L1 and L4: C> Z^n → (010)^n C> (3n steps), (010)^n <E → <E Z^n (3n), Z^n <F → <F (001)^n (3n). R2 followed by R4^a is the old shift A> (001)^a 00 → (100)^a 10 C>.

2.2 Rule Inc_L (check 3)

Inc_L. For every left half-tape L, every a ≥ 0 and every counter D_G(v) with v + 1 < 2^N:

L A>(001)^a 00 D_G(v) T → L <F (001)^a 00 D_G(v+1) T, in 6a + 6S_j + 24j + 7 steps.

Here j = the number of trailing 1 bits of v (b_0..b_(j-1) = 1, b_j = 0) and S_j = g_1 + ... + g_j. The head never reads L before the last step, so L is arbitrary. T is arbitrary too, because the run never reads past d_j.

Proof, in order: 1. R2, R4^a. 2. For i = 0..j-1: R3 on d_i, then R4^(g_(i+1)). 3. R5 on d_j. 4. For i = j-1 down to 0: L1^(g_(i+1)), then L2 on the processed d_i. 5. L1^a, then L3.

The step total is 2 + 3a + Σ(7 + 3g) + 3 + Σ(3g + 17) + 3a + 2. In this argument j ranges over 0..N-1, and the proof is by induction on j (the carry depth), like Climb/E_stmt in CounterClass3v2 TM1.

2.3 Rule Inc

Inc. K_N(a; D_G(v); T) → K_N(a+1; D_G(v+1); T) for v + 1 < 2^N, in 6a + 6S_j + 24j + 9 steps.

Proof: Inc_L with L = 0^inf, then END. 0^inf 00 <F → 0^inf <A 01 leaves A reading a 0 that it reached moving left, with 0 01 (001)^a 00 = (001)^(a+1) 00 on its right.

3. Pause rules (check 4: exact whole tape at the next IR, exact steps)

Each pause rule has the shape Inc_L, then (if two increments) B1 and Inc_L again, then a left-end lemma that ends at the next IR. In every rule b_0 = 0 (v even), so the first Inc_L has j = 0 (6p + 7 steps). j and S below belong to the second increment.

rule statement (IR → IR) domain steps proof
P100 (100)^(n+1) 1 A>(001)^p 00 D(v) → (100)^n 1 A>(001)^(p+1) 00 D(v+2) n ≥ 0, v+2 < 2^N 12p+6S+24j+19 Inc_L, B1, Inc_L, END
WX 0^inf 1 A>(001)^p 00 D(v) → 0^inf A>(001)^(p+1) 00 D(v+2) (normal mode again) v+2 < 2^N same Inc_L, B1, Inc_L, END
P010 Y (010)^(m+1) 01 A>(001)^p 00 D(v) → Y (010)^m 01 A>(001)^(p+1) 00 D(v+2) m ≥ 0, any Y same Inc_L, B1, Inc_L, END
ZX Y (010)^h 1001 01 A>(001)^p 00 D_G(v) → Y (010)^(h-3) 01 A>00 D_(p+2,G)(2(v+2)) h ≥ 3, any Y 12p+6S+24j+39 Inc_L, B1, Inc_L, ENDZX
ZXN (100)^n 10100101 A>(001)^p 00 D_G(v) → (100)^(n-2) 1 A>00 D_(p+2,G)(2(v+2)) n ≥ 2 12p+6S+24j+39 as ZX
ZXP1 (100)^n 01 A>(001)^p 00 D(v) → (100)^(n-1) 10 A>(001)^(p+1) 00 D(v+2) n ≥ 1 (tested n ≥ 3) 12p+6S+24j+19 Inc_L, B1, Inc_L, END
ZXP2 (100)^n 10 A>(001)^p 00 D_G(v) → (100)^(n-2) 1 A>00 D_(p,G)(2(v+1)) n ≥ 2, v even 6p+23 Inc_L (j=0), BN

D_(g,G)(2u) is the counter with a new LSB digit 0 at gap g in front of the old digits, so its value is 2u.

In ZX/ZXN the second Inc_L ends with F on the last cell of a wall that ends ...010 010 100 100 (ZX) or ...0 100 10100100 (ZXN). In both cases the last 12 cells are 010010100100, and ENDZX (22 steps, L4 twice inside it) turns them into 000100011001. A then reads the 13th cell from the end, which is 0, so this is an IR. That needs h ≥ 3 (ZX) or n ≥ 2 (ZXN). The right side reads 0 000100011001 (001)^p 00 d_0... = 00 0010001 Z^(p+2) d_0..., because 1001 (001)^p 00 = Z^(p+2). ZXP2 ends with BN on the last 6 cells 010010 of (100)^n 10 plus the 00 of the first 001. A then reads the middle cell of block n−1, so n ≥ 2 is needed.

The domains above are wider than what the run needs: Y and the walls are arbitrary words of the stated shape. The check ran them with random walls, random p ≤ 200, gaps ≤ 60 and ≤ 6 digits.

4. The overflow

4.1 Right sweep (OvR)

Start from X(a; G; r, H; f, e), or from the second increment of a P-cycle in pause mode (left context (100)^(n-1) 1000 after B1). The carry passes every digit:

R2, R4^a, [R3, R4^(g_i)] for i = 1..k, R3 (gap-2 digit), R4^2, then (R6, R4)^q over the R block.

C now stands on the first cell of F(f), and every token to its left is processed: 00→10, 01→10, Z→010.

4.2 The tail table T(f) (check 5)

For each of the 16,384 fixed parts f with x = 1, run the window C> F(f) (75 cells): - For f ≠ 1^15 the head leaves the window on the left, in state σ(f) ∈ {E, F}, without reading the end unit. Counts: y = 0: F (8192); y = 1: E (6581) or F (1610). - For f = 1^15 the head leaves on the right in state C after 73 steps (CF1). This is ENDCARRY, §4.4.

So T(f) is a finite set of window lemmas C> F(f) → <σ(f) F'(f). They hold for every m, every end-bit setting and every left context.

4.3 Return through the R block, and the boundary

The q processed units 10010 are restored one by one from the right: UE turns E into F, and UF turns F into E. Both write 00100, and UF also turns the first token of the unit to its right into 01. UF needs that token to be 00, and it is: the unit to the right was just restored, or F'(f) starts with 00 when σ = F (check 5, all f). The case analysis: UF at unit i runs only when unit i+1 was restored by UE, or when i = q and σ = F. BN runs only when unit 1 was restored by UE. The full composition is check 6.

After the q units the mode is σ(f) if q is even, and the other state if q is odd. Call it μ.

Class rule: N ⇔ μ = F. Check 6 recomputes this class for every f and compares it with the full simulation.

4.4 ENDCARRY (f = 1^15; check 7)

After CF1, C reads the end unit (0e_1)...(0e_m) 01. Let j = the number of leading 1s of e, with j := m + 1 when all m bits are 1 (the end marker 01 then counts as one more 1, and R7 writes a new marker on the blank cells, so m grows by 1).

R6^j, R7, then the processed tokens are restored right to left by alternating L3 (E→F, gives 00) and L3F (F→E, gives 01). The mode at the left end of the end unit is E for even j and F for odd j. Then PEN or PFN, then §4.3 with q = 2r + 1 (H = y = 1): - j even: N, end bits become (10)^(j/2) 1 rest, f' = 100100010001010, H' = 0; - j odd: S, end bits become (01)^((j+1)/2) rest, f' = 110000100100101, H' = 1. PFN leaves x = 0, and the UF on the H unit sets x = 1 again. - The emission is e0 in both cases.

4.5 TAILFRONT and closure of L* (check 6, exhaustive)

For every tail in L* and every r, a, G, in normal or pause context, the overflow is N or S with exactly the forms above. The new tail is again in L*, with m' = m except in the ENDCARRY growth case. The front unit and the emission follow:

TAILFRONT:   10 -N,e0-> 01 -N,e1-> 11 -N,e0-> 00 -N,e1-> 10,     11 -S,e0-> 10

S occurs only from front unit 11. The finite part (f ≠ 1^15) is the T(f) table plus the parity rule of §4.3, and check 6 runs it for all 16,384 f at two (r, a, G) settings. The f = 1^15 part is ENDCARRY.

Independence from r, a, G and from the left context follows from the decomposition: T(f) is a window lemma, and everything else is parametric. Check 6 also compares PO/SILENTP with NO/SILENT on 200 random tails: the new RC is the same.

5. Macro dynamics and the invariant

5.1 Quantities at a configuration X(a; G; r, H; f, e)

5.2 One overflow and its pause, in closed form (proof.md rules only)

After NO with emission e: R' = R + e and M' = 2^e·M. - The first ZX (p = 0) creates the gap-2 digit. The zones are then rebuilt innermost first: for each zone, (g − 2) P010 cycles, then ZX (ZXN for the last one). Every gap is restored exactly. - After ZXN the counter value is v_0 = 2^(k+2) + 4Γ, the wall is (100)^(a−2) 1 and the lead is 0. - The pause then runs P100 cycles (+2 each). The next overflow slot comes after c' = (M' − 2 − v_0)/2 cycles; for e = 0 this is c' = c + 3. - If c' ≤ a − 2, the slot is reached in pause mode (a PO slot) with p = c', wall a − 2 − c'. Otherwise WX ends the pause and Inc runs to the next normal-mode overflow.

After PO at inner lead p with emission e: the zones of G are rebuilt as above. Then the zone Zn(p): (p − 2) P010 cycles, then ZXP1 and ZXP2, which inserts the new gap p − 1. The wall drops by 3. The value is 2(v_G + 2(p−2) + 2) + 2.

The four paths between consecutive normal-mode overflows, starting from front unit f. Each is a composition of the rules above (algebra below, all in terms of M and s):

path from f outcomes M' s' κ' f'
S 11 S M s + M κ 10
P1 10 or 11 NO e0, PO e1, WX 4M M + 10 − s 2 11 or 10
P1S 10 NO e0, PO e1, SILENTP, WX 4M 5M + 10 − s 2 10
P3 10 NO e0, PO e1, PO e0, PO e1, WX 32M 9M + 32 − s 8 10

The algebra: - S: SILENT gives lead a + 1 and counter 0. Then M − 1 Incs reach the next overflow at a + M, with G and R unchanged. - NO e0: p = c + 3, so PO#1 has wall s − 5 and inner lead p = c + 3. - PO#1 (e1): G'' = (c+2) ∪ G, R'' = R + 1, M'' = 4M. Using 2p = M − 2^(k+2) − 4Γ − 2, the value after ZXP2 is v_1 = 2M − 6. The wall is s − 8 and the lead 0. - The next slot comes after (4M − 2 − v_1)/2 = M + 2 cycles. - If s − 8 < M + 2: WX gives lead s − 7 and value v_1 + 2(s − 7). The next overflow is at a'' = 2M + 12 − s. With the new gaps, c'' = M + 2 (so κ'' = 2) and s'' = M + 10 − s. This is P1. - Otherwise PO#2 is reached at p = M + 2 with wall s − M − 10. Its front unit is 11. - S at PO#2 (SILENTP): p = M + 3, wall s − M − 11, value 0. The next slot is 2M − 1 cycles away, more than the wall, so WX gives lead s − 7 and value 2(s − M − 10). Then a'' = 6M + 12 − s and s'' = 5M + 10 − s. This is P1S. - e0 at PO#2: gap M + 1 is inserted, M''' = 8M, value 8M − 18, wall s − M − 13. The next slot is 8 cycles away: PO#3 at p = 8 with wall s − M − 21. Its front unit is 00, so the outcome is e1. - PO#3 (e1): gap 7 is inserted, M4 = 32M, value 16M − 18, wall s − M − 24. The next slot is 8M + 8 cycles away, more than the wall, so WX follows. Then a'' = 17M + 40 − s, c'' = 8M + 8 (κ = 8) and s'' = 9M + 32 − s. This is P3.

5.3 The invariant

INV at a configuration X: κ ∈ {2, 8}, all gaps ≥ 7, tail in L*, and

Which path runs (front unit and s decide; at a 11 slot both choices are covered):

front unit f s paths why
11 [24, M/4+2] S or P1 (the tail chooses) 11 allows S or e0; after e0 the front unit is 00, which forces e1 at PO#1; then s − 8 < M + 2, so WX
10 [8, M−14] P1 10 forces e0, then 01 forces e1 at PO#1; s − 8 < M + 2, so WX
10 [M+24, 2M] P1S or P3 after PO#1 the front unit is 11; the PO#2 slot is reached because s − 8 ≥ M + 2; the tail chooses S (P1S) or e0 (P3)

Closure (images of the interval end points; every map has slope ±1; check 9b, exact, N = 8..400):

path image of s target
S [M+24, 5M/4+2] inside [M+24, 2M], f = 10
P1 from 11 [3M/4+8, M−14] inside [8, 4M−14] = [8, M'−14], f = 10
P1 from 10 [24, M+2] exactly [24, M'/4+2], f = 11
P1S [3M+10, 4M−14] inside [8, M'−14], f = 10
P3 [7M+32, 8M+8] inside [8, M'−14] with M' = 32M, f = 10

Side conditions that keep every rule inside its domain (check 9c, using M ≥ 256 and c = M/4 + κ ≥ 66): - NO: a = s + c ≥ 74 ≥ 2. - PO#1: p = c + 3 ≥ 69 and wall s − 5 ≥ 3. - PO#2: p = M + 2 and wall s − M − 10 ≥ 14. - PO#3: p = 8 and wall s − M − 21 ≥ 3. - SILENTP: wall ≥ 14 ≥ 1. - New gaps c + 2 ≥ 68, M + 1 and 7 are all ≥ 7, so every ZX zone has ≥ 3 blocks. - The rebuild never overflows. Let slack_i = the number of P-cycles left before the overflow slot after the i-th zone. Then slack_i = (slack_(i+1) + 2g − 3)/2. The final slack is c' ≥ 69, so every earlier slack is ≥ g − 1: the P010 cycles and the ZX of zone g fit. No carry reaches the tail during a rebuild. - S inside a pause happens only at PO#2. PO#1 and PO#3 have front unit 01 or 00. After SILENTP the wall (< M) runs out before the next slot (2M − 1 cycles).

Check 9a compares the closed forms with the event-level model (scripts/deepen3_macro.py, built from the rules of §2–§4 only) on random front-unit sequences: every transition matches, with no other path. Check 9d runs a DFS over all front-unit sequences.

6. Initial segment (check 8)

The first configuration in X ∩ INV is reached by direct simulation from the blank tape in 92,299 steps:

0^inf A>(001)^121 00 0110001 Z^28 0110001 Z^2 (0110001100)^5 01100 W(111111011110101, 010)

So a = 121, G = (28,), r = 5, H = 1, R = 6, N = 8, M = 256. The tail is in L* with m = 3, x = 1, H = y = 1, and the front unit is 11. Further c = 66, s = 55 ∈ [24, 66] and κ = 2.

Earlier all-ones normal-mode records exist (steps 230 … 17,206). Some are X-configurations outside INV, for example step 5,786 with G = () and s = 3. The proof does not use them: the initial segment is the exact 92,299-step run.

7. Conclusion

8. Evidence: check_proof.py

Run as python3 -B check_proof.py [--quick]; the log is work/check_proof.full.log.

check content
1 table the halting transition and the transitions into B
2 windows all 21 window lemmas of §2.1 plus PEN/PFN: exact result, exit and steps
3 Inc_L 11,472 exhaustive (N ≤ 4, all v, gaps 1..3, a ≤ 3, 6 left contexts) + 400 random (a, gaps ≤ 300, N ≤ 8, random L and T): exact tape, F on the last cell of L, L untouched, exact steps
4 pause the eight rules of §2.3/§3 on random and small instances: exact whole tape at the next IR, exact steps
5 T(f) all 16,384 fixed parts: left exit in E/F without reading the end unit, except f = 1^15 (right exit, CF1)
6 overflow 32,768 full overflows (all f, two (r, a, G) settings): NO/SILENT forms, class = parity rule, L* closed, TAILFRONT; 200 pause-context pairs
7 endcarry 300 random ENDCARRY instances with m ≤ 40
8 init blank → first X ∩ INV configuration, exact
9 macro closed forms vs model, interval closure N = 8..400, side conditions, random runs, DFS depth 48

The earlier stages also have this evidence, listed in notes.md: - rules 1050/1050 (scripts/deepen_rules.py); - the macro model reproduces the real run exactly to step 555,048,797; - 40,000 overflows of the RC chain; - closure for all bit settings with m ≤ 8 (scripts/deepen3_closure.c).

9. Lemma plan (Rocq)

No family template applies (SBCv2_6x2 tm108 was ruled out in the observe pass). The nearest pattern is CounterClass3v2.v, Module TM1: a hand-written multi-level counter with sweep lemmas, an E_stmt j induction on carry depth (E_all), Climb/Climbs, and Mac_* macro lemmas. Plan:

  1. Tape words. Define Z, digits, D_G(v) as a function of a list of (bit, gap), Zn, U, and W(f, e) as list Sym. Prove lpow-style rewriting lemmas, copying lpow_* from TM1.
  2. Window lemmas (§2.1): each is one es. The shift rules follow by ind on R4, L1 and L4.
  3. Inc_L: induction on the carry depth j over the digit list. The statement is quantified over l (left side) and r, like TM1's E_stmt.
  4. Pause rules: short follow chains (Inc_L, B1, Inc_L, END / ENDZX / BN).
  5. Overflow, split as in §4: - OvR by follow/ind over digits and units; - T(f): the hard part, 16,383 window lemmas; - the R-block return by induction on q with a mode parameter (UE/UF); - BN/BS; - ENDCARRY by induction on j (L3/L3F alternation).

Options for T(f), cheapest first: - (a) Prove one generic lemma forall f in L*\{1^15}, exists ... by a boolean checker over Fin 2^14 evaluated with vm_compute/native_compute, using a verified step function on lists. A home-made checker must be proved sound against TM.step, so this is a medium-size Rocq development. - (b) Split F(f) into its five units and prove per-unit sweep lemmas over tokens. This would replace the table with about 40 lemmas, but the decomposition has not been worked out. The tail's units are made of the same tokens, and T(f) behaves like a mixed-radix counter with carries, but the per-unit lemmas are not yet derived. - (c) 16k separate es lemmas, generated. Probably too slow. 6. TAILFRONT and closure: another finite fact over f, derived from the T(f) results plus the parity rule. It is proved together with (5a), or (5b). 7. Macro arithmetic: a Definition of the invariant on (a, G, R, f, e) as in §5.3, with the path lemmas as Mac_*-style compositions. lia handles the linear parts; powers of 2 enter as M (keep M = 2^N abstract and record only M ≥ 256, M divisible by 4). Never run CTL/NG-style searches inside Rocq. 8. init by solve_init (92,299 steps), then nonhalt via progress_nonhalt_cond, with P = INV plus the family shape.

10. Gaps (what a reviewer should still look at)

Review log