图灵机是真正的设备还是想象的概念？

Question

当我正在研究图灵机和掌上电脑时，我在想第一台计算设备是图灵机。

因此，我认为存在一种名为图灵机的实用机器，其状态可以用一些特殊设备（比如触发器）来表示，它可以接受磁带作为输入。

因此我问了how input strings are represented in magnetic tapes，但根据答案和我书中的细节，我才知道图灵机在某种程度上是假设的。

我的问题是，图灵机如何实际实施？例如，它如何用于检查当前处理器中的拼写错误。

图灵机是否已过时？还是他们还在使用？

Answer 1

当图灵首先设计出现在所谓的图灵机器时，他出于纯粹的理论原因这样做（它们被用来证明存在不可判定的问题）并且没有真正在现实世界中构建一个。快进到现在，除了业余爱好者为了这样做而建立图灵机之外，TM基本上只限于理论之地。

由于几个原因，在实践中不使用图灵机。对于初学者来说，构建一个真正的TM是不可能的，因为你需要无限的资源来构建无限的磁带。 （您可以想象使用有限数量的磁带构建TM，然后根据需要添加更多磁带。）此外，由于数据访问的顺序性，图灵机本质上比其他计算模型慢。例如，图灵机不能跳过数组的中间而不首先遍历它想要跳过的数组的所有元素。最重要的是，图灵机非常难以设计。例如，尝试编写图灵机来对32位整数列表进行排序。 （实际上，请不要。这真的很难！）

这就引出了一个问题......为什么要研究图灵机呢？幸运的是，有很多理由这样做：

1. 推断可能计算的极限。因为图灵机能够模拟地球上的任何计算机（或者，根据Church-Turing论文，任何物理上可实现的计算设备），如果我们能够展示图灵机可以计算的限制，我们可以证明什么是极限可能希望在实际的计算机上完成。
2. 形式化算法的定义。为什么二进制搜索算法而语句“猜答案”不是？为了回答这个问题，我们必须有一个关于计算机是什么以及算法意味着什么的正式模型。将图灵机作为计算模型使我们能够严格定义算法是什么。实际上，没有人愿意将算法转换为格式，但这样做的能力使算法和可计算性理论领域成为一个坚实的数学基础。
3. 形式化确定性和非确定性算法的定义。可能现在计算机科学中最大的开放性问题是whether P = NP。如果你有一个P和NP的正式定义，这个问题才有意义，如果确定性和非确定性计算，这些定义又需要定义（尽管从技术上讲，它们可以使用二阶逻辑定义）。使用图灵机可以让我们谈谈NP中的重要问题，并为我们提供一种找到NP完全问题的方法。例如，SAT是NP-complete的证明使用了SAT可用于编码图灵机并且在输入上执行的事实。

希望这可以帮助！

Answer 2

这是一个无法实现的概念设备（由于无限磁带的要求）。有些人已经建立了图灵机的物理实现，但由于物理限制，它不是真正的图灵机。

这是一个视频：http://www.youtube.com/watch?v=E3keLeMwfHY

Answer 3

图灵机不是物理机器，而是基本上是概念机器。图灵概念是假设，这在现实世界中很难实现，因为我们需要无限的磁带来实现小而简单的解决方案。

Answer 4

这是一个理论机器，来自维基百科的以下段落

图灵机是一种理论设备，它根据规则表操纵磁带上的符号。尽管它很简单，但图灵机可以适用于模拟任何计算机算法的逻辑，并且在解释计算机内部CPU的功能时特别有用。

这台机器和非确定性机器等其他机器（实际上不存在）在计算复杂性方面非常有用，并证明一种算法比另一种算法更难或一种算法无法解决......等等

Answer 5

图灵机（TM）是用于计算设备的数学模型。它是真正可以计算的最小模型。事实上，您使用的计算机是一个非常大的TM。 TM不会过时。我们有其他的计算模型，但是这个模型用于构建当前的计算机，因此，我们非常感谢1936年提出这个模型的Alan Turing。