TMBR: September 2025

Prev: August 2025

This Month in Beaver Research

Next: October 2025

This Month in Beaver Research for September 2025.

TODO: BB(5) arXiv released https://arxiv.org/abs/2509.12337

TODO: BB(3,3) month next month.

In the News

• 14 Sep 2025. Ben Brubaker. Wired. The Quest to Find the Longest-Running Simple Computer Program.
• 17 Sep 2025. Hacker News. Determination of the fifth Busy Beaver value.
• 18 Sep 2025. Tuomas Kangasniemi. Tekniikkatalous. Iso matematiikan ongelma ratkesi 63 v jälkeen (Finnish) (English: A big math problem solved after 63 years).

Blog Posts

• 12 Sep 2025. Katelyn Doucette. Bugs, Mazes, and the Unreasonably Effective Brady's Algorithm.
• 30 Sep 2025. Nick Drozd. The Shape of a Turing Machine.

Holdouts

This month saw huge reductions to holdout lists in many domains. In BB(6), this was mainly due to mxdys demonstrating the equivalence of many TMs. For the other domains it seems to be mainly due to applying mxdys's main.exe and the Ligockis' Enumerate.py and lr_enum_continue decider pipelines to these domains.

BB Holdout Reduction by Domain

Domain	New Holdout Count	Previous Holdout Count	Holdout Reduction	% Reduction
BB(6)	1,691	2,592	901	34.8%
BB(7)	22,801,601	59,727,905	36,446,066	61.8%
BB(2,6)	873,469	22,302,296	21,428,827	96.1%
BB(4,3)	50,835,926	460,916,384	410,080,458	89.0%

Details

• BB(6):
  • Equivalence Classes:
    • @mxdys shared a new way of grouping TMs by equivalence class, this reduced the number of holdout equivalence classes from 2467 to 1691 (31% reduction).
    • There is some debate about what precisely defines a holdout. Should it be the full list of TNF TMs that are undecided? Or should it be a list of one TM per equivalence class or in other words, a list of TMs such that solving them will also solve all remaining TMs (due to behavioral equivalence). In practice, most holdouts list involve some amount of trimming for equivalence classes whether that is by using TNF-1RB or Marxen-style pruning. For consistency with previous holdouts lists, we list the number of equivalence classes as the holdout count above.
    • @mxdys published a list of 3171 total individual holdout TMs across the 1691 equivalence classes.
  • Andrew Ducharme and @mxdys both found a family of 10 halting TMs independently, all halting in around $10^{69}$ steps.
  • @mxdys decided two machines’ fates from the 50 Random Holdouts released in August, making 8/50 machined solved as of this month.
  • Andrew Ducharme (with help from Peacemaker II) found 3 additional halting TMs: 1 2 3.
  • @mxdys solved 3 machines after Peacemaker II shared a holdout list where machine permutations are grouped, when @-d noticed that even the first group in the holdouts list is interesting.

• BB(7):
  • Andrew Ducharme has continued reducing the number of holdouts, from 59,727,905 to 28,189,617 (52.80% reduction).
  • Terry Ligocki ran an additional 24 filters/parameters. This reduced the number of holdouts, from 28,189,617 to 23,314,388 TMs (17.29% reduction)
  • Andrew Ducharme, starting Stage 4 of Phase 2 ran two additional filters, reducing the number of holdouts, from 23,314,388 to 22,801,601 TMs (2.2% reduction)
  • Racheline decided a machine to be halting manually.

• BB(2,6):
  • An error was noticed in the BB(2,6) holdout reduction reported last month. It was decided to start back at the original 22,302,296 holdout TMs.
  • Andrew Ducharme ran lr_enum_continue and reduced the 22,302,296 holdout TMs to 20,358,011 (8.72% reduction).
  • Terry Ligocki ran 50 variations of deciders/parameters using @mxdys' C++ code, main.exe, reducing the holdout count to 970,101 TMs (95.23% reduction)!
  • Andrew Ducharme ran Enumerate.py reducing the holdout count to 873,469 TMs (9.96% reduction).
  • Peacemaker II found a new second place champion, halting at around $10\uparrow \uparrow 19892$ steps.

• BB(4,3):
  • Terry Ligocki ran @mxdys' main.exe and reduced holdouts from 460,916,384 to 97,701,052 TMs (78.80% reduction).
  • Andrew Ducharme reduced the holdout list to 50,835,926 using Enumerate.py.

• BB(3,4):
  • XnoobSpeakable and Lúkos are working on the holdout list for BB(3,4), ~435M TMs, using @mxdys' deciders with various parameters.

Theory

Linear-Inequality Affine Transformation Automata (LIATA) were introduced as a generalization of the BMO1 rules:

• @Bard proved that 3 dimension LIATA are Turing complete: https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641
• @star proved that 2 dimension LIATA are Turing complete: https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915
• BMO1 is a 2d-LIATA so this provides some sense for the difficulty of the problem.
  • This is analogous to how Conway proved that generalized collatz maps are Turing complete which suggests the difficulty with solving Collatz-like problems.
  • But, like Conway's proof, it does not say anything concrete about any specific 2d-LIATA problem.

BB Adjacent

• @savask shared the Bug Game (and fast-growing $Bug(H,W)$ function)
  • Optimal square mazes have been discovered up to Bug(7,7) = 218 by Katelyn Doucette using TNF-style search. https://discord.com/channels/960643023006490684/1362008236118511758/1416593147210895491
  • Daniel Yuan found some long running mazes using a greedy algorithm including Bug(19,29) ≥ 11,160,428. [1]
  • Daniel Yuan proved that $Bug(H,W)\leq 4^{HW}$. [2], [3] and [4]
• John Tromp proved $BB\lambda (350)>BMS^{3}(5)$ (announcement on Discord, Code). This is an improvement over the previous result requiring 404 bits. (TODO: clarify what BMS is and if this function notation is standard).