有界资源——在期限内判定
不可判定性存在于极限之中。限定资源,它就消失了。
有界停机问题"
M在x上是否于t步以内停机?"是可判定的——直接模拟t步即可。同样,"是否存在次数≤ d的证书?"也只是一次有限搜索。
因此,每一个带有期限的实际收敛问题——"在 T 步以内进入 ε-球"、"在预算内稳定下来"——都是可判定的。不可判定的版本,只是 t,T,d → ∞ 的理想化极限。
问题在于:诚实的界限本身可能不可计算。 忙碌海狸(busy-beaver)函数 BB(n)(一台 n 状态图灵机停机前最多运行的步数)比任何可计算函数都增长得快。于是"如果到第 t 步还没停机,它就永远不会停机"这句话所需要的 t,你往往无法算出来。限定资源换来了可判定性,但安全的期限可能大到天文数字——甚至大到不可计算。
与控制理论的关联: 有限期限/实用稳定性("在 [0,T] 上进入并停留在 ε-球内")就是工程师实际使用的那个可判定替代品——和本文各处一样,它用一个可检验的真理换掉了渐近的真理。这与限定 SOS 证书 次数,是同一种交换。