3,094
个编辑
更改
→定理表述
=== 定理表述 ===
=== 定理表述 ===
'''定义（可计算的变换规则）'''：如果变换 <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>\Psi(\phi)</math> 的每个输出只依赖 <math>\phi</math> 在'''有限个'''输入上的值。
直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。阶乘、斐波那契、以及绝大多数程序语言中的递归定义都满足这两条。<ref name="rogers1967" />
直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。[[阶乘]]、[[斐波那契数列]]、以及绝大多数程序语言中的递归定义都满足这两条<ref name="rogers1967" />.
* '''第一递归定理'''：设 <math>\Psi</math> 是递归算子，则存在函数 <math>\phi</math> 使得：
# <math>\Psi(\phi) = \phi</math>（<math>\phi</math> 是方程的解，即 <math>\Psi</math> 的不动点）；
# '''最小性'''：任何其他解 <math>\psi</math> 都满足 <math>\phi \subseteq \psi</math>（<math>\phi</math> 是"信息最少"的解）；
# '''可计算性'''：<math>\phi</math> 是可计算的部分函数。
'''例子'''：方程组 <math>\phi(1) = 2</math>，<math>\phi(2x) = 2</math><math>\phi(x)</math> 对应一个递归算子，其最小不动点是：<math>\phi(x) = x</math>（当 x 是 2 的幂），其余输入无定义。注意"最小性"自动处理了定义不完整的分支——机器在"非 2 的幂"上自然发散。<ref name="rogers1967" />
* '''证明思路'''（两分钟版）：从"处处无定义的空函数"出发，反复应用 <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>\phi(1) = 2</math>，<math>\phi(2x) = 2\phi(x)</math> 对应一个递归算子，其最小不动点是：<math>\phi(x) = x</math>（当 <math>x</math> 是 2 的幂），其余输入无定义。注意"最小性"自动处理了定义不完整的分支——机器在"非 2 的幂"上自然发散<ref name="rogers1967" />。
=== 意义：递归定义的"存在性定理" ===
=== 意义：递归定义的"存在性定理" ===