在过去的几天里，我对史蒂文温伯格比预期的早逝感到沮丧。即使在我的帖子发表后，我还是花了几个小时在 YouTube 上观看对史蒂夫的旧采访，并阅读他的旧文章以寻找我错过的洞察力的宝石。 （总有一天，我会学习史蒂夫著名的量子场论和广义相对论教科书……但那一天不是今天。）寻找能让我振作起来的东西，当 Shtetl-Optimized 读者 Nick Drozd 在 BusyBeaverology 上报告了一个重要的新发现时，我很高兴- 我很自豪地说，直接受到我去年夏天的忙碌海狸调查文章的启发（请参阅此处的博客文章）。回想一下，BB(n)，第 n 个忙碌海狸数（技术上，“忙碌海狸移位数”）被定义为具有 1 个磁带和 2 个符号的 n 状态图灵机可以执行的最大步数在调用 Halt 转换之前的初始全 0 磁带。众所周知，BB(n) 不仅不可计算，而且它的增长速度比任何可计算的 n 函数都要快——事实上，计算任何增长速度与 Busy Beaver 一样快的东西都相当于解决了停机问题。截至 2021 年，以下是人类对该函数具体值的了解程度：如您所见，该函数在 n≤4 时受到合理控制，然后在 n=5 时“实现升空”。在我的调查中，受到 Harvey Friedman 建议的启发，我定义了一种称为 Beeping Busy Beaver 或 BBB 的变体。将发出哔哔声的图灵机定义为具有单个指定状态的 TM，在该状态下它会发出“哔哔声”。这种机器 M 的蜂鸣次数，用 b(M) 表示，是使 M 在步骤 t 发出蜂鸣声的最大 t，如果没有有限的最大值，则为 ∞。那么 BBB(n) 是 b(M) 的最大有限值，在所有 n 状态机 M 中。我注意到，即使给定普通 BB 函数的预言机，BBB 函数也无法计算地增长。事实上，计算任何增长速度与 BBB 一样快的东西，都相当于解决算术层次第二层中的任何问题（可计算函数在第 0 层，停机问题在第一层）。这意味着确定 BBB 的前几个值应该比为 BB 做同样的事情更有趣！
在我编写的一个小程序的帮助下，其中的前三个，我设法自己完成了。甚至在我完成调查之前，尼克·德罗兹 (Nick Drozd) 就向我传达了第四个信息。所以截至去年夏天，我们知道 BBB 与普通的 Busy Beaver 函数在 n=1 和 n=2 时重合，然后从 n=3 开始脱离。我们不知道 BBB “实现升空”的速度有多快。但是尼克一整年都在继续解决这个问题，现在他声称已经解决了这个问题。更具体地说，他声称有以下两个结果：Nick 实际上是根据另一个 Busy Beaver 变体编写的，他称之为 BLB，或“Blanking Beaver”。他将 BLB(n) 定义为 n 状态图灵机在第一次“擦干净磁带”之前可以采取的最大有限步数——即将所有的磁带方块设置为 0，就像它们在最计算的开始，但因为它们不是在中间时间。 Nick 发现了一个 4 状态机，它需要 32,779,477 个步骤来清空它的磁带，从而证明 Nick 的构造，在调查时，结果证明是基于“类 Collatz”的迭代过程——与 BB(5) 冠军完全一样以及目前已知的大多数其他强大的 Busy Beaver 竞争者。对他的构造的简单修改产生了 BBB 的下限。请注意，Blanking Beaver 函数没有 Beeping Busy Beaver 具有的那种超级不可计算的增长：它只是“正常”地快速增长，就像原始 BB 函数所做的那样。然而，我们看到 BLB 就像 BBB 一样，已经通过 n=4 而不是 n=5“实现了升空”。所以这里真正的教训是四态图灵机已经可以在空白磁带上做非常复杂的事情。只是 BB 函数的通常定义人为地阻止了我们看到；他们隐藏了无法计算的疯狂，直到我们到达 5 个州。 Charlie Harrison 说：我很困惑 BBB(n) 和 BLB(n) 如何不受 BB(n) 的限制，直到我点击尼克的公告并意识到这些机器都不会停止 🙂
Scott 说： Bram #1：我相信经过微不足道的修改（将其中一个状态指定为蜂鸣状态）的同一台机器。如果 Nick 正在阅读这篇文章，希望他能解释这两个边界是如何相差 1 的。Nick Drozd 说：这是同一台机器，它在不同时间表现出两种行为。磁带经过 32,779,477 步后是空白的，然后再走一步，然后永远卡在一种状态。所以测量准停的次数比测量卷尺消隐的次数多一。 （“准暂停”是我一直在使用的词，而不是“指定蜂鸣状态停止蜂鸣”。）情况并非总是如此。 BLB(3) 冠军在 6 步后准停，但在 34 步后将磁带留空。 （如果有人正在寻找图灵机挑战，请尝试手工编写该程序。提示：与其他 Busy Beaver 冠军不同，该程序具有清晰的模块化结构。）如果程序表现出不止一个终止条件，那么哪个是正确的一个用来描述它的行为？如果这个新的冠军计划会说话，它会如何描述自己？我的感觉是它会说“我验证了某个奇怪且无趣的类似 Collatz 的函数，当反复应用于 2 时，最终会达到 0，此时磁带将是空白的。”该计划没有计划之后会发生什么，甚至没有理解“之后”会发生。擦拭磁带后它准停止的事实就像进入僵硬一样。想到这一点的一个原因是空白磁带是我实际找到它的方式。搜索准暂停程序令人不快。显而易见的方法是运行一系列程序，并记录每个状态最后一次被击中的时间，然后检查结果，看看它们中是否有任何一个是准暂停者。但是很难区分准暂停程序和刚刚没有再次到达某个时间段的程序，这会导致很多误报。相比之下，可以完全可靠地检测空白磁带，而且几乎免费。如果您是一个程序并且想被发现，那么擦除磁带将是一个不错的策略。这发出了一个强烈而清晰的信号，实际上可以接收到。 （你可以说我已经在这太久了，因为我一直把想法和愿望归因于程序。不仅仅是任何程序，而是甚至不是由任何人编写的程序！）
zuminator 说：不要被下限所迷惑，BBB(4) 和 BLB(4) 可能相差很大，但计算确切值的能力是有限的。就好像某个古代科学家得出的结论是，天上的星星至少有 1000 颗，一把沙子的数量也至少有 1000 颗，因为他的算盘只有 1000 颗。他的估计在技术上不会“错误”，但实际上这些数字既不接近 1000，也不接近于彼此。 Scott 说： zuminator #5：不，在手头的情况下，我们真的，真的还不知道我们是否看到了算盘的极限，或者（接近）4 态图灵机可以做的实际极限.就像：想象一下，如果有人在看到 BB(4) 的 107 步冠军后，曾圣言：“不要被下限所迷惑！ BB(4) 的实际价值肯定比这大得多。”但是没有，Allan Brady 在 1983 年证明了 BB(4) 只是 107。同样，Nick 告诉我他列举的案例足以证实 BBB(3) 只是 55，这是我设法得到的“天真”下限与 QBasic。至于 BLB 与 BBB，我们抽象地知道他们最终需要相互拉开距离，但没有充分的理由为什么他们需要在 n=4 之前这样做——同样，他们可能会也可能不会这样做。与我们大多数人不同，尼克实际上正在努力寻找答案！ 🙂 fred 说：Scott，你如何看待 S. Wolfram 一直在抛出的“计算不可约性”的概念，但我认为 Wolfram 的真正主张是大多数有趣的过程（即复杂性的出现）发生在我们的物理中世界实际上就像 BB，没有更简单的算法可以绕过运行实际的东西，一步一步。我确实想知道：对于给定大小的自动机/程序，具有该属性的比例是多少。但这也可能无法回答，就像问“1 和 0 的哪些字符串是随机的？”一样。 Scott 说： fred #10：嗯，是的，很明显，对于大量的物理系统，即使我们知道动力学定律和初始状态到合适的精度（通常我们不知道），也可能没有预测系统行为的计算捷径，而不仅仅是概括其时间演变。通过给该观察命名并错误地声称是第一个发现它的人，可以获得有限的数量。 😀
尽管如此，与说大多数物理系统“就像忙碌的海狸计算”完全不同。我不认为这是真的。 Busy Beavers 经过精心优化，可以用尽可能少的状态做尽可能多的事情。它们在图灵机中或者更普遍的物理过程中非常不典型。事实上，如果你随机选择一个 n 状态的图灵机，它表现出“类似 BB(n) 行为”的概率小到可以忽略不计，最有可能是 1/exp(n) 对于我们所说的一些合理形式化“类似BB(n)的行为”（虽然我不知道如何证明这样的说法）。这就是让这些机器如此有趣的部分原因！ Luke W 说：我有一个关于原始 Yedida-Aaronson BB(7918) eludes ZFC+SRP 论文的问题。我从来没有完全理解是什么让这个论点起作用。它是： 陈述 1：必须有一些 k 使得 BB(k) 在任何公理系统 A 中都是不可知的。 证明：假设 S1 是假的。因此，所有 BB(n) 都是可知的。也存在一个图灵机 M 使得 M 当当当 A 存在矛盾时 M 停止。这个机器 M 有一些有限数量的状态 k。但是 A 不能确定 BB(k) 的值。如果可以，A 需要证明 M 永远运行，这将证明 A 的一致性，这违反了哥德尔定理。 QED，S1 为真。为什么 A 确定 BB(k) 的值意味着 A 需要证明 M 永远运行？ Scott 说： Luke W #12：A 需要证明 M 永远运行，因为如果 M 在比假定的忙碌海狸冠军大得多的步数后停止，那么那个冠军就不会是冠军——M 会击败它。换句话说，证明 BB(n) 的值，就其本质而言，需要证明每个非停机的 n 状态图灵机实际上不会停机。这包括任何枚举某个公理系统定理的机器，如果它们发现矛盾就停止。
顺便提一下，应该注意量词：正确的陈述是对于每个公理系统 A，都存在 ak 使得 A 不能证明 BB(k) 的值。另一方面，请注意，对于每个 k，都存在一个 A，使得 A 确实证明了 BB(k) 的值。 Alex 说： 10^(2×10^10^10^18,705,352) 是一个看起来很有趣的下限，特别是因为指数中的因子为 2。 10^10^10^10^18,705,352.0001 远大于此值，所以如果边界被指定为 10^10^10^10^18,705,352，我会假设这当然是一个宽松的下限，几乎肯定可以改进到远大于 10^(2×10^10^10^18,705,352) 的东西，如果你不想花更多的空间来表达它。这让我很好奇那个 2 是从哪里来的，如果它是一个错字。 Scott 说： Alex #14：不，这不是打字错误，这正是 Wythagoras 所说的界限，当然是它获得方式的副产品。当我引用边界时，我想省略“2×”，因为它与那个数量级的数字无关紧要，但经过进一步思考，决定保持原样。 LK2 说： 绝对迷人。即使从我的角度来看，这是一个从事“基础”物理学研究的物理学家。我觉得有必要用 C(++) 写一些类似于你用 Qbasic 写的东西（如果我年轻，那是一种美妙的语言……）。 fred 说：是的，抱歉，我认为不可约性确实是比 BB-likeness 更一般（和微不足道）的属性。我认为推测是大多数导致复杂性（自然界）上升的过程并不是不可简化的，因为没有计算它们的捷径，即人们必须像自然界一样付出同样的努力才能模拟它们，基本上是一个循序渐进的过程（精度受 dt 限制，通常以混乱的方式）。例如，即使牛顿运动方程和重力方程看起来像是描述自然如何运作的有效“捷径”，但实际上除了最微不足道的情况或非常有限的简化之外，几乎没有任何胜利。在其他情况下，例如对于已经非常简单的三体问题，我们几乎必须进行数值模拟（逐步）。但是，对于解析解与数值解的适用性的局限性，也许有一个清晰的理论理解。
我想到的另一个案例是 Mandelbrot。实际上，没有人找到绕过蛮力迭代的方法（不进行近似），我们越深入（放大得越多），这种方法的成本就越高，因为我们必须对越来越大的数字进行数学运算。这令人惊讶，因为考虑到 Mandelbrot 表现出如此多的自相似性，人们可能希望计算成本可以独立于缩放级别。 Nick Drozd 说： 很荣幸能在这个博客上被推荐。我自然会借此机会提出一些建构主义意识形态。和许多读者一样，我第一次接触到来自 Scott 的文章“谁能说出更大的数字？”的 Busy Beaver 函数。 Bigger Number Game 的规则是这样说的：使用标准的数学符号、英语单词或两者，命名一个整数……要足够精确，任何有理性的现代数学家都可以准确地确定你命名的数字……一个数字必须是“命名”。这是一个数字的名称：“7”。 “7”表示一个特定的数字。 “2+5”呢？这是一个“名字”吗？可能，因为它也指定了一个特定的数字。它可能看起来不像一个名字，因为从“2 + 5”到 7 需要一些工作，但很清楚如何到达那里。同样，“Ackermann(100)”表示某个特定的数字。轻描淡写地说，从该名称到它指定的编号需要做一些工作，但仍然指定了某个特定的编号。有一条直线直接从“阿克曼（100）”到某个数，原则上可以得到这个数。 “BB(100)”呢？那是名字吗？我不确定。当然是对某个数字的描述，但是没有办法从描述中得到数字。可以说的是，我们最好的理论预测了一个与该描述相符的数字的存在。
然而，停止程序是递归可枚举的，因此原则上最终可以获得 BB(100) 的见证程序，并由此获得实际数量 BB(100)。要证明它真的是 BB(100) 肯定是不可能的，但它可以得到它在可以想象的范围内。但现在想想 BBB(100)。停机程序是 RE，但准停机程序不是：有些程序准停机但不能证明准停机。这意味着您可能手上拿着 BBB(100) 冠军计划，甚至不知道。我们真的，真的不太了解这些准停机程序。这篇文章中讨论的那个并不难理解，但完全有可能（甚至可能）BBB(5) 冠军已经不能被证明准停了。如果我们对它一无所知，如何命名一个数字？所以你说，给数字命名很容易——只要编一个就行！我们最好的理论预测存在与描述“BBB(100)”匹配的数字，所以称该数字为“X”。现在它有了名字！但这只是意味着某个数字或其他数字与某个虚构的名称相关联。在“命名名称”的意义上，这个数字仍然没有被有意义地识别出来。所有这一切都是说“BBB(100)”可能没有资格参加更大的数字游戏。没有理性的现代数学家可以准确地确定原则上是什么数字。我们对 BBB(100) 一无所知，甚至无法开始想象了解它。 fred 说：Scott，抱歉跑题了……前几天，在你再次发布 QC 炒作之后，我刚刚看到了一个真正的 IBM 量子计算机广告：我不禁注意到它与机器有多么相似在 Devs（你喜欢的系列）中 Scott 说：fred #17：在我看来，几个世纪以来几乎每一项科学成就——从预测日食和飓风到人类登陆月球，再到发明激光、晶体管和天花疫苗和 covid——为 Wolfram 的“计算不可约性原理”提供了另一个反例。也就是说，在每一种情况下，人们确实设法很好地预测（甚至控制）了一个复杂的动力系统，足以做一些有用的事情，而不是无助地看着事情展开。
您或 Wolfram 可能会回答说，与我们仍然无法预测或控制的绝大多数复杂系统相比，这一切都算不了什么——但就个人而言，我对所有这些事情的印象比小看他们！ 🙂 Scott 说： Nick #18：当然，我不同意你关于建构主义的看法……但我们已经多次进行过这种哲学辩论。现在，让我提出一个更实际的观点：对数字的描述可能或多或少有用，这取决于它们让您轻松回答哪些有关数字的问题。举个例子，写“BBB(1000)”并不能让我们说——至少，没有这个星球上没有人知道如何表现的英勇努力——我们是否命名了一个奇数或偶数，素数还是复合材料等。对于这些目的，描述几乎没有用处。另一方面，如果我们需要，很容易证明 BBB(1000) 超过 Ackermann(1000) 和 BB(1000)，甚至可能超过 BB(BB(1000))。这告诉我们，“BBB(1000)”可以是一个非常有用的描述，用于更大数量的比赛——即使不是为了其他目的！此外，我们实际上并不知道 BB(1000) 或 BBB(1000) 的奇数、偶数、素性等对我们来说永远是未知的。也许我们只是错过了解决这些问题的数学捷径——如果是这样，即使对你来说，这些数字也会显得更“真实”吗？有人同样可以争辩说，这并没有给出一个确定的数字，因为没有给出有效的标准，甚至根本没有证据表明这个数字存在。然而，多亏了安德鲁怀尔斯，我们知道它确实命名了一个确定的数字，这个数字是 2。那么，在证明费马大定理的那一天，这是否突然变成了一个确定的定义？
fred 说：进行一个不可约的计算，可能需要经过潜在无限数量的步骤才能完全限定它。这比你描述的要弱得多，对吧？例如，Mandelbrot 集定义是这样的：要确定一个点是否属于它，您可能必须......