不可判定性与不完备性的模糊化版本
父节点:relaxation
这是 relaxation 中的可判定性这一维度。二元的"不可判定 / 不完备"对工程毫无用处("这个控制器收敛吗?"——回答不可判定对谁都没有帮助)。几乎每一个困难的否定结果,都有量化 / 松弛版的对应物,它们聚成几条松弛轴线——每条轴线对应一篇子笔记。
这些轴线
- delta-decidability ——容差:判定到任意小的扰动
δ为止(对控制而言是关键的一条)。 - certificates ——单侧证明:一个 Lyapunov / SOS / 排名(ranking)证书能证明收敛;可靠但不完备。
- generic-case ——典型性:在几乎所有输入上可判定;困难性只落在一个可忽略的集合上。
- probabilistic-undecidability ——概率:Chaitin 的
Ω、几乎必然收敛、极限可计算性。 - bounded-resources ——视界:在
t步 /d次以内可判定;不可判定性只出现在取极限之处。 - robustness ——不可判定性是不鲁棒的:它需要无穷精度;鲁棒的系统是可判定的。
- quantitative-incompleteness ——Chaitin:不完备性按信息比特数分级。
对控制收敛问题而言(可操作的答案)
不要去判定收敛性。而是:(a) 搜索一个 Lyapunov/SOS证书;(b) δ-判定 / 检查到某个容差为止的鲁棒收敛性;(c) 满足于概率性 / 有限视界 / 实用意义上的稳定性。控制理论——以及 recursive-harness——实际做的正是这件事。
没有免费的午餐(老实说)
松弛只是把困难性搬了个地方,并没有把它废除。δ-可判定性仍然保留着一条不可判定的精确边界;证书会漏掉一些确实收敛的系统;那条刀锋始终难啃。而把逻辑本身模糊化(模糊逻辑,Hájek)也不能逃脱不完备性。你是用一小片精确性/完备性换来了可计算性。
与这条线索的关系
recursive-harness 正是这样一个实例:一般意义上的收敛性是不可判定的(recursion-is-a-phase-transition、generalized-collatz),所以我们把范围限制到收缩 / P×C-良基递归——这是一个可判定的充分证书(recursion-convergence-contraction)。P×C-满意化(satisficing)就是那个容差 δ;一次门控检查就是证书检查。