关于递归可枚举集与丢番图集的一些记录

作者: LostAbaddon | 来源:发表于2020-01-11 01:19 被阅读0次

因为网友十酒三的文章，突然对丢番图集产生了兴趣。

加上之前看《永恒的图灵》时也看到过相关的讨论，所以这里就记录一些关于丢番图集与递归可枚举集的想法。

关于图灵机

要理解递归可枚举集，先要理解图灵机。

图灵机的定义，大家可以去查维基百科。

就个人而言，我比较喜欢这样的定义，虽然并不是必须的：

有限非空离散集 $B$ 被称为底空间；
有限非空离散集 $S$ 被称为状态空间；
图灵空间 g 是 $G = B \times S$ 的元素，每个点都有一个位置对应 $B$ 中元素与一个状态为 $S$ 中元素；
图灵点 x 是 $S$ 的一个元素，其取值被称为内禀状态；
偏函数被称为转移规则，它的功能是：
- 先将图灵点当前所处位置的状态转变为新状态
- 再将图灵点的位置转变为新位置
- 最后将图灵点的内禀状态转变为新状态
- 如果 $P(b,s,x)$ 无定义，则计算停止并拒绝
- $B$ 中存在一个特殊的位置 $e$ ，如果 $P$ 产生该位置，则计算停止并接受
$T = \left< G, x, P \right>$ 被称为一台图灵机

很显然， $B$ 的作用就是 description，而 $\{g,x\}$ 的作用就是 configuration。前者描述了“纸带”，后者描述了当前图灵机的状态。

因此，图灵机的运作过程，可以认为是将一个图灵点放在一个初始状态的图灵空间的给定初始位置、并让它再转移规则的作用下“自由运动”所产生的“世界线”，且最后有三种可能：

世界线在某处造成转移规则无定义，此时称初始状态为“被拒绝的”；
世界线最终终止于特殊位置 $e$ ，此时称初始状态为“被接受的”；
世界线永远不达到特殊位置 $e$ ，此时称初始状态为“永不停止的”。

当然，这么个说法其实没多大意义，只不过看起来比较“绚”而已。

如果图灵机最终被接受（当然也就停机了），那么此时它的图灵空间 $g$ 被称为是“输出结果”，相应的，一开始的图灵空间 $g_0$ 被称为“输入参数”。

因此，我们如果只看重一头一尾两个状态的画，那图灵机就是这样的： $g = T(g_0)$ ，也即，它是将输入参数映射到输出结果的偏函数，这是一句废话。

我们如果将图灵空间中的状态限定为有限非空符号集 $\Sigma$ 的幂集 $\Gamma = \Sigma^*$ ，那图灵机显然可以看作是能将有限个 $\Gamma$ 映射到另一组有限个 $\Gamma$ 的偏函数，即：

$T(I \in \Gamma^n) \in \Gamma^m;\ \ \ \ \mathrm{if}\ I \in \Omega_T$

这里 $\Omega_T \subset \Gamma^*$ ，是所有图灵机 $T$ 可接受的输入状态的集合。而如果一个输入状态不在 $\Omega_T$ ，那图灵机可能拒绝并停机，也可能永不停机。

这里，图灵机 $T$ 的可接受输入状态集 $\Omega_T$ 被称为是一个“遍历可枚举集”。

同样的，如果一个集合 $A \in \Gamma^*$ 被称为是“遍历可枚举的”，那就表示存在一个图灵机 $T$ ，使得 $A$ 恰好就是 $T$ 的所有可接受输入状态构成的集合。

停机不可判定问题告诉我们：我们永远不可能找到一个通用图灵机 $P$ ，使得它能告诉我们任意一个图灵机 $T$ 在给定输入状态下是否可以停机。

这也就是说，我们不可能找到一个通用图灵机 $P$ ，使得它能判断任意输入状态是不是某个图灵机 $T$ 的可接受输入状态。

