3,094
个编辑
更改
→存在性与可构造性的分野
经典表述下，第二递归定理的"存在性"部分——不动点存在且可计算——对一切可接受编号成立，且这一保证不附带任何资源代价。然而上一小节的"自指免费，高效自指昂贵"提示了一个更深的问题：'''一旦要求不动点在资源有界的系统（如多项式时间编号）中可构造，定理的哪些部分存活、哪些失效？'''答案是一个干净的分野：'''存在性原封不动地活着；可构造性一旦要求资源有界，就会在子递归系统中部分失效。'''而有意思的是，这片"失效地带"并非荒芜之地——为了刻画它，递归论与复杂性理论交叉出三种新工具。
经典表述下，第二递归定理的"存在性"部分——不动点存在且可计算——对一切可接受编号成立，且这一保证不附带任何资源代价。然而上一小节的"自指免费，高效自指昂贵"提示了一个更深的问题：'''一旦要求不动点在资源有界的系统（如多项式时间编号）中可构造，定理的哪些部分存活、哪些失效？'''答案是一个干净的分野：'''存在性原封不动地活着；可构造性一旦要求资源有界，就会在子递归系统中部分失效。'''而有意思的是，这片"失效地带"并非荒芜之地——为了刻画它，递归论与复杂性理论交叉出三种新工具。
'''工具一：[[Kolmogorov复杂性]]与 [[DNR度]]。'''相对化之后 SRT 何时失效，上一节已给出精确刻画：<math>A</math> 能算 DNR 函数当且仅当 <math>A</math> 是 [[autocomplex]] 的<ref name="kjos2011" />。换个角度看，这条定理把"自指是否可用"从一个全有全无的定性事实，变成了一个可以'''测量、分级、缺失'''的复杂性量——DNR 度的层级就是"自指损坏程度"的标尺。
'''工具一：[[Kolmogorov复杂性]]与 [[DNR度]]。'''相对化之后 SRT 何时失效，上一节已给出精确刻画：<math>A</math> 能算 DNR 函数当且仅当 <math>A</math> 是 [[autocomplex]] 的<ref name="kjos2011">'''Kjos-Hanssen, B.; Merkle, W.; Stephan, F. (2011).''' ''Kolmogorov complexity and the recursion theorem''. Transactions of the American Mathematical Society 363(10): 5465–5480. doi:10.1090/S0002-9947-2011-05306-7.【SRT 相对化失效的刻画：A 能计算 DNR 函数 ⟺ A autocomplex；会议版为 STACS 2006, LNCS 3884, 149–161】</ref>
。换个角度看，这条定理把"自指是否可用"从一个全有全无的定性事实，变成了一个可以'''测量、分级、缺失'''的复杂性量——DNR 度的层级就是"自指损坏程度"的标尺。
'''工具二：延迟对角化（delayed diagonalization）。'''复杂性类分离证明中有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做。Breidbart 的分裂递归集构造把递归定理的延迟技术引入这类证明<ref name="breidbart1978" />，其思想被 Schmidt 统一为"复杂性类的递归论结构"定理<ref name="schmidt1985" />。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。
'''工具二：延迟对角化（delayed diagonalization）。'''复杂性类分离证明中有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做。Breidbart 的分裂递归集构造把递归定理的延迟技术引入这类证明<ref name="breidbart1978" />，其思想被 Schmidt 统一为"复杂性类的递归论结构"定理<ref name="schmidt1985" />。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。