查看“︁可计算性理论”︁的源代码

==基础知识==

==计算机模型==

==原始递归和递归函数==

==可计算性==
===程序的编码===

===元计算程序===
{{theorem|
存在元计算程序 <math>\Psi</math> 使得对任何编号为 n 的程序 P，
<math>\Psi(n,x)</math> 与 <math>P(x)</math>
计算的函数完全一致。}}

===停机问题===
{{theorem|
定义函数 <math>h:\mathbb{N}^2\to\mathbb{N}</math> 如下:

<math>\displaystyle{h(n,x):=\begin{cases}
1 & \Psi(n,x)\downarrow \\
0 & \Psi(n,x)\uparrow \\
\end{cases}}</math>

则 <math>h</math> 不是递归函数.}}

'''证明.''' 设 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 不是递归函数. (证毕)

==递归集合和递归可枚举集合==

==第一不完备性定理==
{{theorem|
设 T 为延伸 PA 的理论，若 T 相容且递归可枚举，则 T 为不完备理论。}}

===符号证明===

===模型论证明===
====Tennenbaum 定理====
{{theorem|
设模型 <math>M\vDash\text{PA}</math>，若 <math>M</math> 可数且不同构于 <math>\mathbb{N}</math> 则：

# <math>M</math> 为非递归模型；
# <math>+^M, \cdot^M</math> 为非递归函数。
}}

==第二不完备性定理==
{{theorem|
设 T 为延伸 PA 的递归可枚举理论，若 <math>T\vdash\operatorname{Cons}T</math> 则 T 为不相容理论。}}

==算数阶级==

==不动点定理==
{{theorem|
设 <math>f:\mathbb{N}\to\mathbb{N}</math> 为一递归函数，则存在 n 使对任意 x

<math>\displaystyle{\Psi(n,x)\downarrow\iff\Psi(f(n),x)\downarrow}</math>

且若两者都停机，则
 
<math>\displaystyle{\Psi(n,x)=\Psi(f(n),x)}</math> .}}

===莱斯定理===
{{theorem|
设 <math>I\subseteq\mathbb{N}</math> 为自然数的一递归子集,
若对所有 <math>e_1, e_2</math> 满足 <math>\displaystyle{W_{e_1}=W_{e_2}}</math> 均有 <math>e_1\in I\iff e_2\in I</math>, 则 <math>I=\varnothing</math> 或 <math>I=\mathbb{N}</math>. }}