从而，这就等于是说，不存在一个通用图灵机能帮助我们来判断一个集合是否是遍历可枚举的。

另一方面，让我们来看一下丢番图集。

所有形如 $\sum_{i=1}^n a_i x_i^{b_i} = c$ 的方程被称为“丢番图方程”，如果其中系数 $a_i$ 、 $b_i$ 和 $c$ 都是整数的话。比如说，我们最常见的一元二次方程 $y - x^2 = 0$ 就是一个丢番图方程；费马方程 $x^n + y^n - z^n = 0$ 也是一个丢番图方程，且我们知道当 $n > 2$ 时该方程没有整数解。

丢番图方程 $F$ 的整数根的存在性是一个非常有趣且艰深的问题，比如费马方程在 $n>2$ 时就没有整数根。

因此，是否存在一个算法，能自动判断任意输入的丢番图方程是否有整数解，就是一个很有趣的问题，如果存在的话，那包括费马大定理在内的很多问题就很容易解了。

现在，我们将一个丢番图方程 $\sum_{i=1}^n a_i x_i^{b_i} = c$ 中所有的系数提取出来： $\{ a_1...a_n; b_1...b_n; c \}$ ，总共有 $2 n + 1$ 个参数。

接下来，我们将这 $2 n + 1$ 个参数中的一部分固定（也可以都不固定），另一部分为可变参数（只能取整数），一组这样的可变参数就被称为一个“参数组”。所有能让该丢番图方程有整数解的参数组构成的集合，就被称为该丢番图方程的“丢番图集合”。

也就是说，丢番图集中的任意一个元素，都能确保对应的丢番图方程（包含那些被固定下来的整数参数）必然有整数解，反之则该丢番图方程没有整数解。

这里，丢番图集中的元素只是原来丢番图方程所有参数中的一部分，所以我们既可以说丢番图集对应了一个丢番图方程及其部分确定的参数，这么一个确定的二元体，也可以说丢番图集合对应了一个丢番图方程，丢番图集中的每个元素都存在一组整数来补充那些“固定”的参数，让这个丢番图方程有整数解。

如果丢番图集和遍历可枚举集是一一对应的，那由于遍历可枚举集是不可判定的，所以也就是说至少存在一个丢番图集是无法通过图灵机来判定的，这就等于说，至少有一个丢番图方程（所有参数都固定），它是否有整数解是无法用图灵机来判定的。

这等于就是说：希尔伯特的第十个问题的答案是否定的。

为了证明（及证伪）希尔伯特的第十个问题，人们努力了很久。戴维斯、普特南及美国首位入选国家科学院的女数学家茱莉娅·罗宾逊一起努力了很久，最后证明到这样的程度：

所有丢番图集必然是遍历可枚举的；
所有遍历可枚举集都是指数丢番图集；
猜测所有指数丢番图集都是丢番图集（即存在“金发姑娘方程JR”，该猜想被称为罗宾逊猜想）。

完成最后这个猜想的证明、也即证明存在JR的，是俄罗斯数学家尤里·马基雅谢维奇。

于是，四个人联合起来就证明了：丢番图集金额遍历可枚举集是等价的。

这被称为MRDP定理，也叫马基雅谢维奇定理。

历史介绍完了，下面说一下个人的想法。

这个定理很有趣，它告诉我们这么两件事：

任何能让一台图灵机接受并停机的输入参数，都能让至少一个丢番图方程有整数解；
任何能让一个丢番图方程有整数解的参数组，都能让至少一台图灵机接受并停机。

发现没有？

这里有趣的地方在于：丢番图方程显然是连续可微的（虽然丢番图集与方程对应函数的自变量无关），而图灵机则是非常显然的离散客体，这两个乍看起来全然不同的东西，居然有如此奇妙的内在联系。

而且，更关键的是，我们印象里，方程与函数能做的事，图灵机都能做；但图灵机能做的事，方程与函数似乎未必都能做到。这样的两个“功能不对等”的东西，对于输入参数居然有相同的要求，似乎很让人惊讶。

