computer-science - 什么是图灵机？

Question

什么是图灵机？为什么人们不断提及它？我的计算只需要我的 IBM PC!为什么有人关心这些机器？

Answer 1

图灵机之所以重要，与经典计算科学或计算理论类型的研究有关。它基本上是关于分析计算机的一般属性，例如计算机具有哪些理论能力和局限性，以及当我们谈论“计算”某物时的含义。

可以使用图灵机研究的一个例子是 The Halting Problem 。虽然这个问题属于学术问题，但它对现实世界具有明显的影响。为什么不编写一个调试器来简单地告诉您程序是否包含任何无限循环？停止问题表明，在一般情况下解决此问题是不可能的。

图灵机的研究也有助于研究语言语法及其类别，从而导致编程语言的开发。术语“正则表达式”的出现是因为它们是 regular grammar ，并且对这些语法的研究(计算理论的一部分)将告诉您更多关于正则表达式可以解决什么类型的问题以及不能解决什么类型的问题。例如，传统的正则表达式语法无法解决以下问题:解析输入中的 N 个字符“a”，然后解析相同数量的 N 个字符“b”。

如果您对有关此类事情的好文章感兴趣，请查看 Introduction to the Theory of Computation作者:迈克尔·西普瑟。很好。