BB(10) 的停机产出被证明超过葛立恒数 — Hacker News 中文摘要
来源：github.com — 49 分 · by surprisetalk
📋 概述
作者给出一个 10 状态图灵机 n1，并用 Coq 形式化证明了它的停机产出落在快速增长层级的 f_(ω+1) 上，从而超过葛立恒数 g_64。机器的前 8 个状态构成「基础机」，与 BB(8) 记录机在 A–E 状态上一致，跑的是同一套数字列表计算——也就是 BB(7) 冠军那台 36 位程序；第一阶段先算出 T = 2↑^37 3，第二阶段把 T 变成倒计时，用约 0.43T 个周期把活跃列表展开，最终得分约为 f_(ω+1)(T)。论文同时用 Coq 证明它超过了 2024 年公布的 BB(10) 冠军精确得分，并给出对比 BB(11)、BB(12)、BB(13) 已公布下界的结论。
🔑 核心要点
- 核心结果是用一台 10 状态机器把停机产出推到 f_(ω+1) 量级，超过葛立恒数。
- 前 8 个状态构成基础机，与 BB(8) 记录机在 A–E 状态上一致。
- 第一阶段算出 T = 2↑^37 3，第二阶段把 T 变成倒计时。
- 得分约为 f_(ω+1)(T)，全流程用 Coq 形式化验证。
- Coq 证明它超过 2024 年公布的 BB(10) 冠军精确得分。
- 文中还给出相对 BB(11)–BB(13) 已公布下界的比较结论。
💡 金句
So its score is about f_(ω+1)(T), up to a small change in the argument.
👍 0
👎 0
← 返回 Hacker News 首页