CKO

CKO（Church-Kleene Ordinal），是可数递归序数的上确界。

定义

Church-Kleene 序数，记作 ${\omega }_1^{\mathrm{C}\mathrm{K}}$，是可计算序数（computable ordinals）的上确界。具体来说，它是在可计算良序（computable well-orderings）的序型（order types）集合中的最小不可数上界。

形式化定义

设 $\mathrm{O}$ 是所有可计算良序的序型构成的集合。即，若 $\prec$ 是一个可计算关系（存在一个图灵机可以判定对于任意的 $x,y$，是否有 $x\prec y$），且 $(A,\prec )$ 是一个良序集（well-ordered set），其中 $A\subseteq \mathrm{N}$，则该良序的序型 $\mathrm{otype}(A,\prec )\in \mathrm{O}$。那么，

${\omega }_1^{\mathrm{C}\mathrm{K}}=\sup \{\mathrm{otype}(A,\prec ):(A,\prec )\text{ 是可计算良序}\}$

性质

不可递归枚举性：不存在一个图灵机可以枚举出所有小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的可计算序数。换句话说，集合 $\{\alpha <{\omega }_1^{\mathrm{C}\mathrm{K}}:\alpha \text{ 是可计算序数}\}$ 不是递归可枚举的。这是因为如果存在这样的图灵机，我们可以利用它构造出一个更大的可计算序数，从而与 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是可计算序数的上确界这一性质矛盾。

不可超递归性：${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 本身不是可计算序数。因为如果 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是可计算的，那么我们可以构造出一个可计算良序，其序型大于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​（通过在已有的可计算良序基础上进行适当的扩展），这与 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的定义矛盾。

在可计算分析中，${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是超穷归纳原理（transfinite induction）在可计算结构上能够有效应用的最大序数。对于任何小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的序数 $\alpha$，我们可以在可计算的意义下对序型为 $\alpha$ 的良序进行归纳。但对于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$ 本身，不存在这样的可计算归纳过程。

${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 与算术层次（arithmetic hierarchy）有着密切的联系。可计算序数可以看作是在算术可定义性框架内能够构造和研究的序数。${\omega }_1^{\mathrm{C}\mathrm{K}}$的存在表明，在算术可定义性的范围内，序数的研究有一个自然的界限。具体来说，${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 是 ${\mathrm{\Delta }}_1^1$​ 完备的，这意味着它是所有 ${\mathrm{\Delta }}_1^1$​ 集合中序型最大的元素（在序数的序关系下），并且任何 ${\mathrm{\Delta }}_1^1$​ 集合的序型都小于 ${\omega }_1^{\mathrm{C}\mathrm{K}}$​。

可计算函数

存在某种算法（如图灵机、λ演算、递归函数等）能在有限步骤内计算出结果的函数。所有可计算函数的集合构成“可计算域”。

Church-Kleene 序数是递归序数的“顶”，但本身不属于递归序数：

• 递归序数是“可构造”的：通过递归函数能定义其良序关系，因此它们与可计算性直接相关（可被算法部分描述）。
• ${\omega }_1^{\mathrm{C}\mathrm{K}}$ 是递归序数的最小上界，但它本身不可计算：无法用递归函数完全定义其良序。

不可计算函数

不存在任何算法能在有限步骤内计算其结果的函数。典型例子是停机问题判定函数（无法通过算法判断任意程序是否会停止）。

递归函数

递归函数是计算理论中一类通过规则构造的函数，分为两类：

• 原始递归函数：由初始函数（零函数、后继函数、投影函数）通过“组合”和“原始递归”运算构造的函数。所有原始递归函数都是可计算的，但覆盖范围有限（如阿克曼函数虽可计算，却非原始递归）。
• 一般递归函数：在原始递归函数基础上引入“最小数算子（μ算子）”，允许通过“搜索最小自然数满足条件”的方式定义函数。一般递归函数与图灵可计算函数等价，即所有一般递归函数都是可计算的，且所有可计算函数都可表示为一般递归函数。因此，可计算函数等价于一般递归函数（在算法等价性下）。

历史背景

Church-Kleene 序数得名于数学家 Alonzo Church 和 Stephen Cole Kleene。他们在 20 世纪 30 年代和 40 年代对递归函数理论和可计算性进行了深入研究，提出了许多重要的概念和结果，其中包括可计算序数和 Kleene 的 O 记号系统。${\omega }_1^{\mathrm{C}\mathrm{K}}$​ 的概念为递归理论和可计算分析提供了一个重要的界限和基准，使得研究人员能够更清晰地划分可计算和不可计算的对象在序数结构中的位置。