更改

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" />。

这个"小宝石"随即在论文<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" />。

这颗"小宝石"随即在论文<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" />。

=== 命名史 ===

=== 命名史 ===