创造集

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

“Creative”是 Post 的技术术语，不评价集合或程序是否新颖。其力量来自枚举与补集对角化的配合：c.e. 性让其他搜索过程能够被编译进 $C$ 的成员问题；补集 productive 性保证编译在正、负两面都不能被一个简单清单击穿。

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

标准例子是对角停机集

$K$ c.e.；productive 性公理库生产集Productive set · Productive function · 产出集能从任意被承诺落在其中的 c.e. 子集索引，有效产出一个尚未被该子集枚举到的自身元素的集合。的对角计算证明 $\bar{K}$ productive，productive function 可取 $p(e)=e$，故 $K$ creative。这不是只引用“停机问题很难”：必须同时验证 $K$ 的可枚举性和补集的统一漏项性质。

下面给出 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. 集都可能缺少这种统一性；simple 集公理库递归论中的 Simple 集Simple set · Simple c.e. set · Post simple set自身 c.e.、补集却无限且不含任何无限 c.e. 子集的集合。只保证补集没有无限 c.e. 子集，并不自动 many-one 完备。两者的对比在于 complement 的 immune 性与 productive 性，而不是“较简单/较有创造力”的自然语言评价。Creative 也不能定义成“补集非 c.e.”，因为所有不可判定 c.e. 集都有这一点。最后，$C$ 与 $\bar{C}$ 的角色不可交换：productive 集从不 c.e.，所以 $\bar{C}$ 不可能是另一个 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 取决于表达能力、编号与一致性条件；“任何不完备理论都 creative”是错误的逆推。