51
个编辑
更改
无编辑摘要
Turing machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.
Turing machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.
图灵机证明了机械计算能力的基本限制的存在。虽然它们可以表达任意的计算，但是它们的最小设计使它们不适合在实践中计算: 现实世界的计算机是基于不同的设计，与图灵机不同的是，它们使用’’’<font color=’’#ff8000’’>随机存取存储器random-access memory </font>’’’。
Turing machines proved the existence of fundamental limitations on the power of mechanical computation.<ref>Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."</ref> While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world [[computer]]s are based on different designs that, unlike Turing machines, use [[random-access memory]].
Turing machines proved the existence of fundamental limitations on the power of mechanical computation.<ref>Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."</ref> While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world [[computer]]s are based on different designs that, unlike Turing machines, use [[random-access memory]].
Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing.
Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing.
假设有一个’’’<font color=’’#ff8000’’> 黑匣子black box</font>’’’，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是由于’’’<font color=’’#ff8000’’> 停机问题halting problem </font>’’’是不可解的，这对计算的理论极限有重大的影响。
假设有一个’’’<font color=’’#ff8000’’> 黑匣子black box</font>’’’，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为’’’<font color=’’#ff8000’’> 停机问题halting problem </font>’’’是不可解的，停机问题对计算的理论极限有着重大的影响。
The Turing machine is capable of processing an [[unrestricted grammar]], which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through [[lambda calculus]].
The Turing machine is capable of processing an [[unrestricted grammar]], which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through [[lambda calculus]].
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory.
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory.
能够模拟任何其他图灵机的图灵机被称为’’’<font color=’’#ff8000’’> 通用图灵机universal Turing machine</font>’’’(UTM，或简称为通用机)。阿隆佐 · 丘奇Alonzo Church提出了一个具有更强数学取向的定义，具有类似的“普遍性”。他关于 λ 微积分的工作与图灵的工作相互交织，形成了一个被称为“丘奇-图灵理论”的计算形式理论。该论文指出，图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
===Physical description===
===Physical description===