创造集

Creative 集的一边可以有效枚举，另一边却带着统一的对角反击：任何试图枚举补集一部分的程序，只要始终保持正确，productive function 就从其代码中制造一个漏掉的补集元素。这使 $C$ 不只是某个不可判定问题，而成为容纳所有 c.e. 正实例搜索的通用目标。

“Creative”是 Post 为这一结构引入的技术术语。$C$ 的 c.e. 性提供可枚举的正实例，补集的 productive 性则从任意正确的部分负实例清单中有效产生新负实例。下面的固定点构造把这两项性质组合成完备性证明。

Many-one 完备性尤其重要。归约对每个输入只产生一个目标数，并同时保持成员与非成员；所以 creative 集共享的不只是“可借助 oracle 解同样问题”，而是更刚性的实例级编码结构。正是这份结构后来允许 Myhill 定理把两个 creative 集之间的对应升级为整个自然数集上的可计算置换。

标准例子是对角停机集

$K$ c.e.；productive 性理路生产集Productive set · 产出集能从任意被承诺落在其中的 c.e. 子集索引，有效产出一个尚未被该子集枚举到的自身元素的集合。的对角计算证明 $\bar{K}$ productive，productive function 可取 $p(e)=e$，故 $K$ creative。

下面给出 creative 推出 many-one 完备的机制。设 $A=W_a$ 是任意 c.e. 集，$p$ 是 $\bar{C}$ 的 productive function。对每个输入 $x$，用带参数的Kleene 递归定理理路Kleene 递归定理Kleene recursion theorem每个总可计算的程序代码变换都存在一个与其变换结果计算同一偏函数的程序索引。一致地取得索引 $e_x$，其枚举器在 $x$ 尚未进入 $A$ 时保持空集；一旦观察到 $x\in A$，就枚举 $p(e_x)$。令 $f(x)=p(e_x)$。

若 $x\notin A$，$W_{e_x}=\varnothing \subseteq \bar{C}$，故 $f(x)\in \bar{C}$。若 $x\in A$ 而假设 $f(x)\in \bar{C}$，则 $W_{e_x}=\{f(x)\}\subseteq \bar{C}$，productive 性又要求 $f(x)=p(e_x)\notin W_{e_x}$，矛盾；所以 $f(x)\in C$。因此 $x\in A⟺f(x)\in C$，且 $f$ 总可计算。

不可判定的 c.e. 集未必 creative。Simple 集理路递归论中的 Simple 集Simple set · Simple c.e. set · Post simple set自身 c.e.、补集却无限且不含任何无限 c.e. 子集的集合。的补集是 immune 的，即没有无限 c.e. 子集；productive 集却包含这样的子集：从空清单开始，反复给有限清单的枚举程序应用 productive function，每次都会得到一个新的成员。因此 simple 集不可能 creative，也就不可能 many-one 完备。

仅要求补集非 c.e. 则只得到一般的不可判定 c.e. 集。Creative 还要求统一可计算的漏项生成机制；它的补集自身不是 c.e.，所以也不属于 creative 类。

Myhill 进一步证明所有 creative 集递归同构：若 $C,D$ creative，存在自然数上的可计算置换 $h$ 满足 $x\in C⟺h(x)\in D$。因此它们不仅处于同一 many-one degree，还能通过一一、满射且逆可计算的全局重命名彼此转换。结论依赖 creative 带来的一一完备性，不能推广到任意 Turing 完备 c.e. 集。

Creative 集为通用程序问题提供稳定规范形。许多“存在一段成功计算”的索引集一旦证明 c.e. 且 many-one hard，便可直接识别为 creative；Rice–Shapiro 型结果与可接受编号则帮助判断哪些语义索引集满足这一点。证明时仍需给出总可计算归约，不能仅说目标问题能模拟任意程序。

在不完备性语境中，creative 理论的定理集具有最强 c.e. 不可判定性，而其补集的 productive function 可从任何有效的否定清单中生成漏项。具体理论是否 creative 取决于表达能力、编号与一致性条件。