递归论中的 Simple 集

Simple 集一边允许算法不断枚举自己的元素，另一边又把剩余空间切得足够零散，使任何无限有效枚举都无法永远躲在补集里。构造者不必知道 $W_e$ 是否真的无限；只需等待它露出一个足够大的元素，然后把该元素吸收到 $S$，便永久破坏“$W_e$ 是补集的无限子集”这一可能性。

难点是同时保留无限补集。若见到每个枚举元素就全部放进 $S$，当然能击中所有 $W_e$，却可能得到 $S=\mathbb{N}$；若为保留空间而完全不行动，又无法满足要求。大小 restraint 把二者平衡：低编号要求只获准拿走一个远处元素，因而任何有限初段附近都有可计数的剩余。

Simple 性只组织 c.e. 子集，不直接控制 Turing degree。Post 最初希望这种“补集无有效无限片段”的稀薄性会迫使 $S$ 不完全，但 simple 只立即给出非可计算；能否计算 $0^{\prime }$ 是另一组全局 oracle 要求。

固定可接受编号公理库程序编号与可接受编号Program indexing · Acceptable numbering · Gödel numbering对部分可计算函数进行有效枚举，并要求编号支持通用解释与有效参数编译。给出的统一枚举 $(W_e)$。从 $S_0=\varnothing$ 开始。阶段 $s$ 搜索最小的尚未满足 $e\le s$，使有限近似 $W_{e,s}$ 含某个 $x>2e$；若找到，就选其中一个 $x$ 放入 $S_{s+1}$，并把 $P_e$ 标记完成，否则保持不变。令 $S=\bigcup _s{S}_s$。

阶段规则是有效的，故 $S$ c.e.。若 $W_e$ 无限，它最终出现大于 $2e$ 的元素；只有有限多个更小要求可能先行动，故 $P_e$ 终会满足。对任意 $n$，落在 $[0,2n]$ 的已枚举元素只能来自 $e<n$，而每个这样的要求至多选一个，所以该区间至少留下 $n+1$ 个数不在 $S$；补集无限。若补集含无限 c.e. 集 $W_e$，$P_e$ 又强迫它和 $S$ 相交，矛盾。因此这确实是一个 simple 集。

边界必须逐项保留。一个 finite c.e. 集的补集虽无限，却含大量无限可计算子集，所以不 simple；一个 immune 集自身不能是无限 c.e.，也不是 simple 的另一种写法；一个 coinfinite 非计算 c.e. 集若漏掉某个无限可计算集合，同样不 simple。

Simple 也不等于 Turing 不完备。存在 low simple 集，其 degree 严格低于 $0^{\prime }$；另一方面，加强为 effectively simple 会导出 Turing 完备性。由此可见，同一补集交叉性质可与不同 jump 行为共存，不能把 Post 问题的历史动机写成定义结论。

Simple 集是优先法的原型。每个 $P_e$ 只需一次行动，要求之间几乎不伤害；加入 low、incomplete 或其他 degree 条件后，元素的枚举可能破坏先前依赖有限 oracle use 的计算，才出现 restraint、injury 与优先次序。基础构造因而提供了读懂复杂有限伤害论证的最小模型。

它还说明“c.e. 非计算”可以由补集的组合结构保证，而无需直接归约停机问题。证明不可计算只用一行反证：若 $S$ 可计算，$\bar{S}$ 是无限 c.e. 子集。与creative 集公理库创造集Creative set · Creative c.e. set · Post creative set自身 c.e. 且补集 productive 的集合，等价刻画 c.e. 集中的 many-one 完全集。的 many-one 完全性相比，simple 性刻画的是补集避开有效无限子集的失败，两种性质回答不同问题；它们的对比不把 immune 与 productive 误当逻辑互补。

在可计算结构或形式理论中，类似要求可用于构造一个有效生成对象，同时让其余部分没有无限有效子对象。迁移时仍须重建“每个要求只取有限资源”和“全局保留无限空间”两项不变量；只把术语 simple 借来描述稀疏外观，不会自动得到递归论结论。