busy-beaver/BB10/1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_0RG1LD_1RH1LG_1LC0RG_0LJ0LI_1RZ0LC.md at main · jeff87654/busy-beaver
Pangram verdict · v3.3
We believe that this text is a mix of AI and human-written content.
AI likelihood · overall
MixedArticle text · 1,712 words · 10 segments analyzed
A 10-state machine at level f_(ω+1) 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_0RG1LD_1RH1LG_1LC0RG_0LJ0LI_1RZ0LC Below we call this machine n1. It halts from the blank tape, its exact score is proved in Coq, and the score lies between two values of f_(ω+1). The current BB(10) champion has the published bound f_ω(f_ω(25)), at level ω of the fast-growing hierarchy. n1 beats it and moves BB(10) to level ω+1. Written 2026-10-08. 0 1 A 1RB 0RA B 1LC 1LF C 1RD 0LB D 1RA 1LE E 1LI 0LC E0 was the halting transition of the base machine F 0RG 1LD G 1RH 1LG H 1LC 0RG I 0LJ 0LI new J --- 0LC new; J0 is undefined and is the halt (1RZ in the string) Where it comes from. States A–H form an 8-state machine that we call the base machine. It agrees with the BB(8) record 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_1LC0RH_1RG1LF (../BB8/) on states A–E. It runs the same digit-list computation as the record, which is the BB(7) champion's program with 36 digits. n1 keeps the base machine, sends its halting transition E0 to a new state I, and adds the states I and J. Main facts. Here T = 2↑^37 3, the value the BB(8) record computes, and F(x) = 2↑^x 4 = 2↑^(x+1) 3. "ones" is the number of 1s on the tape when J reads 0. The standard score is σ = ones + 1, because the halting transition writes a 1. Halts Yes, machine-checked (Coq, no axioms). Exact score Machine-checked: ones = 2W + 3·2↑^(W+1)(2↑^n 5) + 12·JJ + 5, where JJ = (3T − 13)/7 and (n, W) come from an explicit recursion (section 4.4). Lower bound Machine-checked: ones > F^N(33), that is, F applied N = (6T − 19)/7 ≈ 0.86·T times to 33. Level Machine-checked, with the standard fast-growing hierarchy: f_(ω+1)(JJ − 2) < ones < f_(ω+1)(6T). Graham's number Machine-checked: ones > Graham's number. BB(10) champion Beaten, machine-checked against the champion's own Coq-proved exact score. 1. How it works 1.1 Reading the tape The notation follows Ligocki's analysis of the BB(7) champion (bbchallenge wiki page for 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF). Tokens. The tape is a string of blocks D(t) = (10)^t 1.
So D0 = 1, D1 = 101, D2 = 10101, and so on. A string of blocks splits into tokens in only one way. Configurations.
[t_1, t_2, …, t_k | A] means the tape 0^∞ D(t_1) D(t_2) … D(t_k) D0 D(A) H> 0^∞ The tokens are listed left to right, as on the tape, so t_k is next to the head.
A is the accumulator. The D0 just left of it is part of the notation and is not listed. The head is in state H on the blank cell right of D(A). Inside a list, x^j means j copies of the token x.
Digits and zeros. A token 3d + 1 is the digit d. In particular the token 1 (that is, D1) is a zero, and 1^n means n zeros.
Units and blockers. A token 3d + c with c ∈ {0, 1, 2} holds d units. Clearing removes units one at a time. When a token has no units left it becomes c. If c = 1 it is a zero. If c = 0 or c = 2 it is a blocker: the clearing rules cannot borrow from D0 or D2. Depth. The depth of a token is the number of zeros between it and the accumulator. In […, t, 1^j | A] the token t has depth j. Value. The value of an accumulator A ≡ 1 (mod 3) is v = (A + 8)/3. A reset accumulator A = 4 has v = 4. Arrows. 2↑^0 x = 2x, 2↑^1 x = 2^x, and 2↑^(k+1) x applies 2↑^k x times, starting from 1. Two identities are used often: 2↑^k 2 = 4, and 2↑^(k+1) 3 = 2↑^k 4. In Ligocki's notation, B(a; d_1, …, d_k) = [3d_k+1, …, 3d_1+1 | 3a+1] and v = a + 3. His g_j(x) = 2↑^j(x+3) − 3 (with the BB(8) record's constants) is the map v ↦ 2↑^j v below. Example. At step 6447 n1 is in the configuration [7, 1^35 | 4]: one digit 2, then 35 zeros, then the accumulator 4 (v = 4).
On the tape this is D7 (D1)^35 D0 D4, that is, 101010101010101 (101)^35 1 101010101 H> In Ligocki's notation it is B(1; [0]*35, 2), the start of the BB(8) record's main phase.
1.2 The engine n1 uses the clearing rules of the BB(7) champion and the BB(8) record: Clearing one unit of a token at depth j changes the value v into 2↑^j v. At depth 0 this doubles v. At depth 1 it gives 2^v, and at depth 2 a tower of v twos. Clearing always works on the nearest token that is not a zero. If that token is a blocker, no clearing rule applies and the list is exhausted. In the BB(8) record an exhausted list leads to the halt. In n1 it starts one of the special events of section 2.
1.3 Phase 1: the BB(8) record's computation From the blank tape, n1 reaches [7, 1^35 | 4] after 6447 steps. It then clears the two units of the 7 at depth 35: v = 4 → 2↑^35 4 → 2↑^35 (2↑^35 4) = 2↑^36 4 = 2↑^37 3 = T The result is [1^36 | 3T − 8]: 36 zeros and the value v = T. These are the record's own configurations. The BB(8) record halts here, and its final sweep writes about 12T ones. In simulation the rules used up to this point never read E0 (section 1.8), so here n1 behaves exactly like the base machine. 1.4 Phase 2: T becomes a countdown The list is exhausted. A walk to the left (event H) writes 2A + 4 = 6T − 12 new zeros at the far left. Then S0 (the first read of E0) tidies the left end. A clearing, an event P4 with nothing parked yet, and another clearing then give the first period start: [2, 5, 1^(6T−19), 0, 0, 2, 1^34 | A] Reading from the left: the first 2 is debris: a run of D2 tokens, one here, with 4 more added each period; the 5 is a marker; 1^m is the counter, here m = 6T − 19 zeros; the D0 D0 pair is a wall; the next D2 is a blocker; 1^n is the active list, here n = 34 zeros; the accumulator holds a huge value, v > T. The clearing rules only ever act on the active list. Between the active list and the counter there is always a blocker (a D2, a D0, or the D0 D0 wall), so the clearing never uses the counter's zeros as digits. Only the special events touch the counter, and each removes a fixed number of zeros: 6 + 6 + 2 = 14 per period. 1.5 Phase 3: the periods At a period start the active list is exhausted: it holds only zeros, and its far end is the blocker D2. A period runs the same four-step cycle twice. Park. The accumulator moves into the list, as a token just beyond the zeros (event P1, or P3 the second time). Its value v is now stored. The accumulator resets to 6. Fresh small value. R2 borrows one unit from the parked token and writes the 6 into the zero next to it, as a token 9 (three units, at depth n − 1).
Clearing those units gives the fresh value v₁ = 2↑^n 5. The 9 ends as a D0, so the list is exhausted again. Unpack. Event P2 (or P4) turns the parked token, which holds about v units, into about 2v new zeros of the active list. The accumulator, which holds v₁, becomes a token on the far side of the new zeros: the transit token. The accumulator resets to 4. Jump. Clearing the transit token at the new depth n' ≈ n + 2v gives a new value of about 2↑^(n'+1) v₁. The transit token ends as a D2 blocker, so the list is exhausted again and the next step is a park. Each half-period therefore takes the depth from n to about n + 2v, where v is already at least 2↑^n 4. So the depth goes from n to at least F(n) = 2↑^n 4 (Coq lemma growth), and one period goes from n to at least F(F(n)). F grows at the rate of f_ω: 2↑^n 4 is roughly f_(n+1)(4), and Coq proves f_ω(x) ≤ F(F(x)) for x ≥ 3. The unpack is free. P2 and P4 hold for every parked value and every transit value, with no condition relating the two. The small current value never has to pay for the large parked one. 1.6 Phase 4: the end The counter starts at 6T − 19 and loses 14 per period. When a period starts with the counter at 7, P1 takes 6 and leaves 1. That is too few for P2, so the final unpack is a different event, E. It writes a fixed 44-cell pattern at the far left. Its transit token is ≡ 0 (mod 3), so it clears down to a D0 instead of a D2. The machine then walks left into the fixed pattern and reaches state J reading 0: the halt. The counter reaches exactly 7 only if 6T − 19 ≡ 7 (mod 14), that is, T ≡ 2 (mod 7). Coq proves T ≡ 2 (mod 7) (T_mod7). So there are JJ = (3T − 13)/7 ≈ 0.43·T full periods and then the endgame, which is half a period. In all there are N = 2·JJ + 1 = (6T − 19)/7 unpacks, not counting the empty P4 of the set-up. 1.7 Why the level is ω+1 f_(ω+1)(x) is f_ω applied x times to x. n1 makes N ≈ 0.86·T steps of f_ω size, starting from depth 34. So its score is about f_(ω+1)(T), up to a small change in the argument. Coq proves f_(ω+1)((3T − 13)/7 − 2) < ones < f_(ω+1)(6T). A machine at level ω, such as the BB(10) champion, applies f_ω a fixed number of times. n1 applies it a number of times equal to the BB(8) record's value.