graph TD
subgraph grid["π(m,n) = 2^m(2n+1) - 1"]
direction TB
r0["m=0: π(0,0)=0 π(0,1)=2 π(0,2)=4 π(0,3)=6 ⋯"]
r1["m=1: π(1,0)=1 π(1,1)=5 π(1,2)=9 π(1,3)=13 ⋯"]
r2["m=2: π(2,0)=3 π(2,1)=11 π(2,2)=19 π(2,3)=27 ⋯"]
r3["m=3: π(3,0)=7 π(3,1)=23 π(3,2)=39 π(3,3)=55 ⋯"]
end
Goedel Number
Unlimited Register Machine
An Unlimited Register Machine (URM) is an idealized computer.
Definition: A URM has an infinite number of registers \(R_1,R_2,\ldots\), each of which can store a non-negative integer(natural number).
The registers can be equivalently written as for example \[ [r_1 r_2 r_3]_1^3 [r_4]_4^4[r_5r_6 \ldots]_5^\infty \]
Program: A URM program is a finite sequence of instructions.
| Type | Instruction | Response of the URM |
|---|---|---|
| Zero | \(Z(n)\) | Replace \(r_n\) by \(0\). |
| Successor | \(S(n)\) | Add \(1\) to \(r_n\). |
| Transfer | \(T(m,n)\) | Copy \(r_m\) to \(r_n\). |
| Jump | \(J(m,n,q)\) | If \(r_m = r_n\), go to the \(q\)-th instruction; otherwise go to the next instruction. |
Configuration and Computation
Configuration（配置）：寄存器的内容 + 当前指令指针。
Initial configuration（初始配置）：\(P(a_1, a_2, \ldots)\) 表示程序 \(P\) 以 \(r_1 = a_1, r_2 = a_2, \ldots\) 作为初始寄存器内容运行，未显式列出的寄存器初始值为 0。
Convergence and Divergence:
- \(P(a_1, \ldots, a_n) \downarrow\) 表示程序 \(P\) 在初始输入 \((a_1, \ldots, a_n)\) 上收敛（converge），即最终停机。
- \(P(a_1, \ldots, a_n) \uparrow\) 表示程序 \(P\)发散（diverge），即永远不停机。
- \(P(a_1, \ldots, a_n) \downarrow b\) 表示 \(P\) 停机且最终 \(r_1 = b\)。
NoteExample: Monus（截断减法）\(x \dot{-} y\)
程序 \(P\)：
| 指令 | 内容 |
|---|---|
| \(I_1\) | \(J(1, 2, 6)\) |
| \(I_2\) | \(S(2)\) |
| \(I_3\) | \(S(3)\) |
| \(I_4\) | \(J(1, 2, 6)\) |
| \(I_5\) | \(J(1, 1, 2)\) |
| \(I_6\) | \(T(3, 1)\) |
执行 \(P(9, 7)\)（即 \(r_1 = 9, r_2 = 7, r_3 = 0\)）的过程：
| Step | \(r_1\) | \(r_2\) | \(r_3\) | 执行 | 说明 |
|---|---|---|---|---|---|
| 1 | 9 | 7 | 0 | \(J(1,2,6)\): \(9 \neq 7\) | 继续 |
| 2 | 9 | 8 | 1 | \(S(2), S(3)\) | |
| 3 | 9 | 8 | 1 | \(J(1,2,6)\): \(9 \neq 8\) | |
| 4 | 9 | 9 | 2 | \(S(2), S(3)\), then \(J(1,2,6)\): \(9=9\) → goto 6 | |
| 5 | 2 | 9 | 2 | \(T(3,1)\): \(r_1 \leftarrow 2\) | 停机 |
结果：\(P(9,7) \downarrow 2 = 9 \dot{-} 7\)。
URM-Computable Functions
Definition: A URM program \(P\) URM-computes a function \(f : \mathbb{N}^n \to \mathbb{N}\) if for all \((a_1, \ldots, a_n) \in \mathbb{N}^n\):
\[ P(a_1, \ldots, a_n) \downarrow f(a_1, \ldots, a_n) \]
即 \(P\) 在输入 \((a_1, \ldots, a_n)\) 上停机，且 \(r_1\) 的最终值为 \(f(a_1, \ldots, a_n)\)。
A function \(f\) is URM-computable if there exists a URM program that computes it.
- \(\mathcal{C}\) 表示所有 URM 可计算函数的集合。
- \(\mathcal{C}_n\) 表示所有 \(n\) 元 URM 可计算函数的集合。
注意：\(f\) 可以是偏函数（partial function）——对某些输入 \(P\) 可能不停机。
NoteExample: URM Programs for Basic Functions
1. 加法 \(f(x, y) = x + y\)
| 指令 | 内容 |
|---|---|
| \(I_1\) | \(J(3, 2, 5)\) |
| \(I_2\) | \(S(1)\) |
| \(I_3\) | \(S(3)\) |
| \(I_4\) | \(J(1, 1, 1)\) |
思路：\(r_3\) 从 0 开始递增，每次 \(r_1\) 也加 1，直到 \(r_3 = r_2\)（即加了 \(y\) 次）。
2. 前驱 \(f(x) = x \dot{-} 1\)
| 指令 | 内容 |
|---|---|
| \(I_1\) | \(J(1, 2, 7)\) |
| \(I_2\) | \(S(3)\) |
| \(I_3\) | \(J(1, 3, 6)\) |
| \(I_4\) | \(S(2)\) |
| \(I_5\) | \(J(1, 1, 2)\) |
| \(I_6\) | \(T(2, 1)\) |
| \(I_7\) | \(Z(1)\) |
思路：\(r_2, r_3\) 交替递增，\(r_2\) 始终比 \(r_3\) 少 1，当 \(r_3 = r_1\) 时，\(r_2 = r_1 - 1\)。
3. 整除 \(f(x) = x \div 2\)（偏函数，\(x\) 为奇数时不停机）
| 指令 | 内容 |
|---|---|
| \(I_1\) | \(J(1, 2, 6)\) |
| \(I_2\) | \(S(2)\) |
| \(I_3\) | \(S(2)\) |
| \(I_4\) | \(S(3)\) |
| \(I_5\) | \(J(1, 1, 1)\) |
| \(I_6\) | \(T(3, 1)\) |
思路：\(r_2\) 每次加 2，\(r_3\) 每次加 1，当 \(r_2 = r_1\) 时 \(r_3 = x/2\)。若 \(x\) 为奇数则 \(r_2\) 永远跳过 \(r_1\)，不停机。
Church-Turing Thesis
Two Questions:
- How do different models of computation compare to each other?
- How do these models characterize the informal notion of effective computability?
Approaches:
- Gödel-Kleene: Partial recursive functions.
- Turing: Turing machines.
- Church: Lambda Calculus.
- Post: Post systems.
- Markov: Variants of the Post systems.
- Shepherdson-Sturgis: URM-computable functions.
Each of the above proposals for a characterization of the notion of effective computability gives rise to the same class of functions.
Church’s Thesis（丘奇论题）
Church’s Thesis: The intuitively and informally defined class of effectively computable partial functions coincides exactly with the class \(\mathcal{C}\) of URM-computable functions.
这不是一个数学定理（无法严格证明），而是一个关于数学与直觉之间关系的断言。
支撑 Church’s Thesis 的三个论据：
- All models agree（模型一致性）: 所有被提出的计算模型（TM, URM, \(\lambda\)-calculus, 递归函数…）定义了完全相同的函数类 \(\mathcal{C}\)。
- \(\mathcal{C}\) is extremely rich（丰富性）: \(\mathcal{C}\) 包含了人们能想到的一切”可计算”函数，其复杂程度远超直觉预期。
- No counterexample（无反例）: 从未有人构造出一个直觉上”可有效计算”但不在 \(\mathcal{C}\) 中的函数。
Proof by Church-Turing Thesis
在计算理论中，常用”Proof by Church-Turing Thesis”来简化论证：
若能用自然语言描述一个算法（即”there exists an effective procedure…“），则根据 Church-Turing Thesis，存在对应的 URM 程序（或 TM），即该函数属于 \(\mathcal{C}\)。
这使得我们在证明某个函数可计算时，不必每次都写出完整的 URM/TM 程序。
Gödel Number 1931
Essence
The set of the programs are countable.
More importantly, every program can be coded up effectively by a number in such a way that a unique program can be recovered from the number.
Denumerability and Enumerability
A set \(X\) is denumerable if there exists a bijection \(f : X \to \mathbb{N}\).
An enumeration of a set \(X\) is a surjective function \(g : \mathbb{N} \to X\), often written as \(\{x_0, x_1, x_2, \dots\}\), where \(x_n = g(n)\) for each \(n \in \mathbb{N}\).
The enumeration is without repetitions if \(g\) is also injective.
Let \(X\) be a set of finite objects (for example, finite strings over a finite alphabet). We say that \(X\) is effectively denumerable if there exists a bijection \(f : X \to \mathbb{N}\) such that both \(f\) and its inverse \(f^{-1}\) are effectively computable functions (i.e., there are algorithms that, given \(x \in X\), compute \(f(x)\), and given \(n \in \mathbb{N}\), compute \(f^{-1}(n)\)).
\(\mathbb{N} \times \mathbb{N}\) is Effectively Denumerable
Theorem: \(\mathbb{N} \times \mathbb{N}\) 是有效可枚举的。
Pairing function（配对函数）:
\[ \pi(m, n) = 2^m(2n + 1) - 1 \]
\(\pi\) 是双射，且 \(\pi\) 和 \(\pi^{-1}\) 都有效可计算。
逆函数：给定 \(k \in \mathbb{N}\)，将 \(k + 1\) 写成 \(2^m \cdot q\)（\(q\) 为奇数），则：
\[ \pi_1(k) = m, \quad \pi_2(k) = \frac{q - 1}{2} \]
\(\mathbb{N}^+ \times \mathbb{N}^+ \times \mathbb{N}^+\) is Effectively Denumerable
Theorem: \(\mathbb{N}^+ \times \mathbb{N}^+ \times \mathbb{N}^+\) 是有效可枚举的。
定义三元配对函数：
\[ \zeta(m, n, q) = \pi(\pi(m - 1, n - 1),\; q - 1) \]
其中 \(m, n, q \geq 1\)。\(\zeta\) 是双射，且有效可计算。
\(\bigcup_{k > 0} \mathbb{N}^k\) is Effectively Denumerable
Theorem: 所有有限长度自然数元组的集合 \(\bigcup_{k > 0} \mathbb{N}^k\) 是有效可枚举的。
定义元组编码函数 \(\tau\)：对 \((a_1, a_2, \ldots, a_k) \in \mathbb{N}^k\)，
\[ \tau(a_1, a_2, \ldots, a_k) = 2^{a_1} + 2^{a_1 + a_2 + 1} + 2^{a_1 + a_2 + a_3 + 2} + \cdots + 2^{a_1 + \cdots + a_k + (k-1)} - 1 \]
直觉：将 \(\tau(a_1, \ldots, a_k) + 1\) 的二进制表示看作 \(k\) 段，每段长度为 \(a_i + 1\)，段之间用 1 分隔。
Encoding Instructions: \(\beta\)
Theorem: URM 指令集 \(\mathcal{I}\) 是有效可枚举的。
定义双射 \(\beta : \mathcal{I} \to \mathbb{N}\)：
\[ \begin{aligned} \beta(Z(n)) &= 4(n - 1) \\ \beta(S(n)) &= 4(n - 1) + 1 \\ \beta(T(m, n)) &= 4\,\pi(m - 1, n - 1) + 2 \\ \beta(J(m, n, q)) &= 4\,\zeta(m, n, q) + 3 \end{aligned} \]
graph LR
I["Instruction"] --> TypeCheck{"Type?"}
TypeCheck -->|"Z(n)"| ZEnc["4(n-1)"]
TypeCheck -->|"S(n)"| SEnc["4(n-1) + 1"]
TypeCheck -->|"T(m,n)"| TEnc["4π(m-1,n-1) + 2"]
TypeCheck -->|"J(m,n,q)"| JEnc["4ζ(m,n,q) + 3"]
解码：给定 \(k \in \mathbb{N}\)，\(k \mod 4\) 决定指令类型，\(\lfloor k/4 \rfloor\) 编码参数。
Encoding Programs: \(\gamma\) (Gödel Number)
Theorem: URM 程序集 \(\mathcal{P}\) 是有效可枚举的。
对程序 \(P = I_1, I_2, \ldots, I_s\)，定义：
\[ \gamma(P) = \tau(\beta(I_1), \beta(I_2), \ldots, \beta(I_s)) \]
NoteDefinition: Gödel Number
\(\gamma(P)\) 称为程序 \(P\) 的 Gödel 数（哥德尔数）。
记 \(P_n = \gamma^{-1}(n)\)，即 Gödel 数为 \(n\) 的程序。
\(\gamma\) 是双射，且 \(\gamma\) 和 \(\gamma^{-1}\) 都有效可计算。这意味着：
- 给定程序 \(P\)，可以算出它的编号 \(\gamma(P)\)。
- 给定编号 \(n\)，可以还原出程序 \(P_n\)。
NoteExample: Encoding
程序 \(P\)：\(T(1, 3),\; S(4),\; Z(6)\)
Step 1：计算每条指令的编码。
\[ \begin{aligned} \beta(T(1, 3)) &= 4\,\pi(0, 2) + 2 = 4 \times 4 + 2 = 18 \\ \beta(S(4)) &= 4(4 - 1) + 1 = 13 \\ \beta(Z(6)) &= 4(6 - 1) = 20 \end{aligned} \]
Step 2：计算 \(\gamma(P) = \tau(18, 13, 20)\)。
\[ \gamma(P) = 2^{18} + 2^{18+13+1} + 2^{18+13+20+2} - 1 = 2^{18} + 2^{32} + 2^{53} - 1 \]
NoteExample: Decoding
给定 \(n = 4127\)，求 \(P_{4127}\)。
Step 1：\(4127 + 1 = 4128 = 2^5 + 2^{12} = 100000000000000100000_2\)
（二进制表示有两段 1，分隔位在第 5 和第 12 位。）
Step 2：\(\tau^{-1}(4127)\) 得到 \((5, 6)\)，即 \(\beta(I_1) = 5, \beta(I_2) = 6\)。
Step 3：解码指令。
\[ \begin{aligned} \beta^{-1}(5) &: 5 = 4 \times 1 + 1 \Rightarrow S(2) \\ \beta^{-1}(6) &: 6 = 4 \times 1 + 2 \Rightarrow T(\pi^{-1}(1) + (1,1)) = T(1+1, 0+1) = T(2, 1) \end{aligned} \]
\(\pi^{-1}(1)\): \(1+1 = 2 = 2^1 \times 1\)，所以 \(\pi_1(1) = 1, \pi_2(1) = 0\)，参数为 \((m,n) = (2, 1)\)。
结果：\(P_{4127} = S(2);\; T(2, 1)\)