概念Halting Problem
停机问题
图灵证明的不可判定问题:不存在通用算法能判定任意程序是否会在有限步内停机
时间轴 (近 90 天)
10月13日
忙碌海狸函数是不可计算的,不存在通用算法对任意 n 求出 BB(n)。
待验证50%
10月13日
如果能算出 BB(n),就能用它判定所有 n 状态图灵机是否停机,从而解决停机问题。
待验证50%
10月13日
BB(10) 的具体值永远无法被人类算出,因为算出它就等于解决了停机问题的一个实例。
待验证50%
10月11日
将自然语言数学定义翻译为形式语言的语义等价性验证,在某些情形下可归约到比停机问题更高复杂度、属于算术层级更高层次的不可判定问题
待验证50%