更改

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

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

: 证明：设 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" />。

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