图灵机是一个真实的设备还是一个虚构的概念？
当我研究图灵机和PDA时，我认为第一个计算设备是图灵机。
因此，我认为存在一种称为图灵机的实用机器，它的状态可以用一些特殊设备（比如触发器）来表示，并且它可以接受磁带作为输入。
因此我问输入字符串如何在磁带中表示，但通过我书中给出的答案和细节，我开始知道图灵机在某种程度上是假设的。
我的问题是，图灵机实际上如何实现？例如，如何使用它来检查我们当前处理器中的拼写错误。
图灵机已经过时了吗？或者它们仍在使用吗？
When I am studying about Turing machines and PDAs, I was thinking that the first computing device was the Turing machine.
Hence, I thought that there existed a practical machine called the Turing machine and its states could be represented by some special devices (say like flip-flops) and it could accept magnetic tapes as inputs.
Hence I asked how input strings are represented in magnetic tapes, but by the answer and by the details given in my book, I came to know that a Turing machine is somewhat hypothetical.
My question is, how would a Turing machine be implemented practically? For example, how it is used to check spelling errors in our current processors.
Are Turing machines outdated? Or are they still being used?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
当图灵第一次设计现在所谓的图灵机时，他这样做纯粹是出于理论原因（它们被用来证明不可判定问题的存在），而没有在现实世界中实际构建一个。快进到现在，除了出于乐趣而构建图灵机的爱好者之外，TM 基本上仅限于 Theoryland。
由于多种原因，图灵机并未在实践中使用。对于初学者来说，构建真正的 TM 是不可能的，因为您需要无限的资源来构建无限的磁带。 （不过，您可以想象用有限数量的磁带构建 TM，然后根据需要添加更多磁带。）此外，由于数据访问的顺序性质，图灵机本质上比其他计算模型慢。例如，图灵机无法在不首先遍历它想要跳过的数组的所有元素的情况下跳转到数组的中间。最重要的是，图灵机的设计极其困难。例如，尝试编写一个图灵机来对 32 位整数列表进行排序。 （实际上，请不要。这真的很难！）
这就引出了一个问题......为什么要研究图灵机？幸运的是，这样做有很多理由：
推理可能计算的极限。因为图灵机能够模拟地球上的任何计算机（或者，根据丘奇图灵理论，任何物理上可实现的计算设备），如果我们能够展示图灵机可以计算的极限，我们就可以展示什么的极限可能希望在一台实际的计算机上完成。
形式化算法的定义。为什么二分查找是一种算法，而“猜猜答案”却不是？为了回答这个问题，我们必须有一个关于计算机是什么以及算法意味着什么的正式模型。使用图灵机作为计算模型使我们能够严格定义算法是什么。实际上没有人愿意将算法转换为这种格式，但这样做的能力为算法和可计算性理论领域奠定了坚实的数学基础。
正式化确定性和非确定性算法的定义。目前计算机科学中最大的悬而未决的问题可能是是否P = NP。仅当您对 P 和 NP 有正式定义时，这个问题才有意义，而确定性和不确定性计算又需要定义（尽管从技术上讲，它们可以使用二阶逻辑来定义）。有了图灵机，我们就可以讨论 NP 中的重要问题，同时也为我们提供了一种找到 NP 完全问题的方法。例如，证明 SAT 是 NP 完全的，使用 SAT 可用于对图灵机进行编码并在输入上执行的事实。
希望这有帮助！
When Turing first devised what are now called Turing machines, he was doing so for purely theoretical reasons (they were used to prove the existence of undecidable problems) and without having actually constructed one in the real world. Fast forward to the present, and with the exception of hobbyists building Turing machines for the fun of doing so, TMs are essentially confined to Theoryland.
Turing machines aren't used in practice for several reasons. For starters, it's impossible to build a true TM, since you'd need infinite resources to construct the infinite tape. (You could imagine building TMs with a limited amount of tape, then adding more tape in as necessary, though.) Moreover, Turing machines are inherently slower than other models of computation because of the sequential nature of their data access. Turing machines cannot, for example, jump into the middle of an array without first walking across all the elements of the array that it wants to skip. On top of that, Turing machines are extremely difficult to design. Try writing a Turing machine to sort a list of 32-bit integers, for example. (Actually, please don't. It's really hard!)
This then begs the question... why study Turing machines at all? Fortunately, there are a huge number of reasons to do this:
To reason about the limits of what could possibly be computed. Because Turing machines are capable of simulating any computer on planet earth (or, according to the Church-Turing thesis, any physically realizable computing device), if we can show the limits of what Turing machines can compute, we can demonstrate the limits of what could ever hope to be accomplished on an actual computer.
To formalize the definition of an algorithm. Why is binary search an algorithm while the statement "guess the answer" is not? In order to answer this question, we have to have a formal model of what a computer is and what an algorithm means. Having the Turing machine as a model of computation allows us to rigorously define what an algorithm is. No one actually ever wants to translate algorithms into the format, but the ability to do so gives the field of algorithms and computability theory a firm mathematical grounding.
To formalize definitions of deterministic and nondeterministic algorithms. Probably the biggest open question in computer science right now is whether P = NP. This question only makes sense if you have a formal definition for P and NP, and these in turn require definitions if deterministic and nndeterministic computation (though technically they could be defined using second-order logic). Having the Turing machine then allows us to talk about important problems in NP, along with giving us a way to find NP-complete problems. For example, the proof that SAT is NP-complete uses the fact that SAT can be used to encode a Turing machine and it's execution on an input.
Hope this helps!
它是一个无法实现的概念设备（由于无限磁带的要求）。有些人已经构建了图灵机的物理实现，但由于物理限制，它并不是真正的图灵机。
以下是其中一个视频：http://www.youtube.com/watch?v=E3keLeMwfHY
It is a conceptual device that is not realizable (due to the requirement of infinite tape). Some people have built physical realizations of a Turing machine, but it is not a true Turing machine due to physical limitations.
Here's a video of one: http://www.youtube.com/watch?v=E3keLeMwfHY
图灵机并不完全是物理机器，而是基本上是概念机器。图灵概念是假设，这在现实世界中很难实现，因为我们也需要无限的磁带来实现小而简单的解决方案。
Turing Machine are not exactly physical machines, instead they are basically conceptual machine. Turing concept is hypothesis and this is very difficult to implement in real world since we require infinite tapes for small and easy solution too.
这是一台理论机器，以下段落来自维基百科
该机器与其他机器（例如非确定性机器（现实中不存在））在计算复杂性并证明一种算法比另一种算法更难或一种算法不可解等方面非常有用
It's a theoretical machine, the following paragraph from Wikipedia
This machine along with other machines like non-deterministic machine (doesn't exist in real) are very useful in calculating complexity and prove that one algorithm is harder than another or one algorithm is not solvable...etc
图灵机（TM）是计算设备的数学模型。它是真正可以计算的最小模型。事实上，你使用的电脑是一个很大的TM。 TM并没有过时。我们还有其他计算模型，但这个模型用于构建当前的计算机，因此，我们非常感谢艾伦·图灵，他在 1936 年提出了这一模型。
Turing machine (TM) is a mathematical model for computing devices. It is the smallest model that can really compute. In fact, the computer that you are using is a very big TM. TM is not outdated. We have other models for computation but this one was used to build the current computers and because of that, we owe a lot to Alan Turing who proposed this model in 1936.