关于递归可数集和丢番图集的一些记录
另外，之前看《永恒图灵》的时候看到过相关的讨论，这里就记录一些关于丢番图集和递归可数集的想法。
要理解递归可枚举集，首先要理解图灵机。
关于图灵机的定义，可以查维基百科。
我个人更喜欢这个定义，虽然这不是必须的:
显然，的作用是描述，的作用是配置。前者描述的是“纸带”，后者描述的是图灵机的现状。
因此，图灵机的运行过程可以认为是在一个初始状态下，将一个图灵点放在图灵空间的给定初始位置，并使其再次移动的作用下，“自由移动”产生的“世界线”，最终有三种可能:
当然，这种说法没有太大意义，但看起来很“华丽”。
如果图灵机最终被接受(当然它停止了)，那么它的图灵空间就叫做“输出结果”，相应的，初始的图灵空间就叫做“输入参数”。
所以，如果只关注一个头一个尾的画，图灵机是这样的:也就是把输入参数映射到输出结果的部分函数，这是扯淡。
如果我们把图灵空间中的状态限定为有限非空符号集的幂集，那么图灵机显然可以看作是一个能将有限映射到另一组有限的部分函数，即:
这里是图灵机所有可接受输入状态的集合。如果一个输入状态不存在，图灵机可能会拒绝并停止，或者永远不会停止。
在这里，图灵机的可接受输入状态集称为“遍历可枚举集”。
同样，如果一个集合被称为“遍历可枚举”，则意味着存在一个图灵机，使得它恰好是所有可接受输入状态的集合。
停机时间未定的问题告诉我们，我们永远找不到一个普适的图灵机，以至于它能告诉我们任何一个图灵机是否能停在给定的输入状态。
也就是说，我们不可能找到一个普适的图灵机，使得它能够判断任何输入状态是否是一个图灵机的可接受输入状态。
因此，这就相当于说，没有一个普适的图灵机可以帮助我们判断一个集合是否遍历和可枚举。
另一方面，我们来看看丢番图系列。
如果系数和都是整数，则所有形状方程称为“丢番图方程”。比如我们最常见的二次方程是丢番图方程；费马方程也是一个丢番图方程，我们知道这个方程没有整数解。
丢番图方程整数根的存在性是一个很有趣也很困难的问题，比如费马方程存在时没有整数根。
所以，是否有算法可以自动判断任意输入的丢番图方程是否有整数解，这是一个很有意思的问题。如果有，包括费马大定理在内的很多问题都很容易解决。
现在，我们从一个丢番图方程中提取所有的系数:总有一个参数。
接下来，我们将固定这些参数中的一部分(或者一个都不固定)，另一部分将是可变参数(仅限整数)。一组这样的可变参数被称为“参数组”。能使丢番图方程有整数解的所有参数组的集合称为丢番图方程的丢番图集。
也就是说，丢番图集合中的任何一个元素都能保证对应的丢番图方程(包括那些固定的整数参数)一定有整数解，否则丢番图方程没有整数解。
如果丢番图集和遍历可数集之间存在一一对应关系，就意味着至少有一个丢番图集不能被图灵机判定，因为遍历可数集是不可判定的，这就意味着至少有一个丢番图方程(所有参数都是固定的)不能被图灵机判定。
这就相当于说希尔伯特第十个问题的答案是否定的。
为了证明(并证伪)希尔伯特的第十个问题，人们努力了很久。戴维斯、普特南和美国第一位入选国家科学院的女数学家朱莉娅·罗宾逊(Julia Robinson)长期合作，最终证明了这一点:
证明最后一个猜想，即Jr的存在的是俄罗斯数学家尤里·马基雅弗利维奇。
于是，四个人联合起来证明丢番图集遍历可枚举集是等价的。
这被称为MRDP定理，也被称为马基雅维利定理。
历史介绍完了，再来说说我个人的想法。
这个定理很有趣。它告诉我们两件事:
你发现了吗？
这里有趣的是，丢番图方程明显是连续可微的(虽然丢番图集与方程对应函数的自变量无关)，图灵机是非常明显的离散对象。这两个乍一看完全不一样的东西，却有着如此奇妙的内在联系。
而且，更重要的是，在我们的印象中，方程和函数能做的事，图灵机都能做；但是图灵机能做的，方程和函数不一定都能做到。这两个“功能不对等”的东西对输入参数的要求是一样的，这似乎很奇怪。
但是，转念一想，似乎有必要。毕竟有多少图灵机就有多少丢番图方程，两者都是Alef 0，所以有这样的映射关系似乎很正常。
其实，之所以用丢番图函数的参数代替输入变量来对应图灵机的输入状态，是因为对于丢番图函数这样的多项式函数，只要输入变量不是无穷大，它总能给出整数输出；但是如果系数不合适，那么方程可能就找不到整数解了。所以用参数代替变量来对应似乎是合理的——我们甚至可以“猜测”那些整数解可能在某种程度上使用了相应类型图灵机的内部状态甚至输出，谁知道呢。
我甚至猜测，对于任何一台把A输入数据映射到B输出数据的图灵机，在任何编码规则下(把数据映射到自然数)，至少可以找到一组丢番图函数(整系数多项式)与之一一对应。有B组丢番图函数，每组都有一个独立的输入变量。
但随后又认为这样的同构映射应该是不存在的，因为首先任何这样的丢番图函数组都必须映射到一类图灵机，而这类丢番图函数的特点是对于任何输入都可以唯一输出一个整数，也就是说每个这样的丢番图函数组对应的图灵机对于任何输入都必须能够停在接受状态——但这显然不是任何图灵机都能满足的情况，所以一定有一个图灵机不能如此满足。
所以这里再次体现了用丢番图函数的参数对应图灵机输入的优势。
好了，与其纠结于这种内在联系带来的惊喜，不如考虑这样一个问题:
这两套可以扩充吗？
特别地，在丢番图逼近中，我们不再要求丢番图方程的参数必须是整数，而是可以是任意的实数。这样，所有能使一个丢番图方程有整数解的实系数子集都是丢番图方程的“扩展丢番图集”。
例如，这个丢番图方程的丢番图集是:
它的扩展丢番图集可以是:
显然大得多，前者只是后者的子集。
但是，这样的扩张似乎还不够“野”。让我们看看下面的内容:
它是一个叫做丢番图泛函的泛函，其中函数的和称为参数函数，而函数是一个检验函数，要求是实数的任意子集，称为“限制域”，另一个实数的任意子集称为“活动域”。假设方程存在并成立，那么二元组称为“丢番图问题组”的一个“普适参数组”。的所有泛参数组的集合就是这个丢番图泛函的“泛丢番图集”。
注意，这里的、和函数不要求光滑甚至连续，所以可以是分段函数。对活动域和限制域没有要求，可以是可数集，也可以是离散集(两种情况下积分都变成和)，也可以是Hausdorff集。我们一般可以通过固定活动域和限制域来讨论泛丢番图集。
显然，当，，泛丢番图集是上述扩展丢番图集和丢番图集的超集。
或者，更正式地说:
既然丢番图集的拓展很奔放，那么遍历可数集的拓展呢？
或者，这里可以更准确的问，就是图灵机的扩展怎么玩。
在前面的图灵机定义中，有几个离散集合:
如果这两套都一般化了呢？
像这样:
以任意空间为基空间，基空间上的任意元素都会直接产生一个本征空间(不需要离散性和有限性)，称为“外态空间”。然后，桌子上有一个“质点”，对应着表格中的一个元素，叫做“位置”。还有一种“内在状态”，其值在“内部状态空间”中。
现在，底部空间、外部状态空间和内部状态空间不要求是离散的或有限的，可以是任何集合。
其实这有点纤维束，但又不一样。
转移规则还是和上面说的一样，先改变粒子位置的外部状态，再改变粒子的内部状态，再把粒子移动到新的位置。它的作用有点像微分几何中的连接——但我们并不要求这种运动只能在相邻位置上运动，所以可以说是在添加了虫洞结构的纤维丛上的运动学问题。当然，我们也可以将这里的位置变化限制为只在当前点的邻域内移动，就像标准图灵机中的读写头只能从左向右移动一格，看起来更像是运动学问题，同时内部状态和外部状态的变化看起来更像是主从通信和底层流形通信的工作。
一旦粒子的世界线进入“未定义”区域，它就被拒绝并停止——这可以与落入黑洞的奇点相提并论。
也有可能粒子运动到底部流形上的特定区域，被接受并停止——可以比喻为关闭宇宙到达命运的尽头。
也有可能粒子的世界线永远不会停止，一直在某个区域旋转——可以和永远不会结束的开放宇宙相比。
这个超级图灵机的初始状态，也就是底流形的初始状态，可以比作宇宙大爆炸时的宇宙状态。
好吧，相比类比分类，时空当然不是这个定义下的超级图灵机——很可能不是。
现在，这个超级图灵机的输入状态(和输出状态)并不是一个离散集合。
如果是连续空间，比如微分流形，那么输入状态可以是图上的曲线或者曲面。这条曲线或曲面之外的点的外部状态都是0，这条曲线或曲面上的点的外部状态构成输入状态。
因此，很明显，在理论上，泛丢番图集和这里可接受的输入状态之间可以有对应关系。
那么，问题来了:
上述任一扩展超图灵机的可接受初态与一个泛丢番图集之间是否总是一一对应？
如果开个脑洞，是这样的:
任何物理规则下的封闭宇宙的初始状态与泛丢番图的集合之间是否总是一一对应？
这个脑洞更奔放——虽然更美好，没有实际意义。
玩笑归玩笑，但问题依然存在。
我们分别对丢番图集和图灵机进行扩展，使其尽可能“连续”，然后再问对应的泛丢番图集和超图灵可识别集之间是否存在一一对应，如同丢番图集和图灵可识别集之间一样。
当然，我现在肯定回答不了这个问题。
让我们看看别的。
例如可压缩性。
在图灵机领域，可压缩性与算法的复杂度有关，具体如下:
这里我们故意把图灵机和它的输入参数分开。上面给出了任何字符串S的K复杂度的定义。如果它小于，那么我们说S是可压缩的。
现在，让我们试着把问题移植到超级图灵机(HTM)上。
我们称该函数为超级图灵机的状态函数。开始运算前的状态函数称为初始状态，这是超级图灵机接受的输入状态，桌子上的一个元素称为“初始位置”，表示代表读写头的“粒子”将从初始位置开始移动。如果粒子最终移动到指定的“终点位置”，则意味着超级图灵机停止在接受状态，此时的状态函数称为最终状态。
所以，停在公认的超级图灵机就是映射:。
下面，我们可以定义一个能量函数，它可以定义一个状态的能量:
另一方面，传递函数本身也可以被编码。虽然目前还不知道具体怎么编码，但可以正式写成，这样它的能量可以计算如下:
我们可以把一个超级图灵机的转移规则的能量作为这个超级图灵机的能量，这样就可以正式定义“算法复杂度”:
如果是这样，那么我们说状态函数是可压缩的。
从类比的角度来看，可压缩状态意味着能量可以进一步减少的状态，实际上对应的是熵可以进一步增加的状态。所以在这个系统中，超图灵机的“热力学熵”和信息熵应该是等价的，不可压缩态就是“黑体辐射”。
当然，还是那句话，这个类比只适合开个脑洞，实际意义不大。
或者，我们也可以从代数的角度来看不可压缩性，就像十酒三分的思想一样:
如果下列关系对一组给定的函数成立，则称该组函数在世界上是可压缩的:
也就是说，至少有一个函数允许从给定集合中的其他数据导出任何数据项。我们将把这种关系记录为。
事实上，这种形式的数据非常普遍。比如我们选一个D维向量空间，函数集中只有一个向量加法，而数据集取这个D维向量空间的D个基向量。因为它们显然是彼此线性无关的，所以这个数据集不能在向量加法集上压缩。
当然，还有很多可压缩的集合。举个例子，现在我们用向量加法和向量乘法代替上面粒子中的函数集，只需要两个基向量，第三个基向量可以通过这两个基向量的外乘得到，所以可以压缩。
当然问题可以更复杂一些——假设数据集在函数集上是不可压缩的，但是如果加入数据集，集合在表上是可以压缩的，那么这种情况就很有意思了。
我们可以像这样构造一个函数:
因此，如果它在世界上是可压缩的，那么。
同样，我们也可以构造的子集，中的所有元素都可以用and函数构造。我们记得它是一个函数生成的数据集，所以显然是有的。所以我们可以定义另一个函数:
所以这个函数体现了数据集的不可压缩部分，如果。
这两个函数可以在一定程度上描述和的许多特征。
但是这个性质如何对应图灵机似乎有点混乱——如果我们把这里的函数集换成所有可能的图灵机，很明显我们可以压缩任何一个整数集到不留余数，所以在图灵机的情况下，我们会要求加上图灵机本身的“长度”。
但是在函数的问题上，函数的“长度”是我们不知道的。当然，我们可以像上一部分提到的那样对函数进行编码，然后用编码长度来表示函数的“长度”，但这样表示可压缩性会很不纯粹。
拉拉在看丢番图集和递归可数集的对应关系时写了很多想法，基本都是脑洞。
这一块感觉很有意思，可惜没来得及系统看。
本文遵守CC BY-NC-SA 4.0协议进行创作享受。