但，转念想想又感觉似乎有一种必然，毕竟丢番图方程的数量和图灵机的数量，是一样多的，都是阿列夫0，因此存在这样的映射关系似乎很正常。

事实上，之所以用丢番图函数的参数而非输入变量来和图灵机的输入状态做对应，就是因为对于丢番图函数这类多项式函数而言，只要输入的变量不是无穷，那总是可以给出整数输出的；但系数如果不恰当的话，那方程就很可能找不到整数解。所以用参数而非变量来做对应，就看起来很合理了——我们甚至可以“猜想”那些整数解可能在某种程度上对用了相应类型图灵机的内部状态，甚至是输出，谁知道呢。

我之前甚至猜想，对于任意一个将 A 个输入数据映射到 B 个输出数据的图灵机，在任意编码规则（将数据映射到自然数）下，都可以找到至少一组丢番图函数（整系数多项式）与之一一对应，这组丢番图函数有 B 个，每个都要有 A 个独立输入变量。

但随后想想这样的同构映射应该是不存在的，因为首先任意这样的丢番图函数组必然都可以映射到一类图灵机，而这类丢番图函数的特点是对于任意输入的整数，都可以唯一确定地输出一个整数，那就是说每一这样的丢番图函数组对应的图灵机对于任意输入都必然能停机于接受状态——但这显然不是任意图灵机都能满足的情况，所以必然存在图灵机无法被这样的丢番图函数组描述。

所以这里就再次体现出了用丢番图函数的参数来对应图灵机输入的好处了。

好了，不执着于这种内在联系带来的诧异感，让我们来考虑这么一个问题：

这两个集合，还能不能拓展？

尤其，在丢番图逼近中，我们已经不要求一个丢番图方程的参数必须是整数了，而可以是任意实数。这样，所有能让一个丢番图方程有整数解的实系数的子集构成的集，就是该丢番图方程的“拓展丢番图集”。

比如说， $a x^b = 1$ 这个丢番图方程的丢番图集为：

$\{(1, z) | z \in Z\} \cup \{ (n^z, -z) | z \in N, n \in N \}$

而它的拓展丢番图集则可以是：

$\{ (n^x, -x) | x \in R, n \in N \}$

明显大了很多，前者只是后者的一个子集。

但，这样的拓展似乎还不够“狂野”，让我们来看下面这个：

$P(f;A,B) = \int_\Omega A(z) f(z)^{B(z)} dz$

它是一个泛函，称为“丢番图泛函”，其中函数 $A$ 和 $B$ 被称为“参数函数”，函数 $f$ 则是测试函数且要求 $f(z) \in \Sigma$ ， $\Sigma$ 是实数的任意子集，被称为“限制域”，而 $\Omega$ 为实数的另一个任意子集，被称为“活动域”。假定，存在 $f(z)$ 及 $C \in \Sigma$ 使方程 $P(f;A,B) = C$ 成立，那么二元组 $\{A, B\}$ 被称为是“丢番图问题组” $\{P,\Omega,\Sigma\}$ 的一个“泛参数组”。 $P$ 的所有泛参数组构成的集合，就是这个丢番图泛函的“泛丢番图集”。

注意，这里函数 $A$ 、 $B$ 、 $f$ 都不要求光滑，甚至都不要求连续，所以完全可以是分段函数。而活动域 $\Omega$ 与限制域 $\Sigma$ 也没有任何要求，可以是可数集，也可以是离散集（这两种情况下，积分就变成了求和），同样也可以是豪斯道夫集。我们一般可以固定活动域与限制域来讨论泛丢番图集。

显然，当取 $\Omega = R$ 、 $\Sigma = Z$ 时，泛丢番图集是上述拓展丢番图集与丢番图集的超集。

或者，更形式化的写法是：

