可计算性理论

基础知识 编辑

计算机模型 编辑

原始递归和递归函数 编辑

可计算性 编辑

程序的编码 编辑

元计算程序 编辑

 

存在元计算程序   使得对任何编号为 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 定理 编辑

 

设模型  ,若   可数且不同构于   则:

  1.   为非递归模型;
  2.   为非递归函数。

第二不完备性定理 编辑

 

设 T 为延伸 PA 的递归可枚举理论,若   则 T 为不相容理论。

算数阶级 编辑

不动点定理 编辑

 

  为一递归函数,则存在 n 使对任意 x

 

且若两者都停机,则

  .

莱斯定理 编辑

 

  为自然数的一递归子集, 若对所有   满足   均有  , 则   .