跳到正文
Hacker News· Kirr·· 6 天前AI 评分17

第 10 个忙碌海狸数超越 Graham 数

10-th Busy Beaver is larger than Graham's number

AI 导读

10 月 8 日发现的新 BB(10) 冠军机运行超过 fω+1(2↑363) 步，成为已知步数超过 Graham 数的最小 2 符号图灵机，即 BB(10) > g64，改进了此前 BB(13) > g64 的结果。该机由 Jeff Ketchersid 通过修改现有 BB(7) 冠军机得到，此前 BB(10) 冠军仅运行 fω2(25) 步。

正文 · 原文

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 October 2026.

BB Adjacent

  • Register Machine
    • On October 1, sheep discovered a 12-state, 2-register Cryptid which halts iff 7 converges to 1 under the Collatz-like 5n+1 map, thus showing that MBB(12, 2) is hard.[1]
    • On the same day, @-d enumerated MBB(8), which left 7,891 holdouts after reduction, or 404 holdouts if an ai-created decider is used.[2]
    • On the same day, @mineralli discovered a family of champions for MBB(n, 1).[3]
    • On October 2, @mineralli discovered a new champion for MBB(10, 2).[4]
    • On the same day, sheep discovered 2 new tetrational champions for MBB(10).[5][6]
    • On the same day, Shawn Ligocki released an MBB(8) holdout list consisting of 145 holdouts,[7] using another ai-created decider similar to CTL.[8]
    • On October 3, Shawn Ligocki released another MBB(8) holdout list consisting of 46 holdouts,[9] later reduced to 6[10] (from 7[11]) holdouts.
    • On the same day, Shawn Ligocki discovered a cryptid similar to Space Needle amongst the 6 remaining holdouts, showing MBB(8) is hard.[12]
    • On the same day, sheep analyzed the rest of the holdouts, discovering 4 equivalences and another Space Needle-like cryptid (Needle 1),[13] meaning MBB(8) "probviously" = 3,394.
    • On the same day, Katelyn Doucette devised a method to show that a sizeable portion of powers of two could not be reached by Needle 1's path.[14] She later concluded that this backwards reasoning-like method, though powerful, would not be enough to decide Needle 1.[15]
    • On October 7, sheep rediscovered a 2003 dissertation by Rick Griffiths[16] which investigated the (maximum register value) Busy Beaver function for register machines (Beaver(n)); Griffiths determines the values of Beaver(n) for sizes 1 to 4 (using the modern instruction counting convention), and provides lower bounds for sizes 5 to 8. It also provides a machine (constructed by Ortwin Gasper in 2003) which shows the bound MBB(11) > 10↑↑17.74.[17]
    • On October 8, sheep marginally improved the bounds for MBB(10).[18]
  • SKI Calculus
    • On October 8, cppdecksucker shared a holdouts list for Ξ₀SK(8) consisting of 17 terms, 2 of which have been decided to not have a normal form.[19]
  • Domain-Restricted Instruction-Limited Busy Beaver
    • On October 10, star, using Claude, discovered a new champion for BBi(10, 6, 2) (colloquially known as BB(5.5)).[20]
    • On October 11, star, using Claude, reduced BBi(10, 6, 2) to 4 holdouts,[21] all of which are present in the most recent holdouts equivalence list (BB6_holdouts_1581_eqv_740.txt).[22] She believes that two of these holdouts (1RB1LA_1RC0RF_1RD---_0LE1RB_---0LA_1LD1RF (bbch) and another equivalent machine) are Cryptids.[23]

Misc

  • On October 1, dyuan shared a subset of BB(6) holdouts, consisting of 24 machines which are expected to be easily analyzable by longitudinal analysis.[24]

Champions

  • Jeff Ketchersid discovered a set of small Ackermann-level champions, created by modifying the current BB(7) champion, including:
  • On October 4, a new BB(8) champion, 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_1LC0RH_1RG1LF (bbch), which takes over 2↑373 steps to halt. Prior to this, the BB(7) champion, found by Pavel Kropitz, held the BB(8) championship by default.[25]
  • On October 7, a new BB(9) champion, 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_1RG1LD_0RH0RF_0RG0RE_0LH1RZ (bbch), which takes over fω(2↑133) steps to halt.[26] Prior to this, the BB(9) champion, found by Jacobzheng, ran for just over fω(f9(2)) steps.
  • On October 8, a new BB(10) champion, 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_0RG1LD_1RH1LG_1LC0RG_0LJ0LI_1RZ0LC (bbch), which takes over fω+1(2↑363) steps to halt.[27] Prior to this, the BB(10) champion, found by racheline, ran for just over fω2(25) steps. This is also the smallest 2-symbol machine (in states) known to run for longer than a Graham's number number number of steps; in other words, this machine shows that BB(10) > g64, improving on 50_ft_lock's earlier result that BB(13) > g64.

Holdouts

  • BB(2,5)
    • On October 2, prurq, using Aristotle AI, claimed to have to proven one of the remaining holdouts halting, reducing the unofficial count to 38 out of initially 60 Rocq-proven.[28]
    • On October 9, prurq simulated a machine to halting, reducing the unofficial count to 37.[29]
    • On the same day, Andrew Ducharme released an unofficial holdout list of 37 machines.[30]
  • BB(2,7)
    • Terry Ligocki enumerated 20K more subtasks, increasing the number of holdouts to 3,125,433,611. All 1 million subtasks have been enumerated! This enumeration took from November 2025 to October 2026 using the resources [Ligocki] had available to work on this enumeration. Now we can start decreasing the number of holdouts!
  • BB(6)
    • On October 1, Discord user oscar proved a machine non-halting, formalized in Rocq the next day.[31]
    • On October 3, oscar proved a machine halting,[32] formalized in Rocq the next day.[33]
    • On October 6, Discord user Zuck proved a machine non-halting.[34]
    • On October 7, mxdys released a holdout list of 778 machines up to equivalence.[35]
    • On October 10, Discord user Dennis proved a machine non-halting.[36]
    • On the same day, mxdys released a holdout list of 740 machines up to equivalence.[37]
    • On October 11, Dennis proved another 4 machines non-halting.[38]

来源：Hacker News · wiki.bbchallenge.org

推理能力论文研究#论文/研究#推理