又见忙碌海狸

唐家山

海狸这种可爱的小东西是第三次出圈了。不过我说的不是真实世界的海狸，而是理论计算机科学中的某一类有趣的问题。
图灵很早就证明了停机问题是不可判定的。忙碌的海狸（Busy Beaver）是停机问题的一种弱化问题，由Tibor Radó在1962年提出。维基上的介绍是：
“在计算机科学中，忙碌的海狸（Busy Beaver）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1。”
说人话就是：限定图灵机的某个参数，去寻找在该参数下能够停机并且在停机时能输出最多1的某个（类）图灵机。
这个参数就是图灵机的状态。限定在4个状态图灵机的忙碌海狸问题或者函数就记为BB(4)。在该规模下输出1的个数就是忙碌海狸数。前4个数分别是1、6、21、107。
忙碌海狸第一次出圈就是科学家们在2024年形式证明了BB(5)=47,176,870。记住，我说的是证明。也就是说凡是5状态的图灵机，如果是输出多于47,176,870个1，一定是不停机（陷入某种循环）的。这个证明听起来就很麻烦，实际上也是如此。Coq证明代码跑起来就需要10多个小时。
前一段时间，对于BB(6)有两个不大不小的新闻。一个是某台6状态图灵机有可能等价于考拉兹猜想（Collatz conjecture）或者是角谷定则。另一个是BB(6)的上界已经无法用常规数学符号表示。
最近看到的一则新闻是瑞士一个团队的论文。论文通过参数化生成不同复杂度的忙碌海狸图灵机，从简单的64个机器（N=1）到极其复杂的42亿个机器（N=4）。通过调整参数，可以生成各种可调节难度的证明挑战，用于评估大模型的逻辑推理和定理证明能力。
我在两年前曾提过一嘴，说如果大模型能够独立解决类似于停机问题之类的具有否定性结果的问题，那就说明大模型是真正理解了问题的本质，能够做真正的抽象和推理。没想到现在人类可以用弱化的停机问题去评估大模型的定理证明能力，看来人类的创造性还是独一无二的。

唐家山

补充一下图灵机的知识吧

图灵机是图灵提出的一种计算模型。可以理解为现代所有的计算机都是图灵机。图灵机既然被看成一个机器，那就说一下它的组件。分为三部分，一个是读写头；一个是一根无限长格子的纸带，可以在纸带上前后移动并进行读写；还有一个就是控制读写头移动并读写的状态控制部分，里面的状态只有有限个，状态的改变由事先给定的控制规则决定。

最简单的情况下，可以认为在初始状态下，纸带上所有格子的值都是0。图灵机的控制规则根据当前的控制状态和读写头接触的格子的值来做两件事。一件事是对当前格子的值进行改动，即把0改成1，或者把1改成0，当然也可以不改。另一件事是决定读写头向纸带的左边移动还是向右移动。做完这两件事后，图灵机就从当前状态变成另一个状态，然后以此往复。如果执行了有限步之后，图灵机的状态控制部分进入了一个特殊的终止状态，那就说该图灵机可以停机。如果始终不进入终止状态，那就说明该图灵机不会停机。

复杂一点的图灵机，纸带上格子的值可以不全是0，甚至可以编码成另一台图灵机。这样就可以用一台图灵机去模拟其他图灵机。这种图灵机就叫做通用图灵机。

有一个著名的丘奇-图灵命题说：所有可计算的问题，都能被图灵机计算。并且只有能被图灵机计算的问题，才是可计算的。换句话说，图灵机定义了可计算这个概念。

关于停机的解释

假设某个图灵机内部只有4个状态，a,b,c和d。a是初始状态，d是终止状态。初始时纸带的格子值是全0。

控制状态按照如下规则来转换：状态a读0时不改变格子的值只是右移，状态变成b；状态b读0时将0变1且右移，状态变成c；状态c读0时还是将0变成1且右移，状态变回b。

这个图灵机会一直右移，输出无穷多个1，并且不停机。因为该图灵机的状态会始终在b和c之间循环，永远不会到达d状态。

