不可计算和不可数集的表示（2008）

偶尔我听到有人声称不可数和不可计算的集合不能在计算机上表示。更一般地说，关于计算机上数据的表示存在各种错误的观点，尤其是数学性质的无限数据。这是一个关于这个问题的快速教程，其主要观点是：在不考虑我们想要在集合上执行的操作的情况下讨论由数据类型表示的集合是没有意义的。除非你告诉我你想计算这个集合是什么，否则我可以用我想要的任何方式来表示它。你永远不会看我的表示，因为你永远不会对你的集合中的元素做任何事情。通过这种推理，您可以简单地通过具有单个元素 $()$ 的单元类型来表示任何集合 $X$。自然地，您会反对这毫无意义，因为 $X$ 的所有元素都具有相同的表示形式。但这意味着您确实关心 $X$ 的结构：您对 $X$ 上的不等式关系感兴趣。对于一个不太琐碎但仍然很愚蠢的例子，考虑所有图灵机的集合。著名的停机问题要求一种算法来决定，给定图灵机 $T$ 的描述，当我们在空磁带上运行它时 $T$ 是否停机。如果我们只关心停机问题，这样的算法很容易获得。简单地用一个比特表示每台图灵机 $T$，如果 $T$ 停止则为 $1$，否则为 $0$。这样就很容易决定 $T$ 是否停止。愚蠢的？是的，但它说明了一点：它不是我们真正想要表示的集合，而是一个带有相关操作的集合。图灵机上的相关操作有哪些？本质上，我们想要一个表示，使 utm 和 smn 定理成立。前者表示表示应该是这样的，我们可以计算将图灵机应用于输入时会发生什么，而后者表示柯里化操作应该是可计算的。可以证明任何这样的表示都有一个不可判定的停机问题。那好多了。一般来说，我们可以使任何函数 $f : X \to Y$ 可计算，只要我们允许改变 $X$ 的表示：将 X$ 中的元素 $x 表示为成对 $(a, b)$ where $a $代表$x$（在$X$的原始表示中），$b$在$Y$的表示中代表$f(x)$。函数 $f$ 然后变得容易计算作为第一个投影：给定一对表示 $x$ 的 $(a,b)$，值 $f(x)$ 由 $b$ 表示。有时很难发现集合上的哪些操作是“相关的”。你说实数$\mathbb{R}$的相关结构是什么？可计算数学的专家对答案持不同意见。每个人都想要可计算的算术运算 $+$、$-$、$\times$、$/$ 以及可计算的常量 $0$ 和 $1$，但还有什么？如果您说关系 $<$ 应该可以作为从 $\mathbb{R}$ 到布尔真值的函数进行计算，那么您是一个很好的伙伴，尽管您选择了一个相当不切实际的实数计算模型。要求 $<$ 作为从 $\mathbb{R}$ 到半可判定真值的函数是可计算的要合理得多。本质上，实数的相关结构是戴德金完全阿基米德有序场的结构，它也是公开的、豪斯多夫的和局部紧的。不，等等！相关结构是柯西完全阿基米德有序域的结构！哦不，我不同意自己！至少好消息是，一旦我们确定了一个集合的相关数学结构，我们就可以自动计算其计算机表示的描述。

记住，当你看到有人声称某某集合不能用计算机表示时，你应该总是问“但是你想用集合上的哪些操作来计算？”有两个流行的论点据称表明我们不能用计算机表示不可数集： 计算机用 0 和 1 的有限序列表示一切。这样的序列只有可数多个，因此，我们不能表示不可数集。即使我们允许无限的二进制流，我们实际上也只能使用可计算的，而且只有可数的很多。确实，只有可数多个由 0 和 1 组成的有限序列。更准确地说，有可计算的许多这样的序列，因为有一个程序可以枚举它们。但是您是否知道可计算可数集可能包含不可计算可数的子集？例如，所有图灵机的集合是可计算的，但那些不停机的图灵机的子集则不是。第一个论点依赖于这样一个事实，即我们正在谈论任意枚举，包括不可计算的枚举。事实上，如果我们认真对待可计算性，第二个论点立即失败，因为 0 和 1 的可计算无限流的集合对于一个著名的对角线论点来说是可计算不可数的。 （请注意，“可计算不可数”不仅仅是“不可计算可数”：前者意味着给定任何枚举，我们都可以计算枚举之外的元素，而后者只是说没有枚举所有元素。）第二个参数仅当我们以正确的方式混合“可计算”和“不可计算”成分时才有效。即使我们忽略有关可计算与不可计算枚举的理论问题，我们仍然会面临真正的计算机是否“包含”不可计算序列的问题。他们吗？宇宙有吗？或者您是否声称物理学家能够输入计算机的所有 0 和 1 流绝对是可计算的？也许物理学家应该设计一个实验来告诉我们一些关于不可计算流的存在。我想我们很快就会发现这样的实验原则上是不可能的，因为我们可能只能观察到二进制流的有限前缀。根据验证原则，这使得问题变得毫无意义，任何关于其真实性的立场都是一种信仰。

