更改

跳到导航 跳到搜索
删除22字节 、 2026年9月8日 (星期二)
第140行: 第140行:  
# '''可计算性''':<math>\phi</math> 是可计算的部分函数。
 
# '''可计算性''':<math>\phi</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>\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" />。
+
'''例子''':方程组 <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" />。
    
=== 意义:递归定义的"存在性定理" ===
 
=== 意义:递归定义的"存在性定理" ===

导航菜单