turing-machines - 可数性和图灵机停机之间的关系

Question

您好，我对可数性有疑问。为什么有必要找出某些事物是否可数。找到它有什么用吗？而且，如果某些事情不可数，是否意味着没有图灵机可以解决它？

Answer 1

我希望我不是通过回答你的问题来帮助你回答考试问题。

可数性和图灵机是同一事物的两个方面。它们是确定问题是否“可计算”的补充方法。还有其他显示可计算性的等效方法(查找算盘机、可数函数、可计算函数等)。根据定义，如果你能证明一个问题可以用图灵机解决，那么你就表明这个问题是可计算的。或者，如果可以证明问题具有来自可数无限集的解双射，则可以证明问题是可计算的。

顺便说一句，可数无限集是“小”无限集或集合ℵ₀。 (通俗地说，小无限或可数无限集是整数集。整数、奇数或偶数具有相同的基数——小无限集。无限集有一个无限层次，从ℵ₀开始向上到ℵ_∞。ℵ₀，整数集，是最小的无限集。ℵ₁是ℵ₀的超集。R，实数集，与ℵ₁具有相同的基数，等等。 ) 了解无限的层次结构将帮助您了解需要证明什么才能显示可计算性。

基本图灵机有一个无限小的磁带。表明一个问题可以由图灵机计算意味着表明该问题有一个受小的无限时间和空间限制的解。图灵机有一个磁带，磁带上有无限的单元格，可以容纳符号。在任一方向上都有无限单元格(小无限)，就像整数集在任一方向上都是无限的一样。与磁带相关联的是一个读写头，它可以在磁带上向左或向右移动，并且可以在每次移动时读取或写入一个符号。显示将磁带上的磁头从初始状态移动到最终停止或终止状态的指令序列是为了表明问题是“可计算的”。证明图灵机无法解决问题就是证明问题不可计算——无论我们是否给予可数无限的时间或资源。顺便说一句，时间和空间是相辅相成的。如果您可以使用可数无限空间在有限时间内解决问题，或者使用可数无限(即小)无限时间解决消耗有限空间的问题，则表明该问题是可计算的。