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

Question

当我正在研究图灵机和PDA时,我认为第一台计算设备是图灵机.

因此,我认为存在一种称为图灵机的实用机器,其状态可以用一些特殊设备(比如触发器)来表示,它可以接受磁带中的输入.

因此我怀疑如何在磁带中表示输入字符串？.但是通过答案和我书中给出的细节,我才知道图灵机是一些假设的东西.

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

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

Answer 1

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

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

1. 推断可能计算的极限.因为图灵机能够模拟地球上的任何计算机(或者,根据Church-Turing论文,任何物理上可实现的计算设备),如果我们能够展示图灵机可以计算的限制,我们可以证明什么是极限可能希望在实际的计算机上完成.

2. 形式化算法的定义.为什么二进制搜索算法而语句"猜答案"不是？为了回答这个问题,我们必须有一个关于计算机是什么以及算法意味着什么的正式模型.将图灵机作为计算模型使我们能够严格定义算法是什么.实际上,没有人愿意将算法转换为格式,但这样做的能力使算法和可计算性理论领域成为一个坚实的数学基础.

3. 形式化确定性和非确定性算法的定义.现在计算机科学中最大的开放性问题可能是P = NP的问题.如果你有一个P和NP的正式定义,这个问题才有意义,如果确定性和非确定性计算(这在技术上它们可以使用二阶逻辑定义),这些定义又需要定义.使用图灵机可以让我们在NP中讨论重要问题,并为我们提供一种找到NP完全问题的方法.例如,SAT是NP-complete的证明使用了SAT可用于编码图灵机并且在输入上执行的事实.

希望这可以帮助!

Answer 2

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

以下是一个视频:http://www.youtube.com/watch？v = E3keLeMwfHY