更改

=== "可计算"与"部分函数" ===

=== "可计算"与"部分函数" ===

'''可计算的（computable / effective / recursive）'''：一个函数是"可计算的"，意思是存在一套'''固定的、有穷的指令'''（程序），使得对任何输入，只要机械地按指令执行有穷多步，就能得到输出。"可计算的"（computable）、"有效的"（effective）、"递归的"（recursive）在本文中是同义词——这是历史造成的术语冗余，三个词来自 Church、Turing、Gödel–Kleene 三条等价的技术路线<ref name="kleene1938" />。

'''[[可计算的]]（computable / effective / recursive）'''：一个函数是"可计算的"，意思是存在一套'''固定的、有穷的指令'''（程序），使得对任何输入，只要机械地按指令执行有穷多步，就能得到输出。"可计算的"（computable）、"有效的"（effective）、"递归的"（recursive）在本文中是同义词——这是历史造成的术语冗余，三个词来自 Church、Turing、Gödel–Kleene 三条等价的技术路线<ref name="kleene1938" />。

'''部分函数（partial function）'''：一台机器在某些输入上可能'''永远不停机'''（死循环），这时它在这些输入上'''没有输出'''。我们把"在部分输入上有定义、在其余输入上无定义"的函数称为部分函数；在所有输入上都有定义的称为'''全函数（total function）'''。程序天然对应部分函数，而不是数学课本里那种"处处有值"的函数——这是可计算性理论与普通数学的第一个思维差异。

'''[[部分函数]]（partial function）'''：一台机器在某些输入上可能'''永远不停机'''（死循环），这时它在这些输入上'''没有输出'''。我们把"在部分输入上有定义、在其余输入上无定义"的函数称为部分函数；在所有输入上都有定义的称为'''[[全函数]]（total function）'''。程序天然对应部分函数，而不是数学课本里那种"处处有值"的函数——这是可计算性理论与普通数学的第一个思维差异。

'''记号 <math>\phi_e</math>'''：把全体程序（的所有可计算部分函数）排成一个序列，用自然数 0, 1, 2, <math>\ldots</math> 编号，'''<math>\phi_e</math> 表示"编号为 e 的程序所计算的那个部分函数"'''。这个编号也叫'''哥德尔数（Gödel number）'''：关键思想是"程序本身也是一个有限符号串，可以编码成一个自然数"，于是'''程序即数据'''——程序可以作为另一个程序的输入被处理。<math>\phi_e(x)</math> 表示"编号 e 的程序在输入 x 上的输出"（可能无定义）。本文中 p <math>\downarrow</math> 表示"程序 p 停机（有输出）"，p <math>\uparrow</math> 表示"不停机（无输出）"。

'''记号 <math>\phi_e</math>'''：把全体程序（的所有可计算部分函数）排成一个序列，用自然数 0, 1, 2, <math>\ldots</math> 编号，'''<math>\phi_e</math> 表示"编号为 e 的程序所计算的那个部分函数"'''。这个编号也叫'''[[哥德尔配数]]（Gödel number）'''：关键思想是"程序本身也是一个有限符号串，可以编码成一个自然数"，于是'''程序即数据'''——程序可以作为另一个程序的输入被处理。<math>\phi_e(x)</math> 表示"编号 <math>e</math> 的程序在输入 <math>x</math> 上的输出"（可能无定义）。本文中 <math>p \downarrow</math> 表示"程序 <math>p</math> 停机（有输出）"，<math>p \uparrow</math> 表示"不停机（无输出）"。

=== 通用程序（解释器） ===

=== 通用程序（解释器） ===

存在一台"通用机器"：给它输入 (e, x)，它就'''模拟'''编号 e 的程序在输入 x 上的运行。这就是今天的'''解释器 / 虚拟机'''思想，Turing 1936 年的[[通用图灵机]]是它的首个化身。用记号写就是：存在程序 i 使得 <math>\phi_i(e, x) = \phi_e(x)</math>。<ref name="rogers1967" />

存在一台"通用机器"：给它输入 <math>(e, x)</math>，它就'''模拟'''编号 <math>e</math> 的程序在输入 <math>x</math> 上的运行。这就是今天的'''解释器 / 虚拟机'''思想，Turing 1936 年的[[通用图灵机]]是它的首个化身。用记号写就是：存在程序<math>i</math> 使得 <math>\phi_i(e, x) = \phi_e(x)</math>。<ref name="rogers1967" />

=== S-m-n 定理（柯里化 / 参数特化） ===

=== S-m-n 定理（柯里化 / 参数特化） ===

'''S-m-n 定理'''说：给定一个双输入程序和它的'''第一个输入'''，可以机械地生成一个"把第一个输入写死在程序里"的新单输入程序。用程序员的话说，就是'''柯里化（currying）或部分应用（partial application）总是可以机械完成的'''：存在可计算的全函数 S，使得

