更改

第二递归定理诞生于 Kleene 1938 年发表于《符号逻辑杂志》（''The Journal of Symbolic Logic''）的一篇仅 6 页的短文《论序数的记号》（''On Notation for Ordinal Numbers''）<ref name="kleene1938" />。这篇论文的主题表面上与"递归定理"毫不相干：

第二递归定理诞生于 Kleene 1938 年发表于《符号逻辑杂志》（''The Journal of Symbolic Logic''）的一篇仅 6 页的短文《论序数的记号》（''On Notation for Ordinal Numbers''）<ref name="kleene1938" />。这篇论文的主题表面上与"递归定理"毫不相干：

: '''背景知识——[[序数]]（ordinal number）'''：序数是"无限队列的长度"的数学化。数完 0, 1, 2, 3, <math>\ldots</math>（全体自然数）之后，数学上允许继续数：第一个"超过所有自然数"的序数记作 <math>\omega</math>，然后还有 <math>\omega+1</math>, <math>\omega+2</math>, <math>\ldots</math>, <math>\omega\cdot2</math>, <math>\ldots</math>, <math>\omega^2</math>, <math>\ldots</math>, <math>\omega^\omega</math>, <math>\ldots</math>，可以无限延伸。所有"能用可数步骤达到"的序数称为'''[[可数序数]]'''，它们的总体（第二数类）是不可数的。

'''背景知识——[[序数]]（ordinal number）'''：序数是"无限队列的长度"的数学化。数完 0, 1, 2, 3, <math>\ldots</math>（全体自然数）之后，数学上允许继续数：第一个"超过所有自然数"的序数记作 <math>\omega</math>，然后还有 <math>\omega+1</math>, <math>\omega+2</math>, <math>\ldots</math>, <math>\omega\cdot2</math>, <math>\ldots</math>, <math>\omega^2</math>, <math>\ldots</math>, <math>\omega^\omega</math>, <math>\ldots</math>，可以无限延伸。所有"能用可数步骤达到"的序数称为'''[[可数序数]]'''，它们的总体（第二数类）是不可数的。

: Church 与 Kleene 在 1930 年代问了一个构造性问题：'''能不能给每个可数序数起一个"机械可读的代号"（自然数编码），使得仅凭代号就能机械地判断：这个序数是 0、是某个序数的后继（+1）、还是某个递增序列的极限？并且在后两种情况下能机械地取出前驱代号或序列代号？''' 满足这些条件的编码方案称为一个'''序数记号系统'''（Kleene 称之为 [[r-system]]）<ref name="kleene1938" />。

Church 与 Kleene 在 1930 年代问了一个构造性问题：'''能不能给每个可数序数起一个"机械可读的代号"（自然数编码），使得仅凭代号就能机械地判断：这个序数是 0、是某个序数的后继（+1）、还是某个递增序列的极限？并且在后两种情况下能机械地取出前驱代号或序列代号？''' 满足这些条件的编码方案称为一个'''[[序数记号系统]]'''（Kleene 称之为 [[r-system]]）<ref name="kleene1938" />。

Kleene 在论文 §2 中建立了[[可计算函数]]的基本技术（编号、通用函数、§2.3 的 S 函数），然后在 §2 的最后'''顺手'''陈述并证明了一个当时没有名字的定理<ref name="kleene1938" />：

Kleene 在论文的 §2 中建立了[[可计算函数]]的基本技术（编号、[[通用函数]]、§2.3 的 [[S函数]]），然后在 §2 的最后'''顺手'''陈述并证明了一个当时没有名字的定理<ref name="kleene1938" />：

: '''若 <math>\psi(z, x)</math> 是任意可计算的部分函数，则存在一个数 f，使得 <math>\phi_f(x) = \psi(f, x)</math> 对所有 x 成立（等号含义：两边同时无定义，或同时有定义且相等）。'''

'''若 <math>\psi(z, x)</math> 是任意可计算的部分函数，则存在一个数 <math>f</math>，使得 <math>\phi_f(x) = \psi(f, x)</math> 对所有 <math>x</math> 成立（等号含义：两边同时无定义，或同时有定义且相等）。'''

: 证明：设 e 是函数 <math>\psi(S(y,y), x)</math> 的编号，取 f = S(e, e) 即可。

——这就是'''第二递归定理'''的原始形态。Moschovakis 称之为 Kleene 没有意识到自己发掘出&#x7684;'''"小宝石"（little gem）'''<ref name="moschovakis2010" />；Kiselyov 则以"'''函数式珍珠'''（A Functional Pearl）"为题向函数式编程社区重新发掘了它<ref name="kiselyov" />。

证明：设 e 是函数 <math>\psi(S(y,y), x)</math> 的编号，取 <math>f = S(e, e)</math> 即可。

这个"小宝石"随即在论文 §3 被用于证明该文的主要结果：'''存在一个"通用"序数记号系统 <math>S_1</math>'''——任何其他合法记号系统能命名的序数，<math>S_1</math> 都能命名，且翻译过程本身是可计算的<ref name="kleene1938" />。这是"沿着序数逐层向上做递归定义"（后来称为'''有效超限递归'''，effective transfinite recursion）这一方法的首次应用。Kleene 由此构造出著名的'''记号系统 O（Kleene's O）'''，并证明存在最小的一个"不可命名"的序数——'''Church–Kleene 序数 <math>\omega_1^CK</math>'''，即[[序数|可数序数]]中第一个无法被任何机械记号系统触及的序数<ref name="kleene1938" /><ref name="rogers1967" />。

 

这个"小宝石"随即在论文<ref name="kleene1938" />的 §3 被用于证明该文的主要结果：'''存在一个"通用"[[序数记号系统]] <math>S_1</math>'''——任何其他合法记号系统能命名的序数，<math>S_1</math> 都能命名，且翻译过程本身是可计算的<ref name="kleene1938" />。这是"沿着序数逐层向上做递归定义"（后来称为'''[[有效超限递归]]'''，effective transfinite recursion）这一方法的首次应用。Kleene 由此构造出著名的'''[[记号系统 O]]（[[Kleene's O]]）'''，并证明存在最小的一个"不可命名"的序数——'''[[Church–Kleene 序数]] <math>\omega_1^{CK}</math>'''，即[[序数|可数序数]]中第一个无法被任何机械记号系统触及的序数<ref name="kleene1938" /><ref name="rogers1967" />。

=== 命名史 ===

=== 命名史 ===