[控场AI]
概念Halting Problem

停机问题

图灵证明的不可判定问题:不存在通用算法能判定任意程序是否会在有限步内停机

时间轴 (近 90 天)

10月13日

忙碌海狸函数是不可计算的,不存在通用算法对任意 n 求出 BB(n)。

待验证50%
10月13日

如果能算出 BB(n),就能用它判定所有 n 状态图灵机是否停机,从而解决停机问题。

待验证50%
10月13日

BB(10) 的具体值永远无法被人类算出,因为算出它就等于解决了停机问题的一个实例。

待验证50%
10月11日

将自然语言数学定义翻译为形式语言的语义等价性验证,在某些情形下可归约到比停机问题更高复杂度、属于算术层级更高层次的不可判定问题

待验证50%

全部知识事实 (5)

来源文章