嗨，我对可数性有疑问。为什么有必要找出某些事物是否可数。找到它有没有用？而且，如果某些事情是不可数的，是否意味着没有图灵机可以解决它？
问问题
2266 次
3 回答
4
我希望我不是通过回答您的问题来帮助您回答考试问题。
可数性和图灵机是同一枚硬币的两个方面。它们是确定问题是否“可计算”的互补方式。还有其他显示可计算性的等效方法（查找算盘机、可数函数、可计算函数等）。根据定义，如果您可以证明可以通过图灵机解决问题，那么您就可以证明该问题是可计算的。或者，如果您可以证明它具有来自可数无限集的解双射，则您可以证明该问题是可计算的。
顺便说一句，可数无限集是“小”无限集或集合ℵ₀。（通俗地说，小无限或可数无限集是整数的集合。整数、奇数或偶数具有相同的基数——小无限集。无限集有一个无限层次，从ℵ₀开始向上到ℵ_∞。ℵ₀，整数集合，是最小的无限集合。ℵ₁ 是ℵ₀的超集。R，实数集合，与ℵ₁具有相同的基数，依此类推。）了解存在层次结构无穷大将帮助您了解需要证明什么来显示可计算性。
基本的图灵机有一个小的无限磁带。表明一个问题可以由图灵机计算意味着表明该问题有一个以无限小的时间和空间为界的解决方案。图灵机有一个磁带，它有无限的单元可以保存符号。任一方向都有无限单元（小无限），就像整数集在任一方向上都是无限的。与磁带相关的是一个读写头，它可以在磁带上向左或向右移动，每次移动时都可以读取或写入一个符号。显示将磁带上的磁头从初始状态移动到最终停止或终止状态的一系列指令是为了表明问题是“可计算的”。证明图灵机无法解决问题就是证明问题是不可计算的——无论我们是否给予可数无限的时间或资源。顺便说一句，时间和空间是互补的。如果您可以使用可数无限空间在有限时间内解决问题，或者使用可数（即小）无限时间使用有限空间解决问题，则表明该问题是可计算的。
于 2012-04-02T06:36:23.153 回答
3
我可以给你一点答案（抱歉我只懂一点计算理论）。
图灵机的数量是可数的。所以，如果你有一组不可数的问题，你就知道这组问题中至少有一个问题没有图灵机可以解决。
因此，例如，如果您的一组问题是
对于某个函数 f:N -> N，编写一个程序，给定 n，计算 f(n)
你知道至少有一个f不能给出这样的程序，因为有无数这样f的 .
不过，我不相信这种分析可以应用于停机问题，因为停机问题正好包含一个问题：“给定图灵机的代码，决定给定一张空白磁带，它是否最终会停机。” 这只是一个具有可数许多可能输入的问题，因此，仅通过计数，它看起来就有可能解决。您必须以其他方式争论它无法解决。
当然，可数性和不可数性的重要性远比这个例子多样化。我希望其他人可以提供更多。
于 2012-03-17T09:17:36.873 回答
0
对于图灵机以及数学和科学的许多其他地方，可数性实际上非常重要。A 由于图灵机必须按顺序执行操作，因此可以为每个步骤分配一个计数。如果这个过程永远持续下去，那么这个过程是可数无限的。
图灵机不适用的一个操作示例是将 1 和 2 之间的所有数字的平方相加。可以很容易地证明，这个区间中的整个有理数列表可以列在一个可数列表中每个数字都可以与计数数字一一对应。因此，在这个数字列表上一次一个地执行步骤可以由图灵机执行。然而，这不能用这个区间的无理数来完成，因为它们太多了。可以证明（不太容易）无理数列表不能放入有序（可数）列表中。因此，没有顺序可以列出区间上的每个数字，这意味着即使给定无限的时间，图灵机也无法完成任务。
于 2012-04-02T04:15:25.130 回答