更改

=== 推论：SRT 衍生出的若干重要结果 ===

=== 推论：SRT 衍生出的若干重要结果 ===

> SRT 不是孤岛，但也不能把整片大陆都记在它名下。本节收录三条'''真正以 SRT 为证明枢纽'''的结果——它们的证明都必经 SRT，称"推论"名副其实：

SRT 不是孤岛，但也不能把整片大陆都记在它名下。本节收录三条'''真正以 SRT 为证明枢纽'''的结果——它们的证明都必经 SRT，称"推论"名副其实：

 

> - '''§5.2.1 Smullyan 双递归定理'''——SRT 的"联立化"推广：一次造出两个互相引用对方代码的程序（可推广到 k 个），是后续许多构造的通用工具；

* '''[[Smullyan 双递归定理]]'''——SRT 的"联立化"推广：一次造出两个互相引用对方代码的程序（可推广到 <math>k</math> 个），是后续许多构造的通用工具；

> - '''§5.2.2 Rogers 同构定理'''——SRT 的"编号[[独立性 (数学)|独立性]]"推论：任意两个[[通用图灵机|通用程序]]枚举之间必有保结构的可计算同构；

* '''[[Rogers 同构定理]]'''——SRT 的"编号[[独立性 (数学)|独立性]]"推论：任意两个[[通用图灵机|通用程序]]枚举之间必有保结构的可计算同构；

> - '''§5.2.3 Arslanov 完全性判据'''——相对化 SRT 的"刻画性"等价定理：一个 r.e. 集何时是 r.e.-完备的。

* '''[[Arslanov 完全性判据]]'''——相对化 SRT 的"刻画性"等价定理：一个 r.e. 集何时是 [[r.e.-完备的]]。

> 常被误归为 SRT 推论的 '''Rice 定理'''与 '''Rice-Shapiro 定理'''不在此列：Rice 的教科书证明是停机[[归约 (数学)]]（对角线矛盾），Rice-Shapiro 是"有限可生成"的结构定理，两者都不依赖 SRT（SRT 至多为 Rice 提供一条事后捷径）。它们属于 r.e. '''索引集理论'''，与 SRT 的关系是"同源，但独立"——因此移至 §6.5，与真正依赖 SRT 的 [[#Myhill 定理：创造集 = 完备集|Myhill 定理]]并置，以对照这两种不同关系。

==== Smullyan 双递归定理（1959, 1961） ====

==== Smullyan 双递归定理（1959, 1961） ====

'''SRT 的联立推广'''：对任意两个全可计算函数 g, h（不一定全），存在两个程序 m, n 使得

'''SRT 的联立推广'''：对任意两个全可计算函数 <math>g</math>, <math>h</math>（不一定全），存在两个程序 <math>m, n</math> 使得

> <math>\phi_m(x) = g(\langle m, n\rangle, x)</math>，<math>\phi_n(x) = h(\langle m, n\rangle, x)</math>

: <math>

\phi_m(x) = g(\langle m, n\rangle, x)\\

\phi_n(x) = h(\langle m, n\rangle, x)

</math>

——两个程序可以'''互相引用对方的代码'''。这是 SRT 的"二元推广"，可直接由 SRT 套用：

——两个程序可以'''互相引用对方的代码'''。这是 SRT 的"二元推广"，可直接由 SRT 套用：

1. 先用 S-m-n（§2.3）构造两个可计算函数 <math>\psi_1(x) = g(S(x, x), x)</math>、<math>\psi_2(x) = h(S(x, x), x)</math>，二者均依赖自身编号；

# 先用 s-m-n（§2.3）构造两个可计算函数 <math>\psi_1(x) = g(S(x, x), x)</math>、<math>\psi_2(x) = h(S(x, x), x)</math>，二者均依赖自身编号；

2. 对 <math>\psi_1</math> 套 SRT 拿到不动点 m；

# 对 <math>\psi_1</math> 套 SRT 拿到不动点 <math>m</math>；

3. m 唯一确定后，n 由 <math>\phi_n = \psi_2(m)</math> 的不动点结构给出。

# <math>m</math> 唯一确定后，<math>n</math> 由 <math>\phi_n = \psi_2(m)</math> 的不动点结构给出。

推广到 k 元：对任意 k 个全可计算函数 <math>g_1</math>, <math>\ldots</math>, <math>g_k</math>，存在 k 个程序 <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>。

推广到 <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）|双递归定理]]是后续许多重要构造的核心：① §6.3 介绍的"两层超算术构造"里，[[克利福德·斯佩克特|Spector]] 定理需要同时构造两个互相缠绕的函数；②Myhill-Shepherdson 定理（§6.6 简述）描述"如何用 r.e. 集作为其它 r.e. 集的有效操作"时也需要联立不动点；③某些停机问题的"相对化"证明也走双递归路线。<ref name="smullyan1961" /><ref name="rogers1967" />

[[#Smullyan 双递归定理（1959, 1961）|双递归定理]]是后续许多重要构造的核心：① §6.3 介绍的"两层超算术构造"里，[[克利福德·斯佩克特|Spector]] 定理需要同时构造两个互相缠绕的函数；② Myhill-Shepherdson 定理（§6.6 简述）描述"如何用 r.e. 集作为其它 r.e. 集的有效操作"时也需要联立不动点；③ 某些停机问题的"相对化"证明也走双递归路线。<ref name="smullyan1961" /><ref name="rogers1967" />

==== Rogers 同构定理（1958） ====

==== Rogers 同构定理（1958） ====