可計算性理論

可計算性

元計算程序

存在元計算程序 $\Psi$ 使得對任何編號為 n 的程序 P， $\Psi (n,x)$ 與 $P(x)$ 計算的函數完全一致。

停機問題

定義函數 $h:\mathbb {N} ^{2}\to \mathbb {N}$ 如下: $\displaystyle {h(n,x):={\begin{cases}1&\Psi (n,x)\downarrow \\0&\Psi (n,x)\uparrow \\\end{cases}}}$ 則 $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\vDash {\text{PA}}$，若 $M$ 可數且不同構於 $\mathbb {N}$ 則： $M$ 為非遞歸模型； $+^{M},\cdot ^{M}$ 為非遞歸函數。

第二不完備性定理

設 T 為延伸 PA 的遞歸可枚舉理論，若 $T\vdash \operatorname {Cons} T$ 則 T 為不相容理論。

不動點定理

設 $f:\mathbb {N} \to \mathbb {N}$ 為一遞歸函數，則存在 n 使對任意 x $\displaystyle {\Psi (n,x)\downarrow \iff \Psi (f(n),x)\downarrow }$ 且若兩者都停機，則 $\displaystyle {\Psi (n,x)=\Psi (f(n),x)}$ .

萊斯定理

設 $I\subseteq \mathbb {N}$ 為自然數的一遞歸子集, 若對所有 $e_{1},e_{2}$ 滿足 $\displaystyle {W_{e_{1}}=W_{e_{2}}}$ 均有 $e_{1}\in I\iff e_{2}\in I$, 則 $I=\varnothing$ 或 $I=\mathbb {N}$.