生产集 | Codeboy's Blog

形式陈述

固定所有c.e. 集的统一枚举 $(W_e)_{e\in\mathbb N}$ 。集合 $P\subseteq\mathbb N$ 称为 productive，若存在总可计算函数 $p$ ，对每个索引 $e$ 都有

W_e\subseteq P \quad\Longrightarrow\quad p(e)\in P\setminus W_e.

$p$ 称为 productive function。定义依赖可接受编号提供的统一程序索引，但 productive 性在合理编号间保持：有效翻译索引即可移植 $p$ 。蕴含式只在 $W_e\subseteq P$ 时提出保证；若枚举器已经输出 $P$ 外元素， $p(e)$ 可以是任意值。

有些教材先允许 $p$ 为部分可计算函数，只要求它在所有满足前件的索引上有定义；这一口径与上面的总函数口径等价，可用有效参数化与交错模拟把见证全函数化，进一步还能安排成单射。不能省掉的是索引到漏项的统一有效性。

任何 productive 集都不是 c.e.。若 $P=W_e$ ，定义会要求 $p(e)\in P\setminus P$ ，矛盾；因此它也必为无限。更强的 Myhill 刻画说，令对角集 $K=\{e:e\in W_e\}$ ，则

P\text{ productive} \iff \overline K\le_1P \iff \overline K\le_mP,

其中后两项分别是一一和many-one 归约。

总函数口径可直接核验。设 $\psi$ 是部分可计算的 productive function。由参数化定理取得总可计算 $h$ ：编号 $h(e)$ 的程序先等待 $\psi(e)$ 停机，再模拟编号 $e$ 的程序。因此若 $\psi(e)\downarrow$ ，则 $W_{h(e)}=W_e$ ；否则 $W_{h(e)}=\varnothing$ 。交错计算 $\psi(e)$ 与 $\psi(h(e))$ ，把先停机的一项作为 $q(e)$ 。若第一项永不停机，第二项对应空集而必停机，所以 $q$ 总可计算；若 $W_e\subseteq P$ ，两项中任何已定义值都属于 $P\setminus W_e$ ，故 $q$ 仍是 productive function。

直觉

给 productive function 的输入不是一个已经列完的集合，而是一段枚举程序的代码。只要这段程序声称自己永远留在 $P$ 内， $p$ 就能读其索引并构造一个同属 $P$ 、却一定没被它列出的新元素。任何单一有效清单因此都无法穷尽 $P$ ，而且漏项不是纯存在：从清单代码可以有效找到。

这是一种对角“扩表器”。普通非 c.e. 只说不存在完整枚举，可能没有统一方式指出某份候选清单漏在哪里；productive 性把失败做成总可计算函数。它也不要求 $p(e)$ 对不同 $e$ 互异，虽然可通过标准改造取得一一 productive function；核心是每份合法候选都被自己的索引击败。

Productive 与 immune 的量词不能互换。Immune 集禁止任何无限 c.e. 子集；productive 集只禁止某个 c.e. 子集覆盖自己，并为每份子集产出漏项。一个 productive 集完全可能含有无限可计算子集，所以二者既非同义，也非集合补关系。

例子与边界

对角集 $K=\{e:e\in W_e\}$ 的补集 $\overline K$ productive，而且 productive function 可以取最简单的 $p(e)=e$ 。假设 $W_e\subseteq\overline K$ 。若 $e\in W_e$ ，按 $K$ 的定义有 $e\in K$ ，却又因子集条件有 $e\in\overline K$ ，矛盾。因此 $e\notin W_e$ ；同一事实又按定义给 $e\notin K$ ，即

p(e)=e\in\overline K\setminus W_e.

这段两步对角核验同时证明“在 $P$ 内”和“在清单外”，不能只证明后者。

$\overline K$ 还展示 productive 不等于immune。由 padding 可总可计算地产生两两不同的索引 $d_0,d_1,\ldots$ ，每个索引都代表处处发散程序；于是 $d_n\notin W_{d_n}$ ，所以 $\{d_n:n\in\mathbb N\}$ 是 $\overline K$ 内的无限 c.e. 子集。若还要得到可判定的无限子集，可从这个无界序列有效选出严格递增子序列；判定时枚举到首个不小于待测数的项即可。Productive function 仍能对这份清单给出另一个漏项，并不要求清单有限。

边界还在蕴含前件。若 $W_e$ 只“目前看来”落在 $P$ ，却未来可能枚举出外部元素，定义不保证 $p(e)$ ；无法用有限阶段观察确认 $W_e\subseteq P$ 。另一方面，非 c.e. 集也未必 productive：不存在完整枚举不等于能从每份候选子集的索引统一抽取漏项。

推论与应用

集合 $C$ creative 当且仅当 $C$ c.e. 且 $\overline C$ productive。于是 productive function 把“不可能有效枚举完否定信息”转化为 creative 集的 many-one 完全性。 $K$ 是标准 creative 集， $\overline K$ 则是标准 productive 集；两个术语描述互补集合上的不同性质，productive 集本身不能归入 c.e.

在形式理论中，若真句编码集 $T$ productive，那么任何 c.e. 的正确理论 $W_e\subseteq T$ 都漏掉可由 $e$ 有效构造的真句 $p(e)$ 。这给不完备性一种“从公理化程序产生新真句”的形式，但应用必须证明真理集确实 productive，并区分语义真理与理论可证性；单靠理论不完备并不会自动提供 productive function。

Many-one 刻画还表明 productive 性带有统一的归约强度。若 $\overline K\le_mP$ ，任意声称枚举完 $P$ 的程序都会经归约诱导对角矛盾；反向则从 $p$ 与带参数的递归定理构造总可计算归约。后一方向真正使用了可接受编号和不动点机制，不能从“每份清单总有漏项”这一非一致陈述直接推出。

参考资料

Emil L. Post, “Recursively Enumerable Sets of Positive Integers and Their Decision Problems,” Bulletin of the American Mathematical Society 50(5), 1944, pp. 284–316，productive and creative sets。
John Myhill, “Creative Sets,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1(2), 1955, pp. 97–108，productive functions and reducibility characterizations。
Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，章节 “Creative and Productive Sets”。
Jean Gallier, Introduction to the Theory of Computation，creative/productive sets 与参数递归定理：总 productive witness 及归约刻画。

形式陈述 ​

反向链接

形式陈述