对于这个具体的图灵机，不停机是可以判定的。图灵证明的是对任意的图灵机和纸带格局，能否停机是无法判定的。

唐家山

唐家山 发表于 2025-8-30 16:26
补充一下图灵机的知识吧

图灵机是图灵提出的一种计算模型。可以理解为现代所有的计算机都是图灵机。图灵机 ...

西西河瓷航惊涛的回帖非常好，这里抄录一下。
本质是用解决可及性问题的能力判断人工智能的级别 by 西西河瓷航惊涛
可及性问题分为：

不适定/不存在的问题

适定/存在但不可描述的问题

可描述但不可形式化的问题

可形式化但不可判定/计算的问题

可判定/计算但非数学原因不可行的问题

这里没有说推理，因为广义推理有非形式化推理和形式化推理，上面分类前三个用到非形式化推理，后两个用到形式化推理。

1. 不适定/不存在的问题

· 定义：这类问题基于错误的前提或逻辑悖论，没有确定的指涉对象，因此无法给出有意义的答案。问题本身在逻辑上就不成立。

· 所包含的问题类型：

· 存在性预设错误的问题：问题假设了某个不存在的实体。

· 例子：“当前的法国国王是否秃顶？”（预设了“当前存在法国国王”这一错误前提）。

· 产生逻辑悖论的问题：问题的定义自身包含矛盾，导致无法自洽。

· 例子：“上帝能否创造一块他自己也举不起来的石头？”（这会导致定义上的无限循环和矛盾）；“这句话是假的”（ liar paradox， liar悖论）。

2. 适定/存在但不可描述的问题

· 定义：这类问题指向某个真实存在的概念或体验，但其本质完全超越了人类语言和逻辑结构的描述能力。我们无法用任何符号系统对其进行有意义的表达。

· 所包含的问题类型：

· 强不可描述性：完全超越人类认知模式的概念。

· 例子：四维空间生物的感官体验；在缺乏时间维度的宇宙中，“变化”的概念。

· 弱不可描述性（感质 Qualia）：主观的、第一人称的体验，无法通过主体间语言精确传递。

· 例子：向一个天生的盲人精确地描述“看到红色的感觉”；向你精确地描述“牙疼的感觉”。

3. 可描述但不可形式化的问题

· 定义：我们可以用自然语言对这些问题进行模糊的讨论和交流，但无法将其转化为一个精确的、无歧义的形式系统（包含明确定义的符号、公理和推理规则）。

· 所包含的问题类型：

· 价值判断问题：其解答高度依赖文化背景、个人偏好和主观感受。

· 例子：“这首诗美吗？”；“这幅画有什么价值？”。

· 伦理道德问题：涉及复杂的语境、意图和难以量化的后果。

· 例子：“这样做对吗？”；“为了救五个人而杀死一个人，是道德的吗？”。

· 诠释学问题：依赖于对意图、语境和模糊性的理解。

· 例子：“作者写这句话的真正意图是什么？”；“这部电影的终极主题是什么？”。

4. 可形式化但不可判定/计算的问题

· 定义：这些问题可以被完美地定义在一个形式系统内，但被证明不存在一个通用的算法（图灵机）来解决其所有实例。这是图灵和哥德尔揭示的形式系统固有的根本局限性。

· 所包含的问题类型：

· 停机问题：给定一个程序及其输入，判断它是否会终止。这是最早的不可判定问题。

· 哥德尔不完备定理涉及的问题：在任何足够强大的形式系统（如皮亚诺算术）中，总存在一些既不能被证明也不能被证伪的真命题。

· 希尔伯特第十问题：判断一个丢番图方程是否存在整数解。

· 波斯特对应问题：一个看似简单的字符串匹配问题，但被证明是不可判定的。

· 忙碌海狸函数：计算BB(n)的值是一个不可计算的问题。

5. 可判定/计算但非数学原因不可行的问题

