可计算性理论

可计算性

元计算程序

存在元计算程序 $\mathrm{\Psi }$ 使得对任何编号为 n 的程序 P， $\mathrm{\Psi }(n,x)$ 与 $P(x)$ 计算的函数完全一致。

停机问题

定义函数 $h:{\mathbb{N}}^2\to \mathbb{N}$ 如下: $h(n,x):=\{\begin{array}{cc}1& \mathrm{\Psi }(n,x)\downarrow \\ 0& \mathrm{\Psi }(n,x)\uparrow \end{array}$ 则 $h$ 不是递归函数.

证明. 设 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 定理

设模型 $M\models \text{PA}$，若 $M$ 可数且不同构于 $\mathbb{N}$ 则： $M$ 为非递归模型； ${+}^M,{\cdot }^M$ 为非递归函数。

第二不完备性定理

设 T 为延伸 PA 的递归可枚举理论，若 $T⊢\mathrm{Cons}T$ 则 T 为不相容理论。

不动点定理

设 $f:\mathbb{N}\to \mathbb{N}$ 为一递归函数，则存在 n 使对任意 x $\mathrm{\Psi }(n,x)\downarrow ⟺\mathrm{\Psi }(f(n),x)\downarrow$ 且若两者都停机，则 $\mathrm{\Psi }(n,x)=\mathrm{\Psi }(f(n),x)$ .

莱斯定理

设 $I\subseteq \mathbb{N}$ 为自然数的一递归子集, 若对所有 $e_1,e_2$ 满足 $W_{e_1}=W_{e_2}$ 均有 $e_1\in I⟺e_2\in I$, 则 $I=\varnothing$ 或 $I=\mathbb{N}$.