可计算性理论
基础知识
编辑计算机模型
编辑原始递归和递归函数
编辑可计算性
编辑程序的编码
编辑元计算程序
编辑
存在元计算程序 使得对任何编号为 n 的程序 P, 与 计算的函数完全一致。 |
停机问题
编辑
定义函数 如下:
则 不是递归函数. |
证明. 设 h 为递归函数, 则存在程序 P 计算 h.
设计程序 Q(n) 如下. 运行程序 P(n, n), 若返回 0 则停机, 若返回 1 则进入无限循环.
令 m 为 Q 的编号. 假定 P(m, m) 返回 1, 说明 Q(m) 停机, 但是 Q(m) 停机当且仅当 P(m, m) 返回 0, 自相矛盾.
同理,假定 P(m, m) 返回 0, 说明 Q(m) 无限循环, 但是 Q(m) 无限循环当且仅当 P(m, m) 返回 1, 自相矛盾.
以此推定, h 不是递归函数. (证毕)
递归集合和递归可枚举集合
编辑第一不完备性定理
编辑
设 T 为延伸 PA 的理论,若 T 相容且递归可枚举,则 T 为不完备理论。 |
符号证明
编辑模型论证明
编辑Tennenbaum 定理
编辑
设模型 ,若 可数且不同构于 则:
|
第二不完备性定理
编辑
设 T 为延伸 PA 的递归可枚举理论,若 则 T 为不相容理论。 |
算数阶级
编辑不动点定理
编辑
设 为一递归函数,则存在 n 使对任意 x
且若两者都停机,则 . |
莱斯定理
编辑
设 为自然数的一递归子集, 若对所有 满足 均有 , 则 或 . |