TMBR: September 2025: Difference between revisions

Latest revision as of 23:01, 28 September 2025

Prev: August 2025	This Month in Beaver Research	Next: October 2025

This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).

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.
23 Sep 2025. Katelyn Doucette. Building the Busy Beaver Ladder.

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)	23,314,388	59,727,905	36,413,517	61.0%
BB(2,6)	873,469	22,302,296	21,428,827	96.1%
BB(4,3)	97,701,052	460,916,384	363,215,332	78.8%

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.
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)
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).
BB(4,3):
- Terry Ligocki ran a set of deciders/parameters from @mxdys' code to reduce the number of holdouts which were at 460,916,384 TMs. Six passes have reduced the holdout count to 97,701,052 TMs (78.80% reduction). (TODO: Source)
BB(3,4):
- TODO: XnoobSpeakable and Lúkos are working on the holdout list for BB(3,4), ~435M TMs, using @mxdys' deciders with various parameters.

BB Adjacent

John Tromp announced on Discord that a 350-bit $BB\lambda (n)$ function now reaches the limit of BMS, an improvement from the previous 404 bits.

TODO: phrasing. Discord source: https://discord.com/channels/960643023006490684/1355653587824283678/1413637783045542038 and https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/bms.lam

TODO: savask shared "Busy Bug Game": https://discord.com/channels/960643023006490684/1362008236118511758/1415723582989930679

Misc

TODO: Affine maps are Turing complete and its relation to BMO1: https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641 https://discord.com/channels/960643023006490684/1239205785913790465/1420491357969059910

@@ Line 1: / Line 1: @@
 {{TMBRnav|August 2025|October 2025}}
-{{stub}}
+:<div class="notice metadata plainlinks" id="stub">''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''</div>
 [[:Category:This Month in Beaver Research|This Month in Beaver Research]] for September 2025.
@@ Line 14: / Line 14: @@
 * 18 Sep 2025. Tuomas Kangasniemi. Tekniikkatalous. [https://www.tekniikkatalous.fi/uutiset/a/85aafdaf-f506-4ce0-8035-a4dbe15ee4ff Iso matematiikan ongelma ratkesi 63 v jälkeen] (Finnish) (English: A big math problem solved after 63 years).
-==Holdouts==
+== Blog Posts ==
+* 12 Sep 2025.  Katelyn Doucette. [https://katelyndoucette.com/articles/bugs-mazes-and-bradys-algorithm Bugs, Mazes, and the Unreasonably Effective Brady's Algorithm].
+* 23 Sep 2025.  Katelyn Doucette. [https://katelyndoucette.com/articles/building-the-busy-beaver-ladder Building the Busy Beaver Ladder].
+== 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 <code>main.exe</code> and the Ligockis' <code>Enumerate.py</code> and <code>lr_enum_continue</code> decider pipelines to these domains.
+{| class="wikitable"
+|+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)]]
+|23,314,388
+|59,727,905
+|36,413,517
+|61.0%
+|-
+|[[BB(2,6)]]
+|873,469
+|22,302,296
+|21,428,827
+|96.1%
+|-
+|[[BB(4,3)]]
+|97,701,052
+|460,916,384
+|363,215,332
+|78.8%
+|}
 * [[BB(6)|BB(6):]]
