567
个编辑
更改
→Overview
<font color="’’#ff8000’’">“图灵完备性 Turing completeness”</font>是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务<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> ; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
<font color="’’#ff8000’’">“图灵完备性 Turing completeness”</font>是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务<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> ; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
==Overview==
==图灵机概述==
图灵机是一种“<font color="’’#ff8000’’">中央处理器central processing unit”</font>(CPU)，它控制着计算机正在进行的所有数据操作，规范机器使用顺序存储器来存储数据。更具体地说，它是一种能够枚举字母表有效字符串的一些任意子集的机器（自动机）; 这些字符串是字母递归可枚举集的一部分。图灵机有一卷无限长的磁带，它可以在上面执行读写操作。
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>’’’是不可解的，停机问题对计算的理论极限有着重大的影响。
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 method]]s in [[logic]] and [[mathematics]], and provide a precise definition of an [[algorithm]] or "mechanical procedure". Studying their [[abstract machine|abstract properties]] yields many insights into [[computer science]] and [[computational complexity theory|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 method]]s in [[logic]] and [[mathematics]], and provide a precise definition of an [[algorithm]] or "mechanical procedure". Studying their [[abstract machine|abstract properties]] yields many insights into [[computer science]] and [[computational complexity theory|complexity theory]].
任一图灵机能够模拟任何其他被称为’’’<font color=’’#ff8000’’> 通用图灵机universal Turing machine</font>’’’(UTM，或简称为通用机)的图灵机。阿隆佐 · 丘奇Alonzo Church提出了一个具有更强数学取向的定义，具有类似的“普遍性”。他关于 λ 微积分的工作与图灵的工作相互交织，形成了一个被称为“丘奇-图灵理论”的计算形式理论。该论文指出，图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
===Physical description===
===实体描述===
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:
</ref>}}
</ref>}}
更切确地说，图灵机由以下部分组成:
更切确地说，图灵机由以下部分组成: