更改

第二递归定理诞生于 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> 是任意可计算的部分函数，则存在一个数 <math>f</math>，使得 <math>\phi_f(x) = \psi(f, x)</math> 对所有 <math>x</math> 成立（等号含义：两边同时无定义，或同时有定义且相等）。'''

'''若 <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> 的编号，取 <math>f = S(e, e)</math> 即可。

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

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

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