更改
跳到导航
跳到搜索
←上一编辑
下一编辑→
递归定理
(查看源代码)
2026年9月8日 (二) 14:57的版本
删除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" />。
=== 意义:递归定义的"存在性定理" ===
=== 意义:递归定义的"存在性定理" ===
Jake
行政员
、
界面管理员
、
管理员
3,094
个编辑
导航菜单
个人工具
登录
名字空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
集智百科
集智主页
集智斑图
集智学园
最近更改
所有页面
捐赠我们
帮助
工具
特殊页面
可打印版本