'''S-m-n 定理'''说：给定一个双输入程序和它的'''第一个输入'''，可以机械地生成一个"把第一个输入写死在程序里"的新单输入程序。用程序员的话说，就是'''柯里化（currying）或部分应用（partial application）总是可以机械完成的'''：存在可计算的全函数 S，使得

> <math>\phi_{S(e, y)}(x) = \phi_e(y, x)</math>

: <math>\phi_{S(e, y)}(x) = \phi_e(y, x)</math>

即"程序 S(e,y)"在输入 x 上的行为 = "程序 e"在输入 (y, x) 上的行为。Kleene 1938 年论文中的 S 函数就是这个工具<ref name="kleene1938" />。'''第二递归定理的证明只需要这一个工具'''，此外什么都不需要——这是它惊人简单的原因。

即"程序 <math>S(e,y)</math>"在输入 <math>x</math> 上的行为 = "程序 <math>e</math>"在输入 <math>(y, x)</math> 上的行为。Kleene 1938 年论文中的 S 函数就是这个工具<ref name="kleene1938" />。'''第二递归定理的证明只需要这一个工具'''，此外什么都不需要——这是它惊人简单的原因。

=== 递归可枚举集（r.e. set） ===

=== 递归可枚举集（r.e. set） ===

一个自然数集合称为'''递归可枚举的（recursively enumerable, r.e.）'''，如果存在一台机器能把它的元素'''一个一个地全部列出来'''（允许重复、允许乱序；不在集合里的元素永远不会被列出）。等价地，r.e. 集就是某个程序'''有定义的输入的集合'''（即 <math>\phi_e</math> 的定义域），记作 <math>W_e</math>。典型例子："所有会停机的 (程序,输入) 对"构成的集合（停机问题集合 K）是 r.e. 的，但它的补集不是——这正是"停机问题不可判定"的现代表述。

一个自然数集合称为'''递归可枚举的（recursively enumerable, r.e.）'''，如果存在一台机器能把它的元素'''一个一个地全部列出来'''（允许重复、允许乱序；不在集合里的元素永远不会被列出）。等价地，r.e. 集就是某个程序'''有定义的输入的集合'''（即 <math>\phi_e</math> 的定义域），记作 <math>W_e</math>。典型例子："所有会停机的 (程序,输入) 对"构成的集合（停机问题集合 <math>K</math>）是 r.e. 的，但它的补集不是——这正是"停机问题不可判定"的现代表述。

=== "不动点"的两种含义（重要！） ===

=== "不动点"的两种含义（重要！） ===

"不动点"在本文中出现于两个截然不同的层面，混淆它们是最常见的理解障碍：

"不动点"在本文中出现于两个截然不同的层面，混淆它们是最常见的理解障碍：

- '''函数层面的不动点'''（[[#第一递归定理（FRT）|第一递归定理]]）：变换规则 <math>\Psi</math> 把函数 <math>\phi</math> 变成新函数 <math>\Psi(\phi)</math>；若 <math>\Psi(\phi) = \phi</math>（作为函数处处相等），<math>\phi</math> 就是 <math>\Psi</math> 的不动点。这与分析学中"f(x) = x 的解"同类。

- '''函数层面的不动点'''（[[#第一递归定理（FRT）|第一递归定理]]）：变换规则 <math>\Psi</math> 把函数 <math>\phi</math> 变成新函数 <math>\Psi(\phi)</math>；若 <math>\Psi(\phi) = \phi</math>（作为函数处处相等），<math>\phi</math> 就是 <math>\Psi</math> 的不动点。这与分析学中"<math>f(x) = x</math> 的解"同类。

- '''代码层面的不动点'''（第二递归定理）：变换规则 f 把程序编号 n 变成新编号 f(n)；'''注意 f(n) <math>\neq n</math> 通常成立'''——程序代码确实变了；但神奇的是，新程序 f(n) 和旧程序 n '''计算的函数相同'''：<math>\phi_n = \phi_{f(n)}</math>。所以"不动"的不是代码，而是'''代码的行为'''。[[Hartley Rogers, Jr|Rogers]] 为此特意造了"'''不动点值'''（fixed-point value）"一词，强调它不是数值不动点<ref name="rogers1967" />。

- '''代码层面的不动点'''（第二递归定理）：变换规则 <math>f</math> 把程序编号 <math>n</math> 变成新编号 <math>f(n)</math>；'''注意 <math>f(n)\neq n</math> 通常成立'''——程序代码确实变了；但神奇的是，新程序 <math>f(n)</math> 和旧程序 <math>n</math> '''计算的函数相同'''：<math>\phi_n = \phi_{f(n)}</math>。所以"不动"的不是代码，而是'''代码的行为'''。[[Hartley Rogers, Jr|Rogers]] 为此特意造了"'''不动点值'''（fixed-point value）"一词，强调它不是数值不动点<ref name="rogers1967" />。

 

== 历史背景 ==

== 历史背景 ==