$\{ (A, B) | \exists C \in \Sigma \cup \exists f : \Omega \rightarrow \Sigma, P(f; A, B) = C \}\\ P(f;A,B) = \int_\Omega A(z) f(z)^{B(z)} dz$

现在对丢番图集的拓展算是很奔放地完成了，那么对遍历可枚举集的拓展呢？

或者，这里可以更准确地问，是对图灵机的拓展可以怎么玩。

在前面关于图灵机的定义中，有几个离散集：

有限非空离散集 $B$ 被称为底空间
有限非空离散集 $S$ 被称为状态空间

如果将这两个集合推广呢？

比如这样：

取任意空间 $B$ 为底空间，底空间上任意元素上都直积一个内禀空间（不要求离散与有限），称为“外状态空间”。而后， $B$ 上有一个“粒子” $p$ ，它对应到 $B$ 中的一个元素，称为“位置”。 $p$ 还有一个“内禀状态”，取值在“内状态空间”中。

现在，底空间、外状态空间与内状态空间都不要求离散或有限，可以是任意集合。

事实上，这样就有点纤维丛的意思了，但并不一样。

转移规则依然和前面所说的一样，先改变粒子所处位置的外状态，然后改变粒子的内状态，接着移动粒子到新的位置。它的作用有点像微分几何中的联络——但我们并不要求这种移动只能在邻近位置上移动，所以这可以说是添加了“虫洞”结构的纤维丛上的运动学问题了。当然，我们也可以和标准图灵机中读写头只能局限在左右移动一格一样，将这里对位置的改动限定在只能在当前点的邻域内移动，那这样看起来就更像是运动学问题了，于此同时对内状态和外状态的改变看起来也更像是主从联络与底流形联络所干的事了。

一旦粒子的世界线进入“无定义”的区域，就被拒绝并停止——可以类比掉入黑洞的奇点。

也可能粒子运动到了底流形上的特定区域，从而被接受并停止——可以类比闭合宇宙到达命运终结。

还有可能，粒子的世界线永远不会停止，一直在某个区域里打转——可以类比开放宇宙永不终结。

而这种超图灵机的初始状态，也就是底流形的初始状态，可以类比为宇宙在大爆炸时的状态。

好了，类比归类比，时空当然不是这种定义下的超图灵机了——大概不是吧。

现在，这种超图灵机的输入状态（以及输出状态）都不是离散集了。

如果 $B$ 是连续空间，比如一个微分流形，那么输入状态就可以是 $B$ 上的一条曲线，或者曲面。在这条曲线或曲面之外的点上的外状态都为 0，而在这条曲线或曲面上的点的外状态就构成了输入状态。

因此，很显然理论上泛丢番图集与这里的可接受输入状态之间，是可以做对应的。

于是，问题来了：

是否，任意上述拓展的超图灵机的可接受初始状态，与某个泛丢番图集，总能一一对应？

开个脑洞的话，就是这样的：

是否，任意物理规则下的闭合宇宙初始状态，与泛丢番图集，总能一一对应？

这个脑洞就比较奔放了——虽然更多只是好看，并无实际意义。

玩笑归玩笑，问题还是在的。

我们对丢番图集和图灵机分别做了拓展，尽可能地将它们“连续化”，然后提出了相应的泛丢番图集与超图灵可识别集之间，是否也存在如丢番图集与图灵可识别集之间那样的一一对应关系，这么一个问题。

当然，这个问题本身我当然现在是回答不了的。

我们来看下别的东西。

比如，可压缩性。

在图灵机领域，可压缩性与算法复杂度相关，具体来说是这样的：

$K(s \in \Gamma) = \inf \left( \left\{ \mathrm{len} (r) + \mathrm{len} (T) | r \in \Gamma \cup T \in \mathrm{TM}, T(r) = s \right\} \right)$

