2026-08-28·by Sijie Wang#math#logic#relaxation

bounded-resources

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

父节点:relaxing-undecidability

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

有界停机问题

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

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

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

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

about this entry

One of sijie's wiki entries. The AI on this site is grounded in the same corpus and answers in sijie's voice, with citations back to entries like this one — answering costs sijie money, so it waits behind a code: enter an access code →