跳到正文
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) 步。

正文 · AI 翻译

本期 TMBR 正在编写中，尚未发布。请添加你认为可能相关的任何注释（包括以 TODO 的形式，并附上任何相关 Discord 讨论的链接）。

本月海狸研究，2026 年 10 月。

BB 相关

  • Register Machine
    • 10 月 1 日，sheep 发现了一个 12 状态、2 寄存器的 Cryptid，当且仅当 7 在类 Collatz 的 5n+1 映射下收敛到 1 时停机，从而表明 MBB(12, 2) 是困难的。[1]
    • 同一天，@-d 枚举了 MBB(8)，归约后留下 7,891 个未决项，若使用 AI 创建的判定器则为 404 个未决项。[2]
    • 同一天，@mineralli 发现了 MBB(n, 1) 的一族冠军。[3]
    • 10 月 2 日，@mineralli 发现了 MBB(10, 2) 的一个新冠军。[4]
    • 同一天，sheep 发现了 MBB(10) 的 2 个新的四重指数级冠军。[5][6]
    • 同一天，Shawn Ligocki 发布了一份 MBB(8) 未决项列表，包含 145 个未决项，[7]使用了另一个类似于 CTL 的 AI 创建的判定器。[8]
    • 10 月 3 日，Shawn Ligocki 发布了另一份 MBB(8) 未决项列表，包含 46 个未决项，[9]后来减少到 6 个[10]（从 7 个[11]）未决项。
    • 同一天，Shawn Ligocki 在剩余的 6 个未决项中发现了一个类似于 Space Needle 的 Cryptid，表明 MBB(8) 是困难的。[12]
    • 同一天，sheep 分析了其余的未决项，发现了 4 个等价关系和另一个类似 Space Needle 的 Cryptid（Needle 1），[13]这意味着 MBB(8) “很可能” = 3,394。
    • 同一天，Katelyn Doucette 设计了一种方法，证明 Needle 1 的路径无法到达相当一部分的 2 的幂。[14]她后来得出结论，这种类似反向推理的方法虽然强大，但不足以判定 Needle 1。[15]
    • 10 月 7 日，sheep 重新发现了 Rick Griffiths 在 2003 年的一篇学位论文，[16]该论文研究了寄存器机器的（最大寄存器值）忙碌海狸函数（Beaver(n)）；Griffiths 确定了大小 1 到 4 的 Beaver(n) 值（使用现代指令计数约定），并给出了大小 5 到 8 的下界。它还提供了一台机器（由 Ortwin Gasper 于 2003 年构造），表明界 MBB(11) > 10↑↑17.74。[17]
    • 10 月 8 日，sheep 略微改进了 MBB(10) 的界。[18]
  • SKI Calculus
    • 10 月 8 日，cppdecksucker 分享了一份 Ξ₀SK(8) 的未决项列表，包含 17 个项，其中 2 个已被判定为没有范式。[19]
  • Domain-Restricted Instruction-Limited Busy Beaver
    • 10 月 10 日，star 使用 Claude 发现了 BBi(10, 6, 2)（俗称 BB(5.5)）的一个新冠军。[20]
    • 10 月 11 日，star 使用 Claude 将 BBi(10, 6, 2) 减少到 4 个未决项，[21]所有这些都出现在最新的未决项等价列表（BB6_holdouts_1581_eqv_740.txt）中。[22]她认为其中两个未决项（1RB1LA_1RC0RF_1RD---_0LE1RB_---0LA_1LD1RF（bbch）和另一台等价机器）是 Cryptid。[23]

杂项

  • 10月1日，dyuan 分享了 BB(6) 遗留问题的一个子集，包含 24 台机器，预计可通过纵向分析轻松分析。[24]

冠军

  • Jeff Ketchersid 发现了一组小型 Ackermann 级冠军，通过修改当前的 BB(7) 冠军而创建，包括：
  • 10月4日，一个新的 BB(8) 冠军，1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_1LC0RH_1RG1LF（bbch），需要超过 2↑373 步才能停机。在此之前，由 Pavel Kropitz 发现的 BB(7) 冠军默认持有 BB(8) 冠军头衔。[25]
  • 10月7日，一个新的 BB(9) 冠军，1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_1RG1LD_0RH0RF_0RG0RE_0LH1RZ（bbch），需要超过 fω(2↑133) 步才能停机。[26] 在此之前，由 Jacobzheng 发现的 BB(9) 冠军运行了略超过 fω(f9(2)) 步。
  • 10月8日，一个新的 BB(10) 冠军，1RB0RA_1LC1LF_1RD0LB_1RA1LE_1LI0LC_0RG1LD_1RH1LG_1LC0RG_0LJ0LI_1RZ0LC（bbch），需要超过 fω+1(2↑363) 步才能停机。[27] 在此之前，由 racheline 发现的 BB(10) 冠军运行了略超过 fω2(25) 步。这也是已知运行步数超过格雷厄姆数的步数的最小 2 符号机器（按状态数计）；换句话说，这台机器表明 BB(10) > g64，改进了 50_ft_lock 早先关于 BB(13) > g64 的结果。

遗留问题

  • BB(2,5)
    • 10月2日，prurq 使用 Aristotle AI 声称已证明其中一个剩余遗留问题会停机，将非官方计数从最初的 60 个 Rocq 证明减少到 38 个。[28]
    • 10月9日，prurq 模拟了一台机器直至停机，将非官方计数减少到 37 个。[29]
    • 同一天，Andrew Ducharme 发布了一份包含 37 台机器的非官方遗留问题列表。[30]
  • BB(2,7)
    • Terry Ligocki 又枚举了 2 万个子任务，将遗留问题数量增加到 3,125,433,611。全部 100 万个子任务已枚举完毕！这次枚举从 2025 年 11 月持续到 2026 年 10 月，使用了 [Ligocki] 可用的资源来进行这次枚举。现在我们可以开始减少遗留问题的数量了！
  • BB(6)
    • 10月1日，Discord 用户 oscar 证明了一台机器不停机，次日在 Rocq 中形式化。[31]
    • 10月3日，oscar 证明了一台机器停机，[32]次日用 Rocq 形式化。[33]
    • 10月6日，Discord 用户 Zuck 证明了一台机器不停机。[34]
    • 10月7日，mxdys 发布了一份包含 778 台机器（按等价性计）的遗留问题列表。[35]
    • 10月10日，Discord 用户 Dennis 证明了一台机器不停机。[36]
    • 同一天，mxdys 发布了一份包含 740 台机器（按等价性计）的遗留问题列表。[37]
    • 10月11日，Dennis 又证明了 4 台机器不停机。[38]

来源：Hacker News · wiki.bbchallenge.org

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