更改

'''定义（可计算的变换规则）'''：如果变换 <math>\Psi</math> 满足下面两条，就称它是'''[[递归算子]]（recursive operator）'''：

'''定义（可计算的变换规则）'''：如果变换 <math>\Psi</math> 满足下面两条，就称它是'''[[递归算子]]（recursive operator）'''：

# '''单调性'''：<math>\phi \subseteq \psi</math>（即 <math>\psi</math> 在 <math>\phi</math> 有定义的地方都有定义且取值相同）蕴含 <math>\Psi(\phi) \subseteq \Psi(\psi)</math>；

# '''单调性'''：<math>\alpha \subseteq \beta</math>（即 <math>\beta</math> 在 <math>\alpha</math> 有定义的地方都有定义且取值相同）蕴含 <math>\Psi(\alpha) \subseteq \Psi(\beta)</math>；

# '''有限性/连续性'''：<math>\Psi(\phi)</math> 的每个输出只依赖 <math>\phi</math> 在'''有限个'''输入上的值。

# '''有限性/连续性'''：<math>\Psi(\alpha)</math> 的每个输出只依赖 <math>\alpha</math> 在'''有限个'''输入上的值。

直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。[[阶乘]]、[[斐波那契数列]]、以及绝大多数程序语言中的递归定义都满足这两条<ref name="rogers1967" />.

直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化表达。[[阶乘]]、[[斐波那契数列]]、以及绝大多数程序语言中的递归定义都满足这两条<ref name="rogers1967" />.

'''第一递归定理'''：设 <math>\Psi</math> 是递归算子，则存在函数 <math>\phi</math> 使得：

'''第一递归定理'''：设 <math>\Psi</math> 是递归算子，则存在函数 <math>\alpha</math> 使得：

# <math>\Psi(\phi) = \phi</math>（<math>\phi</math> 是方程的解，即 <math>\Psi</math> 的不动点）；

# <math>\Psi(\alpha) = \alpha</math>（<math>\alpha</math> 是方程的解，即 <math>\Psi</math> 的不动点）；

# '''最小性'''：任何其他解 <math>\psi</math> 都满足 <math>\phi \subseteq \psi</math>（<math>\phi</math> 是"信息最少"的解）；

# '''最小性'''：任何其他解 <math>\beta</math> 都满足 <math>\alpha \subseteq \beta</math>（<math>\alpha</math> 是"信息最少"的解）；

# '''可计算性'''：<math>\phi</math> 是可计算的部分函数。

# '''可计算性'''：<math>\alpha</math> 是可计算的部分函数。

'''证明思路'''：从"处处无定义的空函数"出发，反复应用 <math>\Psi</math>：<math>\phi_0</math> = 空，<math>\phi_1 = \Psi(\phi_0)</math>，<math>\phi_2 = \Psi(\phi_1),\ldots\ldots</math>。单调性保证这个序列不断"变长"（每次迭代只增不减）；有限性保证最终收敛到一个函数 <math>\phi</math>，且 <math>\Psi(\phi) = \phi</math>；"每一步都是机械操作"保证 <math>\phi</math> 整体可计算。取所有 <math>\phi_n</math>的并就是答案<ref name="rogers1967" />。

'''证明思路'''：从"处处无定义的空函数"出发，反复应用 <math>\Psi</math>：<math>\alpha_0=\empty</math>，<math>\alpha_1 = \Psi(\alpha_0)</math>，<math>\alpha_2 = \Psi(\alpha_1),\ldots\ldots</math>。单调性保证这个序列不断"变长"（每次迭代只增不减）；有限性保证最终收敛到一个函数 <math>\alpha</math>，且 <math>\Psi(\alpha) = \alpha</math>；"每一步都是机械操作"保证 <math>\alpha</math> 整体可计算。取所有 <math>\alpha_n</math>的并就是答案<ref name="rogers1967" />。

'''例子'''：方程组 <math>\phi(1) = 2</math>，<math>\phi(2x) = 2\phi(x)</math> 对应一个递归算子，其最小不动点是：<math>\phi(x) = x</math>（当 <math>x</math> 是 2 的幂），其余输入无定义。注意"最小性"自动处理了定义不完整的分支——机器在"非 2 的幂"上自然发散<ref name="rogers1967" />。

'''例子'''：方程组 <math>\alpha(1) = 2</math>，<math>\alpha(2x) = 2\alpha(x)</math> 对应一个递归算子，其最小不动点是：<math>\alpha(x) = x</math>（当 <math>x</math> 是 2 的幂），其余输入无定义。注意"最小性"自动处理了定义不完整的分支——机器在"非 2 的幂"上自然发散<ref name="rogers1967" />。

=== 意义：递归定义的"存在性定理" ===

=== 意义：递归定义的"存在性定理" ===