3,094
个编辑
更改
跳到导航
跳到搜索
第178行：
第178行： − − === 推论：SRT 衍生出的若干重要结果 === − − SRT 不是孤岛，但也不能把整片大陆都记在它名下。本节收录三条'''真正以 SRT 为证明枢纽'''的结果——它们的证明都必经 SRT，称"推论"名副其实： − − * '''[[Smullyan 双递归定理]]'''——SRT 的"联立化"推广：一次造出两个互相引用对方代码的程序（可推广到 <math>k</math> 个），是后续许多构造的通用工具； − * '''[[Rogers 同构定理]]'''——SRT 的"编号[[独立性 (数学)|独立性]]"推论：任意两个[[通用图灵机|通用程序]]枚举之间必有保结构的可计算同构； − * '''[[Arslanov 完全性判据]]'''——相对化 SRT 的"刻画性"等价定理：一个 r.e. 集何时是 [[r.e.-完备的]]。 − − ==== Smullyan 双递归定理（1959, 1961） ==== − − '''SRT 的联立推广'''：对任意两个可计算函数 <math>g</math>, <math>h</math>（不一定要求是全函数），存在两个程序 <math>m, n</math> 使得 − − : <math> − \phi_m(x) = g(\langle m, n\rangle, x);\qquad − \phi_n(x) = h(\langle m, n\rangle, x) − </math> − − ——两个程序可以'''互相引用对方的代码'''，其中<math>\langle m,n\rangle</math>代表将两个自然数编码为一个自然数的编码方式。 − − 由于这个Smullyan双递归定理是 SRT 的"二元推广"，因此我们可直接由 SRT 的证明套用： − − # 带参数的 SRT 造"第二号程序"：把"程序算 <math>h(\langle z, u\rangle, x)</math>"看成带两个参数 <math>z,u</math> 的偏可计算函数，先由 s-m-n（[[#s-m-n 定理（柯里化 / 参数特化）|§2.3]]）把 <math>z</math> 写死，再套 SRT，得到一个'''全'''可计算函数 <math>n_0</math>，对每个 <math>z</math> 都满足 <math>\phi_{n_0(z)}(x) = h(\langle z, n_0(z)\rangle, x)</math>； − # 再由 s-m-n 造"第一号程序"：令 <math>f(z)</math> 为"算 <math>g(\langle z, n_0(z)\rangle, x)</math> 的那个程序"——由于 <math>n_0</math> 全且可计算，<math>f</math> 也是全可计算的； − # 对 <math>f</math> 套普通 SRT：得到不动点 <math>m</math>，令 <math>n = n_0(m)</math>。于是 <math>\phi_m(x) = g(\langle m, n\rangle, x)</math>（SRT 的直接结论），且 <math>\phi_n(x) = h(\langle m, n_0(m)\rangle, x) = h(\langle m, n\rangle, x)</math>（<math>n_0</math> 的定义）。 − − 注意 <math>g,h</math> 的"全性"从头到尾没有被用到——需要全函数的只是辅助构造 <math>n_0</math> 与 <math>f</math>，而它们的全性由 s-m-n 定理和 SRT 保证。这正是定理对偏函数照样成立的原因。 − − 推广到 <math>k</math> 元：对任意 <math>k</math> 个全可计算函数 <math>g_1</math>, <math>\ldots</math>, <math>g_k</math>，存在 <math>k</math> 个程序 <math>m_1</math>, <math>\ldots</math>, <math>m_k</math> 使得 <math>\phi_{m_i}(x) = g_i(\langle m_1, \ldots, m_k\rangle, x)</math>。 − − [[#Smullyan 双递归定理（1959, 1961）|双递归定理]]是后续许多重要构造的核心：① [[#超算术层级与 Spector 唯一性定理|§5.8.3]] 介绍的"两层超算术构造"里，[[克利福德·斯佩克特|Spector]] 定理需要同时构造两个互相缠绕的函数；② [[Myhill-Shepherdson 定理]]（[[#有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理|§5.8.6]] 简述）描述"如何用 r.e. 集作为其它 r.e. 集的有效操作"时也需要联立不动点；③ 某些停机问题的"相对化"证明也走双递归路线<ref name="smullyan1961">'''Smullyan, R. M. (1961).''' ''Theory of Formal Systems''. Princeton University Press.【双递归定理的提出者；§[[#Smullyan 双递归定理（1959, 1961）|5.2.1]]】</ref><ref name="rogers1967" />. − − 另外，值得一提的是，这个双递归定理以及对应的n递归定理的推广形式，实际上可以看成是多个部分互相指涉，互相依赖的形式，因此也就构成了[[自创生理论]]（Autopoesis）的数学基础。 − − ==== Rogers 同构定理（1958） ==== − − 任意两个'''通用程序枚举'''（即枚举出所有可计算函数的程序编号系统，详见 [[#通用程序（解释器）|§2.2]]；下称 <math>\phi</math> 系统与 <math>\psi</math> 系统）之间，必然存在一个'''可计算同构''' <math>\rho</math>：<math>\mathbb{N} \to \mathbb{N}</math>——一部双向都可计算的"翻译词典"，把 <math>\phi</math> 系统里的每个程序号 <math>e</math> 送到 <math>\psi</math> 系统里的程序号 <math>\rho(e)</math>，并且 '''保 <math>\phi</math> 等价'''、'''保 W 等价'''。这两个"保…等价"是说：这部词典'''不改变任何行为事实'''。逐个拆开看： − − * '''<math>\phi</math> 等价'''：同一编号系统内，若两个程序 <math>e_1</math>、<math>e_2</math> 计算的是同一个（部分）函数（<math>\phi_{e_1} = \phi_{e_2}</math>，[[#"可计算"与"部分函数"|§2.1]]），就说它们 '''<math>\phi</math> 等价'''——编号只是程序的外衣，算出的函数才是实质。 − * '''保 <math>\phi</math> 等价'''：要求对每个程序号 <math>e</math> 成立 <math>\phi_e = \psi_{\rho(e)}</math>：<math>e</math> 在 <math>\phi</math> 系统里算什么函数，<math>\rho(e)</math> 在 <math>\psi</math> 系统里就算同一个函数。于是"算同一函数"的程序对，翻译后依然是"算同一函数"的对。 − * '''W 等价 / 保 W 等价'''：<math>W_e</math> 是程序 <math>e</math> 的定义域——会让它停机的输入集合（[[#递归可枚举集（r.e. set）|§2.4]]）。两个程序 '''W 等价'''指 <math>W_{e_1} = W_{e_2}</math>（接受的输入一模一样）；'''保 W 等价'''指翻译也不破坏这层对应。由于词条约定 <math>W_e = \text{dom}(\phi_e)</math>，"保 <math>\phi</math>"已自动带出"保 W"；Rogers 原版把两层并列，是因为他的框架允许"函数枚举"与"r.e. 集枚举"彼此独立（[[#r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|§5.8.5]] 索引集的 <math>\mathcal{A}</math> 用的正是独立于 <math>\phi</math> 的 W 层）。 − − 直觉上：两个不同的程序编号系统乍看像不同的语言（一个把 quine 编号成 42，另一个编号成 100），但实质上说的是同一类对象；Rogers 定理说它们之间必有可计算的"翻译词典"，且词典严格保结构。 − − 证明思路：把"取 <math>f(c)</math> = 在另一编号系统下对应于 <math>c</math> 的程序编号"作为变换规则，对它套 SRT 得到不动点 <math>c</math>——<math>c</math> 就是翻译词典的种子；之后逐条验证它保 <math>\phi</math>、W 等价性。[[#Rogers 同构定理（1958）|Rogers 同构定理]]常被引用作"程序编号系统的选择不影响可计算性理论"的根据——你可以挑任何合理的编号方式，得出的可计算性结论都一样<ref name="rogers1967" />。 − − ==== Arslanov 完全性判据（1981） ==== − − '''SRT 的相对化版本所给出的等价刻画'''：r.e. 集合 C 称为 r.e.-'''完全'''，当且仅当满足下面这一性质： − − * 对每个 r.e. 集合 <math>W</math>，存在一个可计算函数 <math>f_W</math> 使得 <math>W\leq_T C</math> 通过 <math>f_W</math> − − 这里一下子出现了三个新名字，先逐个解释： − − * '''r.e. 集合'''：见 [[#递归可枚举集（r.e. set）|§2.4]]。本词条统一用缩写 r.e.（recursively enumerable，[[递归可枚举集|递归可枚举]]）。 − * '''r.e.-完全'''：r.e. 集合这个"复杂度类别"里"最硬核"的一档——任何别的 r.e. 集合 <math>W</math> 都能机械地归约到 <math>C</math>，判定"<math>W</math> 含 <math>x</math>"等价于"问 <math>C</math>"。 − * '''Turing 归约 / <math>W\leq_T C</math> 通过 <math>f_W</math>'''：<math>A</math> 能 '''Turing 归约'''到 <math>B</math>（记 <math>A\leq_T B</math>），意思是"只要允许把 <math>B</math> 当'''神谕机（oracle，下一条解释）'''——可以向它提任意多个 yes/no 问题并瞬时得到回答——<math>A</math> 就能被判定"。等式 <math>W\leq_T C</math> 通过 <math>f_W</math> 即"编排提问方式的过程由可计算函数 <math>f_W</math> 给出，它把 <math>x</math> 改写成若干个向 <math>C</math> 的查询并综合出答案"。 − − 直觉上：[[R. R. Arslanov|Arslanov]] 判据说"装得下所有 r.e. 集合"等价于"对每个 r.e. 集合都有机械的相对化方式"——这和 SRT 中"对每个全可计算 <math>f</math> 都给出一个不动点"的相对化版本（relativized SRT）说的是同一件事：SRT 的相对化是说"对每个以 <math>C</math> 为'''神谕'''（oracle）可计算的 <math>f</math>，存在不动点 <math>c</math>"；Arslanov 判据说"对每个 <math>W</math>，存在以 <math>C</math> 为[[谕示机|神谕]]可计算的归约"。 − − [[Arslanov 判据]]在[[递归论]]里是教科书级工具：①用于证明 Gödel 不完备定理的算术陈述（"[[PA不一致]]"这种陈述）的相对可计算性与停机问题同构；② 用于证明某些 r.e. 集"不可能被简化"<ref name="arslanov1981">'''Arslanov, R. R. (1981).''' On a class of recursively enumerable sets. ''Algebra and Logic'', 20, 324–328.【Arslanov 完全性判据】【§[[#Arslanov 完全性判据（1981）|5.2.3]]】</ref><ref name="soare1987">'''Soare, R. I. (1987).''' ''Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets''. Berlin: Springer-Verlag.【r.e. 集与图灵度的标准教科书；Arslanov 完备性判据（§[[#Arslanov 完全性判据（1981）|5.2.3]]）与 Rice–Shapiro 等索引集定理（§[[#r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|5.8.5]]）的教科书出处】</ref> − 。
→推论：SRT 衍生出的若干重要结果
'''表述 C（带参数的强化形式）'''：A、B 只断言不动点"存在"，表述 C 进一步保证：不动点'''能被程序机械地找出来，并且能随参数连续变化'''。设想变换规则额外带一个参数 <math>y</math>——用一个三元函数 <math>\psi(e, y, x)</math> 表示"编号为 <math>e</math> 的程序在参数 <math>y</math> 下的行为"。那么存在一个可计算的全函数 <math>z</math>：你输入 <math>y</math>，它就输出针对这个参数的不动点编号 <math>z(y)</math>，使得 <math>\phi_{z(y)}(x) = \psi(z(y), y, x)</math> 对所有 <math>x</math> 成立。此外还能要求：①不动点不止一个，而是'''无穷多个'''；②不同参数 <math>y</math> 给出不同的编号（<math>z</math> 是'''单射'''，即一对一）<ref name="rogers1967" /><ref name="moschovakis2010" />。
'''表述 C（带参数的强化形式）'''：A、B 只断言不动点"存在"，表述 C 进一步保证：不动点'''能被程序机械地找出来，并且能随参数连续变化'''。设想变换规则额外带一个参数 <math>y</math>——用一个三元函数 <math>\psi(e, y, x)</math> 表示"编号为 <math>e</math> 的程序在参数 <math>y</math> 下的行为"。那么存在一个可计算的全函数 <math>z</math>：你输入 <math>y</math>，它就输出针对这个参数的不动点编号 <math>z(y)</math>，使得 <math>\phi_{z(y)}(x) = \psi(z(y), y, x)</math> 对所有 <math>x</math> 成立。此外还能要求：①不动点不止一个，而是'''无穷多个'''；②不同参数 <math>y</math> 给出不同的编号（<math>z</math> 是'''单射'''，即一对一）<ref name="rogers1967" /><ref name="moschovakis2010" />。
=== 证明 ===
=== 证明 ===