所有图灵机的集合是可数的，而所有无限二进制序列的集合是不可数的
The Set of All Turing Machines is Countable vs the set of all infinite binary sequences is uncountable
试图为期末学习而对可数性感到困惑。
我理解任何图灵机都可以描述为一个字符串。我们有有限数量的输入 (Σ)。我们可以计算每个长度的字符串组合。
假设有 256 个不同的输入符号。
对于字符串长度为1:256的组合。
对于长度为 2 的字符串：我们有 256^2 种组合。
对于长度为k的字符串，我们有256^k种组合。
然后我们给所有这些组合编号。
1, 2 ... 256,
257、258 ... 256 + 256^2 ...
由于自然数是可数的，所以存在双射映射。所以所有图灵机的集合是可数的。
我的问题是为什么我不能对所有无限二进制序列做同样的事情？我找到每个长度的所有组合，对它们进行编号，然后我将得到一个双射映射。
非常感谢！
听起来你在问康托尔对角线论证。给定一组无限序列，您可以制作一个不在该集合中的序列。
这和无理数不能数的说法很相似。鉴于集合由 numbers/strings/etc 组成，您将始终能够制作不在集合中的数字。无限长。
我认为你的论点中最大的缺陷是你说 "I find all the combinations of each length" 但考虑到你允许字符串具有无限长度，这是不可能的。
试图为期末学习而对可数性感到困惑。
我理解任何图灵机都可以描述为一个字符串。我们有有限数量的输入 (Σ)。我们可以计算每个长度的字符串组合。
假设有 256 个不同的输入符号。
对于字符串长度为1:256的组合。
对于长度为 2 的字符串：我们有 256^2 种组合。
对于长度为k的字符串，我们有256^k种组合。
然后我们给所有这些组合编号。
1, 2 ... 256, 257、258 ... 256 + 256^2 ...
由于自然数是可数的，所以存在双射映射。所以所有图灵机的集合是可数的。
我的问题是为什么我不能对所有无限二进制序列做同样的事情？我找到每个长度的所有组合，对它们进行编号，然后我将得到一个双射映射。
非常感谢！
听起来你在问康托尔对角线论证。给定一组无限序列，您可以制作一个不在该集合中的序列。
这和无理数不能数的说法很相似。鉴于集合由 numbers/strings/etc 组成，您将始终能够制作不在集合中的数字。无限长。
我认为你的论点中最大的缺陷是你说 "I find all the combinations of each length" 但考虑到你允许字符串具有无限长度，这是不可能的。