最后，让我们说计算机可以代表我们宇宙的所有无限二进制流，因为计算机配备了 I/O 设备，可以让它们与宇宙交互。如果你是一位受过经典逻辑训练的人类物理学家，那么宇宙中是否有无数的二元流是一个信仰问题。如果您是计算机，问题就很清楚了：可以计算出无数的二进制流。一个更有趣的问题是二进制流的空间是否紧凑，但那是另一回事。我不确定是否公平地说，物理学家实际上会根据验证原理之类的东西，将不可计算流的物理生成可能性问题视为毫无意义。我们只能观察二进制流的有限前缀这一事实使我们在“存在只有有限多个 0 的二进制流”和“存在不可计算的二进制流”方面处于类似的位置，不是吗？然而，每个物理学家都会说前一个问题已经解决了（通过归纳基础让我们相信某些流都是 1）。类似地，我们至少可以根据归纳原理得出结论，即某些物理过程实际上会产生一个二进制流，例如，每当此类计算停止时，其第 n 个值与第 n 个程序在其自身上的值不同。从而得出不可计算二进制流的物理存在性。我认为这种情况不太可能发生，但这仅仅是因为我出于迷信而不是逻辑的原因，怀疑世界是这样运作的，因此认为永远不会找到必要的经验证据.然而，很明显，科学实践的方法本身对得出这样的结论没有必要的障碍。 （我在上面写的“第 n 个程序本身”，我的意思当然是“输入 n 上的第 n 个程序”）你说得对，我在拖入验证原则时有点草率。真正重要的是物理定律是否预测可计算流的存在或不存在，而不是我们可以在有限时间内验证的内容。另请注意，可能存在以概率方式测试不可计算流是否存在的时髦实验，而实际上并未展示不可计算流。但是，“存在只有有限多个 0 的二进制流”和“存在不可计算的二进制流”之间似乎确实存在差异，即我可以产生一种机制，该机制输出 1s 的无限流，并从当前接受的法律中证明不包含任何 0 的物理学（模理想化，例如“机制不会中断或耗尽能量和时间”）。是否有可能构建一种输出二进制流的机制，并使用当前公认的物理定律证明它输出的是不可计算的流？是否有可能从目前公认的物理定律证明不存在这种机制？我怀疑当前的物理定律对这两种选择都没有太多说明。

为什么从实用的角度来看它很重要？对于计算任务，我们只需要能够提供输入并读取输出（可能以统一的方式），我们不需要能够计算任何表示的函数。这是接受表示（/编码/编号/命名）的充分条件吗？正如我在 1 中所写，重要的是我们应该能够与计算机器进行通信。运营部门是否同意这一点？ Kaveh：如果接收方不以任何方式分析数据，那么交流数据是没有意义的。要知道给定的数据传达/代表/命名什么，就是能够对数据做一些合理的事情，即，您想对数据执行一些操作。所以这是非常务实的，真的。举个例子（这与我上面写的基本相同）：假设我们是两家银行，它们相互交流信用卡号码。我们想就一个协议达成一致，该协议允许我们“提供输入”和“读取输出”，但我们对信用卡号码应该能够做什么没有强加任何要求。那么下面的（奇怪的）协议就可以了：每当你想向我传达信用卡号码时，只需向我发送字符串“hi”。你已经输入了，我已经阅读了输出。一旦我们想对信用卡号做点什么，这个协议就会很糟糕。这就是我这篇文章的重点：首先弄清楚你想要做什么（例如“我希望能够说出信用卡号码的数字”），然后你选择一个表示。您还询问了使陈述可接受的充分条件。这是一个被不同人研究过的问题。例如，在第二类计算中，“好的表示”具有拓扑特征，并以可接受的名称命名。另一种可能性是表达表征数据的抽象数学属性，然后使用逻辑和类型理论的可实现性解释计算表示。 RZ就是这样做的。 “那么让我们说计算机可以代表我们宇宙的所有无限二进制流”

你忘了提到，在我们的宇宙中是否存在无限的二进制流也是一个信仰问题。我很确定没有，所有二进制流都是有限的。 @Steven：“计算机可以表示我们宇宙中所有无限的二进制流”的假设并没有假设任何关于此类流的存在。所以我不明白为什么你的评论是相关的。此外，我认为“我们的宇宙中是否存在无限流？”之类的讨论。除非所涉及的概念被很好地定义，否则有点毫无意义，否则人们总是可以通过说“这取决于你所说的‘是’的意思”来捍卫自己的立场。 andrej> “计算机可以表示我们宇宙中所有无限的二进制流”的假设并没有假设这些流的存在。好吧，你让 Steven 参与他的推论是完全正确的，但这确实预设了（因为这里我们无疑预设了 Church--Turing）无限流至少是递归的，这是一个不平凡的主张。考虑一下不相容的说法，即自然界中有无限的流，但这些都是不确定的。在我看来，这确实是有道理的。 @Charles：我重申；当我说“计算机可以代表我们宇宙的所有无限二进制流”时，我并没有假设任何关于我们宇宙的无限二进制流的可计算性或存在性。此外，因为存在无数无限二进制流的证明是有建设性的，所以无论我们假设无限二进制流的可计算性如何，它都有效。 […] Bauer 写了一篇博客文章，其中讨论了代表性的重要性。他举了两个例子。首先，他 [...] 使用 Markdown 写下您的评论。使用 $⋯$ 进行内联，$$⋯$$ 用于显示 LaTeX 公式，以及 <pre>⋯</pre> 用于显示代码。您的电子邮件地址仅用于计算您的 Gravatar，不会存储在任何地方。评论通过拉取请求进行审核。