什么是图灵机? [英] What's a Turing machine?
问题描述
什么是图灵机?为什么人们不断提到它?我的IBM PC是我进行计算所需的全部！为什么有人会在意这些机器?
What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?
推荐答案
图灵机如此重要的原因与对经典计算科学或计算理论的研究有关.基本上，这是分析计算机的一般属性，例如计算机的理论能力和局限性，以及当我们谈论计算"某物时的意思.
The reason that Turing Machines are a big deal has to do with the study of classical Computing Science or Theory of Computation type stuff. It's basically about analyzing the general properties of a computer, such as what theoretical abilities and limitations a computer has, as well as what we mean when we talk about "computing" something.
停止问题是一个可以使用图灵机学习的示例.尽管此问题是学术活动，但它对现实世界的影响很明显.为什么不编写一个调试器来简单地告诉您程序是否包含无限循环?暂停问题确定了在一般情况下解决该问题是不可能的.
One example of something that one might study using Turing Machines is The Halting Problem. While this problem is something of an academic exercise, it has easily tangible real-world implications. Why not write a debugger that will simply tell you whether or not your program contains any infinite loops? The Halting Problem establishes that solving this problem for the general case is impossible.
对Turing Machines的研究还有助于研究语言语法及其类，从而促进了编程语言的发展.之所以使用正则表达式"，是因为它们是常规语法，并且是对这些语法的研究(计算理论的一部分)将为您详细介绍正则表达式可以解决的问题以及不能解决的问题.例如，传统的正则表达式语法将无法解决以下问题:解析输入中某些数字"a"个字符，然后解析相同数字N的字符"b".
The study of Turing Machines also lends itself to studying language grammars and classes of thereof, which leads into programming language development. The term "regular expressions" comes about because they are a regular grammar, and the study of these grammars (part of Theory of Computation) will tell you more about exactly what kinds of problems regular expressions can solve and what they can't. For example, a traditional regular expression syntax won't be able to solve the following problem: parse some number N of 'a' chars in input, and then parse the same number N of char 'b'.
If you're interested in a good text about this sort of thing, check out Introduction to the Theory of Computation by Michael Sipser. It's good.
这篇关于什么是图灵机?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
