2026-08-28·作者 Sijie Wang#math#logic#relaxation

bounded-resources

有界资源——在期限内判定

父节点:relaxing-undecidability

不可判定性存在于极限之中。限定资源,它就消失了。

有界停机问题

"M 在 x 上是否于t 步以内停机?"是可判定的——直接模拟 t 步即可。同样,"是否存在次数 ≤ d 的证书?"也只是一次有限搜索。

因此,每一个带有期限的实际收敛问题——"在 T 步以内进入 ε-球"、"在预算内稳定下来"——都是可判定的。不可判定的版本,只是 t,T,d → ∞ 的理想化极限。

问题在于:诚实的界限本身可能不可计算。 忙碌海狸(busy-beaver)函数 BB(n)(一台 n 状态图灵机停机前最多运行的步数)比任何可计算函数都增长得快。于是"如果到第 t 步还没停机,它就永远不会停机"这句话所需要的 t,你往往无法算出来。限定资源换来了可判定性,但安全的期限可能大到天文数字——甚至大到不可计算。

与控制理论的关联: 有限期限/实用稳定性("在 [0,T] 上进入并停留在 ε-球内")就是工程师实际使用的那个可判定替代品——和本文各处一样,它用一个可检验的真理换掉了渐近的真理。这与限定 SOS 证书 次数,是同一种交换。

关于这一条

sijie 的一条 wiki 条目。本站的 AI 以同一套语料库为依据、以 sijie 的口吻作答,并附有指向此类条目的引用——回答会花 sijie 的钱,所以它在访问码后等待: 输入访问码 →