这里我们故意将图灵机 $T$ 与它的输入参数 $r$ 分开。任意字符串 s 的 K 氏复杂度的定义由上面给出，它如果小于 $\mathrm{len}(s)$ ，那么就说 s 是可压缩的。

现在，我们试着将问题移植到超图灵机（记为 HTM）上。

我们将函数 $f: B \rightarrow S$ 称为超图灵机的一个状态函数。在开始运作之前的状态函数 $I$ 被称初态，它是超图灵机接受的输入状态，而 $B$ 上的一个元素被称为“初始位置”，代表读写头的“粒子”将从初始位置开始运动。如果粒子最终运动到指定的“终点位置”，则表示这台超图灵机停机于接受状态，此时的状态函数 $O$ 被称为末态。

因此，停机于接受的超图灵机就是映射： $Q(I) = O$ 。

下面，我们可以定义一个能量函数 $H: S \rightarrow R^+ \cup \{0\}$ ，从而可以定义一个状态的能量：

$E(f) = \int_B H(f(\epsilon)) d\epsilon$

另一方面，转移函数 $P$ 本身也可以被编码，虽然我们目前不清楚到底应该如何编码，但可以形式化地记为 $\mathrm{Code}(P) \subset S^*$ ，从而一样可以计算它的能量：

$E(P) = \sum_i H(\mathrm{Code}(P)(i))$

我们可以将一台超图灵机的转移规则的能量作为这台超图灵机的能量，从而就可以形式化地定义“算法复杂度”了：

$K(f) = \inf \left( \left\{ H(I) + H(Q) | Q(I) = f \right\} \right)$

如果 $K(f) < H(f)$ ，那我们就说状态函数 $f$ 是可压缩的。

从类比的角度来看，可压缩状态意味着能量可以进一步降低的状态，事实上也就对应了熵可以进一步增高的状态，所以在这个系统中，“热力学熵”和超图灵机的信息熵应该是等价的，不可压缩状态也就意味着“黑体辐射”。

当然，还是那句话，这种类比只适合开脑洞，没多大实际意义。

或者，我们也可以和十酒三的思路一样，从代数的角度来看不可压缩性：

给定函数集 $F$ ，若对于集合 $X$ 有如下关系成立，则称 $X$ 在 $F$ 上是可压缩的：

$\exists f \in F, ( \forall x \in X, F(X/x) = x )$

也即，存在至少一个函数，能让任意一项数据可以通过给定集合中的别的数据导出。我们将这个关系记为 $A \vdash F$ 。

这种形式的数据其实很常见，比如让我们选择一个 D 维矢量空间，函数集里只有一个矢量加法，而数据集我们取这个 D 维矢量空间的 D 个基矢，由于它们显然彼此是线性无关的，所以这个数据集无法在矢量加法集上被压缩。

而可压缩集当然也很多，比如现在我们将上面这个粒子中的函数集替换为矢量加法与矢量外乘，那我们只需要两个基矢就足够了，第三个基矢可以通过这两个基矢的外乘来得到，从而可以被压缩掉。

当然，问题可以变得更加复杂——假定数据集 $A$ 在函数集 $F$ 上不可压缩，但如果加上数据集 $B$ 之后，集合 $A \cup B$ 就能在 $F$ 上压缩了，那这样的情况就很有趣了。

我们可以构造这样的函数：

$\mathrm{ext} (A) = \inf \left( \mathrm{len} (B) | A \cup B \vdash F \right)$

因此，如果 $A$ 在 $F$ 上可压缩，那 $\mathrm{ext} (A) = 0$ 。

同样的，我们也可以构造 $B = \mathrm{core}_f (A)$ 是 $A$ 的一个子集，可以通过 $B$ 与函数 $f$ 构造出 $A$ 中的所有的元素。我们记 $\mathrm{gen}_f (B)$ 为数据集 $B$ 通过函数 $f$ 生成的数据集，所以显然有 $A \subseteq \mathrm{gen}_f (B)$ 。这样我们就可以定义另一个函数：