+** Equivalence Classes:
+*** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1419290767767240734 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 [https://discord.com/channels/960643023006490684/1239205785913790465/1419364305068888105 published a list] of 3171 total individual holdout TMs across the 1691 equivalence classes.
 ** Andrew Ducharme and @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1413428240000745618 both found a family of 10 halting TMs] independently, all halting in around <math>10^{69}</math> steps.
 ** @mxdys [https://discord.com/channels/960643023006490684/1400456788955893840/1413542505772748810 decided two machines’ fates] from the [[TMBR: August 2025#Misc|50 Random Holdouts released in August]], making 8/50 machined solved as of this month.
-** Andrew Ducharme [https://discord.com/channels/960643023006490684/1239205785913790465/1415859365944230001 found a non-halting TM], to which [https://discord.com/channels/960643023006490684/1239205785913790465/1415885515068280833 Peacemaker II replied with another machine] that turned out to be very similar, and non-halting as well. Later in his search Andrew [https://discord.com/channels/960643023006490684/1239205785913790465/1416229864280948817 found another non-halting TM.]
+** Andrew Ducharme (with help from Peacemaker II) found 3 additional halting TMs: [https://discord.com/channels/960643023006490684/1239205785913790465/1415859365944230001 1] [https://discord.com/channels/960643023006490684/1239205785913790465/1415885515068280833 2] [https://discord.com/channels/960643023006490684/1239205785913790465/1416229864280948817 3].
-** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1419290767767240734 shared a new way of grouping TMs by equivalence class,] this reduced the number of holdout equivalence classes from 2467 to 1691 (31% reduction).
-** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1419364305068888105 published a list] of 3171 holdouts. The holdouts are in 1691 equivalence classes by halting status.
 * [[BB(7)|BB(7):]]
 ** Andrew Ducharme has continued reducing [https://wiki.bbchallenge.org/wiki/BB(7)#Phase_2 the number of holdouts], from 59,727,905 to 28,189,617 (52.80% reduction).
-** Terry Ligocki ran an additional 41 filters/parameters. This reduced [https://wiki.bbchallenge.org/wiki/BB(7)#Phase_2 the number of holdouts], from 28,189,617 to 23,314,388 TMs (17.29% reduction)
+** Terry Ligocki ran an additional 24 filters/parameters. This reduced [https://wiki.bbchallenge.org/wiki/BB(7)#Phase_2 the number of holdouts], from 28,189,617 to 23,314,388 TMs (17.29% reduction)
-** The overall reduction this month was 72.9% (note: This point can be discarded after the table is made for overall reduction for all domains)
+* [[BB(2,6)|BB(2,6):]]
-* [[BB(2,6)|BB(2,6):]]
+** [https://discord.com/channels/960643023006490684/1084047886494470185/1415184724707639377 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.
-** @Peacemaker II noticed some TMs missing from Andrew Ducharme reductions. It was decided to start back at the original 22,302,296 holdout TMs. (TODO: Source)
+** Andrew Ducharme ran <code>lr_enum_continue</code> and [https://discord.com/channels/960643023006490684/1084047886494470185/1415871302274777269 reduced] the 22,302,296 holdout TMs to 20,358,011 (8.72% reduction).
-** Andrew Ducharme ran several deciders/filters and reduced the 22,302,296 holdout TMs to 20,358,011 (8.72% reduction). (TODO: Source)
+** Terry Ligocki ran 50 variations of deciders/parameters using @mxdys' C++ code, <code>main.exe</code>, [https://discord.com/channels/960643023006490684/1084047886494470185/1417287770774307037 reducing the holdout count] to 970,101 TMs (95.23% reduction)!
-** Terry Ligocki ran 50 variations of deciders/parameters using @mxdys' C++ code, main.cpp, reducing the [[BB(2,6)#Filtering|holdout count]] to 970,101 TMs (95.23% reduction)!
+** Andrew Ducharme ran <code>Enumerate.py</code>  [https://discord.com/channels/960643023006490684/1084047886494470185/1419506101912866937 reducing the holdout count] to 873,469 TMs (9.96% reduction).
-** Andrew Ducharme ran some additional deciders reducing the holdout count to 873,469 TMs (9.96% reduction). (TODO: Link to wiki page where you can find the specific filters)
 *[[BB(4,3)|BB(4,3):]]
 ** Terry Ligocki ran a set of deciders/parameters from @mxdys' code to reduce the number of holdouts which were at 460,916,384 TMs. Six passes have reduced the holdout count to 97,701,052 TMs (78.80% reduction). (TODO: Source)
@@ Line 40: / Line 78: @@
 * TODO: savask shared "Busy Bug Game": https://discord.com/channels/960643023006490684/1362008236118511758/1415723582989930679
-== Blog Posts ==
-* 12 Sep 2025.  Katelyn Doucette. [https://katelyndoucette.com/articles/bugs-mazes-and-bradys-algorithm Bugs, Mazes, and the Unreasonably Effective Brady's Algorithm].
-* 23 Sep 2025.  Katelyn Doucette. [https://katelyndoucette.com/articles/building-the-busy-beaver-ladder Building the Busy Beaver Ladder].
 == Misc ==