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 的錢,所以它在存取碼後等待: 輸入存取碼 →

bounded-resources — Sijie Wang