当我研究图灵机和 PDA 时，我认为第一个计算设备是图灵机。
因此，我认为存在一种叫做图灵机的实用机器，它的状态可以用一些特殊的设备（比如触发器）来表示，它可以接受磁带作为输入。
因此，我问了磁带中输入字符串是如何表示的，但是通过答案和我书中给出的细节，我开始知道图灵机在某种程度上是假设的。
我的问题是，如何实际实现图灵机？例如，它如何用于检查我们当前处理器中的拼写错误。
图灵机过时了吗？还是它们还在被使用？
问问题
9390 次
5 回答
37
当图灵第一次设计现在称为图灵机的东西时，他这样做是出于纯粹的理论原因（它们被用来证明不可判定问题的存在），并没有在现实世界中实际构建过。快进到现在，除了业余爱好者为了好玩而构建图灵机之外，TM 基本上仅限于 Theoryland。
由于几个原因，图灵机并未在实践中使用。对于初学者来说，构建一个真正的 TM 是不可能的，因为您需要无限的资源来构建无限的磁带。（您可以想象用有限数量的磁带构建 TM，然后根据需要添加更多磁带。）此外，由于数据访问的顺序性，图灵机本质上比其他计算模型慢。例如，图灵机不能跳到数组的中间而不先遍历它想要跳过的数组的所有元素。最重要的是，图灵机极难设计。例如，尝试编写一个图灵机来对 32 位整数列表进行排序。（实际上，请不要。这真的很难！）
这就引出了一个问题……为什么要研究图灵机？幸运的是，这样做的原因有很多：
推理可能计算的限制。因为图灵机能够模拟地球上的任何计算机（或者，根据 Church-Turing 论文，任何物理上可实现的计算设备），如果我们能够展示图灵机可以计算的极限，我们就可以证明什么的极限可能永远希望在一台实际的计算机上完成。
形式化算法的定义。为什么二进制搜索是一种算法，而“猜测答案”则不是？为了回答这个问题，我们必须有一个关于什么是计算机以及算法意味着什么的正式模型。将图灵机作为计算模型使我们能够严格定义算法是什么。没有人真正想要将算法转换为格式，但这样做的能力为算法和可计算性理论领域提供了坚实的数学基础。
形式化确定性和非确定性算法的定义。目前计算机科学中最大的悬而未决的问题可能是P = NP 是否。这个问题只有在你有 P 和 NP 的正式定义时才有意义，并且如果确定性和 nndeterministic 计算又需要定义（尽管从技术上讲，它们可以使用二阶逻辑来定义）。有了图灵机，我们就可以讨论 NP 中的重要问题，同时为我们提供了一种找到 NP 完全问题的方法。例如，SAT 是 NP 完全的证明使用 SAT 可用于编码图灵机并在输入上执行的事实。
希望这可以帮助！
于 2011-09-09T19:42:21.830 回答
6
这是一个无法实现的概念设备（由于需要无限磁带）。有些人已经构建了图灵机的物理实现，但由于物理限制，它不是真正的图灵机。
于 2011-09-09T19:29:19.677 回答
0
这是一个理论机器，以下段落来自维基百科
图灵机是一种理论上的设备，它根据规则表来操作一条胶带上的符号。尽管图灵机很简单，但它可以用来模拟任何计算机算法的逻辑，并且在解释计算机内部 CPU 的功能时特别有用。
这台机器以及其他机器，如非确定性机器（实际上并不存在）在计算复杂度方面非常有用，并证明一种算法比另一种算法更难，或者一种算法不可解……等等
于 2011-09-09T19:38:28.303 回答
0
图灵机不完全是物理机器，而是基本上是概念机器。图灵的概念是假设，这在现实世界中很难实现，因为我们也需要无限的磁带来实现小而简单的解决方案。
于 2016-07-18T06:05:30.107 回答
0
图灵机 (TM) 是计算设备的数学模型。它是可以真正计算的最小模型。实际上，您使用的计算机是一个非常大的TM。TM 没有过时。我们还有其他计算模型，但这个模型用于构建当前的计算机，因此，我们非常感谢 1936 年提出这个模型的艾伦·图灵。
于 2019-06-10T11:01:34.243 回答