关于证明INF ≡ₘ TOT的技术问询

算力阿峰

2026-4-20

关于证明 $\text{INF} \equiv_m \text{TOT}$ 的技术问询

首先明确我们要处理的两个核心集合定义：

$\text{INF} = {x \in \mathbb{N}:\operatorname{Dom}\phi_x\text{ is infinite}}$：所有定义域为无限集的部分可计算函数对应的编码集合
$\text{TOT} = {x \in \mathbb{N} : \operatorname{Dom}\phi_x = \mathbb{N}}$：所有全可计算函数对应的编码集合

我们的目标是证明这两个集合m-等价（记作$\text{INF} \equiv_m \text{TOT}$），也就是需要构造两个部分可计算函数$f, g$，满足：

你提到构造程序时的主要卡点是：没法直接在程序里判定$\operatorname{Dom}(\phi_x)$是否无限——这确实是关键，因为无限性本身是不可判定的。我们不能直接“检查”无限性，得用可计算枚举的延迟技巧或者函数编码的构造性转化来绕开这个问题。

我们需要定义一个部分可计算函数$f$，让它把全函数编码映射到无限定义域函数编码，把非全函数编码映射到有限定义域函数编码。

具体构造$f(x)$对应的函数$\phi_{f(x)}$：

对任意输入$n$，$\phi_{f(x)}(n)$的计算逻辑是：先依次模拟$\phi_x(0), \phi_x(1), ..., \phi_x(n)$的运行。如果所有这些模拟都能停机（也就是$x$对应的函数是全函数），那么$\phi_{f(x)}(n)$就停机（比如返回0）；如果其中有某个$\phi_x(k)$（$k \leq n$）永远不停机，那么$\phi_{f(x)}(n)$也跟着不停机。

这样一来：

若$x \in \text{TOT}$：$\phi_x$对所有输入都停机，所以$\phi_{f(x)}$的定义域是整个自然数集$\mathbb{N}$（无限），即$f(x) \in \text{INF}$
若$x \notin \text{TOT}$：存在某个最小的$k$使得$\phi_x(k)$不停机，那么当$n \geq k$时，$\phi_{f(x)}(n)$都无法停机，定义域就变成了${0,1,...,k-1}$（有限），即$f(x) \notin \text{INF}$

这个$f$是部分可计算的，因为我们可以用通用图灵机来模拟$\phi_x$的计算过程，完全符合可计算函数的编码规则。

这一步需要把无限定义域函数编码映射到全函数编码，把有限定义域函数编码映射到非全函数编码，思路是利用枚举延迟输出：

具体构造$g(x)$对应的函数$\phi_{g(x)}$：

对任意输入$n$，$\phi_{g(x)}(n)$的计算逻辑是：开始枚举$\phi_x$的定义域元素（也就是所有让$\phi_x(k)$停机的$k$），按从小到大的顺序记为$k_0, k_1, k_2, ...$。当我们枚举到第$n+1$个这样的$k$时，$\phi_{g(x)}(n)$就停机（比如返回0）；如果永远枚举不到第$n+1$个元素（也就是$\phi_x$的定义域有限），那么$\phi_{g(x)}(n)$就一直不停机。

这样一来：

若$x \in \text{INF}$：$\phi_x$的定义域是无限的，所以对任意$n$，我们总能枚举到第$n+1$个元素，$\phi_{g(x)}(n)$对所有$n$都停机，即$g(x) \in \text{TOT}$
若$x \notin \text{INF}$：$\phi_x$的定义域是有限的（比如只有$m$个元素），那么当$n \geq m$时，$\phi_{g(x)}(n)$永远无法停机，$\phi_{g(x)}$不是全函数，即$g(x) \notin \text{TOT}$

这个$g$也是部分可计算的，因为枚举$\phi_x$的定义域是可计算枚举过程，用通用机就能实现。

通过上面的构造，我们得到了满足要求的$f$和$g$：

因此$\text{INF} \equiv_m \text{TOT}$得证。

备注：内容来源于stack exchange，提问作者Sai Nallani