概念Halting Problem
停机问题
图灵证明的不可判定问题：不存在通用算法能判定任意程序是否会在有限步内停机
核心事实
时间轴 (近 90 天)
11月1日
哥德尔不完备定理与停机问题共同划定了形式系统的表达边界。
待验证50%
10月13日
忙碌海狸函数是不可计算的，不存在通用算法对任意 n 求出 BB(n)。
待验证50%
10月13日
如果能算出 BB(n)，就能用它判定所有 n 状态图灵机是否停机，从而解决停机问题。
待验证50%
10月13日
BB(10) 的具体值永远无法被人类算出，因为算出它就等于解决了停机问题的一个实例。
待验证50%
10月11日
将自然语言数学定义翻译为形式语言的语义等价性验证，在某些情形下可归约到比停机问题更高复杂度、属于算术层级更高层次的不可判定问题
待验证50%
全部知识事实 (8)
已验证
1936年图灵证明不存在通用算法判定任意程序是否会在有限步内停止（停机问题）
65%待验证bash命令的安全性检测本质上是一个不可判定问题，无法写出完美的规则引擎来判断任意bash命令是否安全
70%待验证哥德尔不完备定理与停机问题共同划定了形式系统的表达边界。
50%待验证忙碌海狸函数是不可计算的，不存在通用算法对任意 n 求出 BB(n)。
50%待验证如果能算出 BB(n)，就能用它判定所有 n 状态图灵机是否停机，从而解决停机问题。
50%待验证将自然语言数学定义翻译为形式语言的语义等价性验证，在某些情形下可归约到比停机问题更高复杂度、属于算术层级更高层次的不可判定问题
50%待验证哥德尔不完备定理的推论之一是不存在能够判定任意程序是否停机的算法（停机问题），代码正确性验证在一般意义上属于不可判定问题
50%待验证BB(10) 的具体值永远无法被人类算出，因为算出它就等于解决了停机问题的一个实例。
50%