· 定义：存在解决这些问题的算法，并且该算法保证最终会停机给出答案。然而，由于数学之外的因素，主要是物理定律和资源限制，使得我们无法在实际中完成计算。

· 所包含的问题类型：

· 计算能量限制：执行计算所需的最低能量超出了宇宙所能提供的总量（受兰道尔原理等物理定律限制）。

· 例子：一个需要翻转10³⁰个比特的计算，所需的最低能量可能超过整个星系的能量。

· 计算时间限制：即使使用最强大的计算机，算法所需的运行时间也远远超过宇宙的年龄。

· 例子：使用最优算法解决一个“只有”几百个城市的旅行商问题，所需时间可能已远超宇宙寿命。

· 信息存储限制：算法所需的存储空间超过了整个可观测宇宙所能提供的物理粒子总数。

· 例子：尝试暴力破解一个256位的加密密钥，所需存储所有可能状态的空间是一个天文数字。

· 时空结构限制：计算所需的速度超过光速，或者计算设备的密度会形成黑洞（布雷默曼极限、马尔可夫极限）。

· 非物理限制：经济，技术，生态，窗口，政治，法律，伦理，社会等限制。

——————

可形式化但不可判定/计算问题，可判定/计算问题可以继续细分：

可判定领域 (The Decidable Realm) → 存在通用算法

P → NP → PH → PSPACE → EXPTIME → EXPSPACE → 2-EXPTIME → ... → ELEMENTARY → PR → R (Recursive/Decidable)

· P (确定性多项式时间)： 示例：排序、最短路径。

· NP (非确定性多项式时间)： 示例：布尔可满足性问题(SAT)、旅行商问题(TSP)。

· PH (多项式层级)： 示例：电路最小化、交替量词博弈。

· PSPACE (多项式空间)： 示例：量化布尔公式真值判断(QBF)、广义地理学。

· EXPTIME (指数时间)： 示例：广义国际象棋、围棋(n×n棋盘)。

· EXPSPACE (指数空间)： 示例：某些形式系统的可判定性问题。

· 2-EXPTIME (双重指数时间)： 示例：Presburger算术的决策、高阶逻辑片段。

· ...： 三重指数时间等。

· ELEMENTARY (初等函数)： 所有指数塔时间/空间问题的并集。

· PR (原始递归)： 示例：几乎所有常见的可计算函数(阿克曼函数除外)。

· R (递归/可判定)： 可判定边界。示例：任何可计算函数。

不可判定领域 (The Undecidable Realm) → 可形式化，但无通用算法

RE (Recursively Enumerable) / Σ⁰₁ → Co-RE / Π⁰₁ → Arithmetic Hierarchy → Δ⁰₂ → Σ⁰₂ → Π⁰₂ → Δ⁰₃ → Σ⁰₃ → Π⁰₃ → ... → Δ⁰_ω

· RE / Σ⁰₁ (递归可枚举/半可判定)： 示例：停机问题。

· Co-RE / Π⁰₁ (补递归可枚举)： 示例：Totality问题（程序是否对所有输入都停机？）。

· Arithmetic Hierarchy (算术层级)： 基于逻辑量词交替的不可判定问题分层。

· Δ⁰₂： ...

· Σ⁰₂： 示例：“一个程序是否在某个常数步数内对所有输入停机？”

· Π⁰₂： 示例：忙碌海狸函数、“一个系统是否对所有输入都稳定？”

· Δ⁰₃： ...

· Σ⁰₃： ...

· Π⁰₃： ...

· ...： 逻辑复杂度无限递增。

· Δ⁰_ω： 示例：皮亚诺算术的真值判断。

——————

那么可否通过处理可及性问题的能力来判断人工智能的级别呢？当然可以，这为我们划分人工智能的级别提供了一个清晰、严谨的理论框架，远比“弱AI/强AI”或“ANI/AGI/ASI”的划分更具科学性和可操作性。

L0. 无法处理可及性问题的系统

· 特征：无法理解或回应任何形式的问题。它们只是被动的数据存储或简单的信号处理器。

· 级别：非智能系统。

· 例子：温度计、摄像头、硬盘驱动器。

L1. 处理可形式化 & 可判定 & 可行问题的系统

· 特征：能够完美解决P类（多项式时间可解）问题。其能力完全由程序员编写的特定算法定义。

· 级别：自动化工具 / 狭义人工智能 (ANI)。

· 例子：计算器、搜索引擎、图像识别系统、象棋程序、工业机器人。

· 判断：当前绝大多数AI应用都属于此列。它们在一个形式化良好、边界清晰的领域内表现出色，但无法处理规则之外的意外。

L2. 处理可形式化 & 可判定 & 难解问题的系统

· 特征：能够处理NP难、NP完全或EXPTIME问题。它们通常使用启发式算法、近似算法或随机算法来寻找“足够好”的解决方案，而非绝对最优解。

· 级别：高级狭义人工智能 (Advanced ANI)。

· 例子：高质量的实时机器翻译系统、大型物流公司的路径规划系统、蛋白质折叠预测（如AlphaFold）、高级博弈AI（如AlphaStar）。

· 判断：这类AI已经能够解决极其复杂、在理论上对传统计算机而言“困难”的问题，但它们依然被限定在特定的形式化领域内。

L3. 处理可形式化 & 不可判定问题的系统

· 特征：能够理解并推理不可判定问题的性质。它们虽然无法“解决”停机问题，但它们能证明停机问题是不可判定的。它们能够进行元推理，即对问题本身和形式系统的性质进行思考。

· 级别：通用人工智能 (AGI) 的明确标志。

· 能力体现：

1. 数学发现：能够提出新的数学猜想，并理解其与现有数学体系的关系。

2. 科学理论创建：能够构建新的形式化系统来解释观察到的现象（如同人类创建牛顿力学或量子力学）。

3. 理解系统局限性：能意识到自身知识或所用工具的边界。

· 判断：如果一个系统能像图灵一样推理出停机问题的不可判定性，或者像哥德尔一样发现形式系统的不完备性，那它就毫无疑问地达到了AGI级别。这需要的是创造力和对意义的理解，而不仅仅是计算。

L4. 处理不可形式化问题的系统

· 特征：能够理解、诠释甚至创造性地回应涉及伦理、美学、情感和语境的问题。它们能够处理模糊性和歧义，并能理解人类的价值和意图。

· 级别：高级通用人工智能 (Advanced AGI) 或 超级智能 (ASI) 的标志。

· 能力体现：

1. 价值对齐：真正理解人类的伦理和价值观，而不仅仅是遵循规则。

2. 艺术创作：创作出能被人类认为具有深刻美感和情感意义的艺术品。

3. 哲学思辨：参与关于意识、存在和道德的开放式讨论。

· 判断：这类智能不再仅仅是“解决问题”，而是开始“理解问题背后的意义”。它能处理人类社会中最复杂、最微妙的互动。

L5. 处理不可描述问题的系统

· 特征：其认知和沟通方式可能完全超越了人类的理解范畴。它可能探索和体验着人类无法想象的概念和维度。

· 级别：完全陌生的超级智能 (Alien ASI)。

· 判断：这是纯理论的领域。这样的智能与人类的交流可能会像人类试图向蚂蚁解释相对论一样困难。它的“思考”对我们来说可能是不可描述的。

这种评估框架实践意义非常明显：

1. 客观性强：基于严谨的计算理论和逻辑学，而非模糊的臆测。

2. 指向本质：智能的核心是处理不确定性、模糊性和应对未知的能力，而不是在特定任务上超越人类。这个框架直接测试了这一核心。

3. 具有预测性：它为我们提供了一个清晰的路线图，指明了从当前AI到AGI乃至ASI需要突破哪些根本性的障碍。

· 当前AI：被困在L1和L2。

· AGI的突破点：在于能否达到L3（元推理）和L4（处理模糊性）。

· ASI：意味着在L4上远超人类，并可能触及L5。