567
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − A '''Turing machine''' is a [[mathematical model of computation]] that defines an [[abstract machine]],<ref name=":3">Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref> which manipulates symbols on a strip of tape according to a table of rules.<ref name=":4">Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> Despite the model's simplicity, given any [[computer algorithm]], a Turing machine capable of simulating that algorithm's logic can be constructed.<ref name=":5">Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>+ − − 图灵机定义了一个抽象的机器<ref name=":3" />：“<font color="’’#ff800’’">数学计算模型mathematical model of computation”</font>，它根据不同的算法规则表在磁带上上操纵符号<ref name=":4" /> 来实现。虽说图灵机非常简单，但可以用来模拟任何算法<ref name=":5" />。图灵机的设计模式对人们使用纸和笔进行数学计算的过程进行抽象，让机器代替人类进行数学计算。 − The machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there. Then, as per the symbol and the machine's own present state in a "finite table" of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation. + + + − The Turing machine was invented in 1936 by [[Alan Turing]],<ref name="Hodges-2012">{{cite book| first=Andrew | last=Hodges | authorlink =Andrew Hodges | year = 2012 | title =Alan Turing: The Enigma |publisher =[[Princeton University Press]] |isbn=978-0-691-15564-7| edition=The Centenary }}</ref><ref>The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by [[M. H. A. Newman]] in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process"which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).</ref> who called it an "a-machine" (automatic machine).<ref>See footnote in Davis 2000:151.</ref> With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.<ref>Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.</ref><ref>{{cite journal | url=http://plms.oxfordjournals.org/content/s2-42/1.toc | first=Alan Mathison |last=Turing | title=On Computable Numbers, with an Application to the Entscheidungsproblem | journal=Proceedings of the London Mathematical Society, Series 2 | volume=42 | number=1 | pages=230–265 | year=1937 | doi=10.1112/plms/s2-42.1.230 }} — Reprint at: {{cite web+ − − |url=http://www.turingarchive.org/viewer/?id=466&title=01e|accessdate=9 July 2020|first=Alan |last=Turing |title=On computable numbers, with an application to the Entscheidungsproblem|website=The Turing Digital Archive }}</ref> Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the [[computability|uncomputability]] of the ''[[Entscheidungsproblem]]'' ('decision problem').<ref>Turing 1936 in ''The Undecidable'' 1965:145</ref> − − The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine" (automatic machine). With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol. Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the ’’’<font color=’’#ff8000’’> 可判定性Entscheidungsproblem </font>’’’ ('decision problem'). − − 图灵机是1936年由阿兰 · 图灵Alan Turing发明的，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题: (1)是否存在一台机器，能够确定其磁带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ; 同样地，(2)是否存在一台机器，可以确定其磁带上的任意机器是否曾打印过给定的符号。因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是可判定性(“决策问题”)的不可计算性。 − − − 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 completeness]] is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored. − Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored. − ’’’<font color=’’#ff8000’’>图灵完备性 Turing completeness</font>’’’是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。+ 第45行：
第29行： − A Turing machine is a general example of a central processing unit (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (automaton) capable of enumerating some arbitrary subset of valid strings of an alphabet; these strings are part of a recursively enumerable set. A Turing machine has a tape of infinite length on which it can perform read and write operations. − +
无编辑摘要
{{Automata theory}}
{{Automata theory}}
图灵机定义了一个抽象的机器<ref name=":3">Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.</ref>：“<font color="’’#ff800’’">数学计算模型mathematical model of computation”</font>，它根据不同的算法规则表在磁带上上操纵符号<ref name=":4">Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".</ref> 来实现。虽说图灵机非常简单，但可以用来模拟任何算法<ref name=":5">Sipser 2006:137 "A Turing machine can do everything that a real computer can do".</ref>。图灵机的设计模式对人们使用纸和笔进行数学计算的过程进行抽象，让机器代替人类进行数学计算。
The machine operates on an infinite<ref name=":0">Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref name=":1">Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref name=":2">This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>
The machine operates on an infinite<ref name=":0">Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".</ref> memory tape divided into [[discrete mathematics|discrete]] "cells".<ref name=":1">Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.</ref> The machine positions its "head" over a cell and "reads" or "scans"<ref name=":2">This word is used by e.g. Davis 2000:151</ref> the symbol there. Then, as per the symbol and the machine's own present state in a "finite table"<ref>This table represents an [[algorithm]] or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.</ref> of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),<ref>Boolos Burgess and Jeffrey 2002:25</ref> then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),<ref>Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.</ref> then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation.<ref>"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at [[Halting problem]].</ref>
机器在一个无限<ref name=":0" />大的存储磁带上运行，磁带被分割成若干个离散的“单元”。<ref name=":1" /> 机器将它的“头”定位在一个单元上，并“读取”或“扫描”<ref name=":2" /> 那里的符号。然后，根据符号和机器本身在用户指定指令的“有限表”中的现状，机器（i）将符号（例如，有限字母表中的一位数字或一个字母）写入单元（某些型号允许擦除符号或不写入字符），然后(ii)将磁带向左或向右移动一个单元格(有些模型允许不移动，有些模型允许移动磁头) ，然后(iii)(根据观察到的符号和机器自身在表中的状态)继续执行后续指令或停止计算。
机器在一个无限<ref name=":0" />大的存储磁带上运行，磁带被分割成若干个离散的“单元”。<ref name=":1" /> 机器将它的“头”定位在一个单元上，并“读取”或“扫描”<ref name=":2" /> 那里的符号。然后，根据符号和机器本身在用户指定指令的“有限表”中的现状，机器（i）将符号（例如，有限字母表中的一位数字或一个字母）写入单元（某些型号允许擦除符号或不写入字符），然后(ii)将磁带向左或向右移动一个单元格(有些模型允许不移动，有些模型允许移动磁头) ，然后(iii)(根据观察到的符号和机器自身在表中的状态)继续执行后续指令或停止计算。
[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]
图灵机是1936年由阿兰 · 图灵Alan Turing<ref name="Hodges-2012">{{cite book| first=Andrew | last=Hodges | authorlink =Andrew Hodges | year = 2012 | title =Alan Turing: The Enigma |publisher =[[Princeton University Press]] |isbn=978-0-691-15564-7| edition=The Centenary }}</ref><ref>The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by [[M. H. A. Newman]] in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process"which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).</ref> 发明的，他称之为“自动机”<ref>See footnote in Davis 2000:151.</ref> 。通过这个模型，图灵能够否定地回答两个问题: (1)是否存在一台机器，能够确定其磁带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ; 同样地，(2)是否存在一台机器，可以确定其磁带上的任意机器是否曾打印过给定的符号<ref>Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.</ref><ref>{{cite journal | url=http://plms.oxfordjournals.org/content/s2-42/1.toc | first=Alan Mathison |last=Turing | title=On Computable Numbers, with an Application to the Entscheidungsproblem | journal=Proceedings of the London Mathematical Society, Series 2 | volume=42 | number=1 | pages=230–265 | year=1937 | doi=10.1112/plms/s2-42.1.230 }} — Reprint at: {{cite web
|url=http://www.turingarchive.org/viewer/?id=466&title=01e|accessdate=9 July 2020|first=Alan |last=Turing |title=On computable numbers, with an application to the Entscheidungsproblem|website=The Turing Digital Archive }}</ref> 。因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是可判定性(“决策问题”)的不可计算性。<ref>Turing 1936 in ''The Undecidable'' 1965:145</ref>
图灵机证明了机械计算能力的基本限制的存在。虽然它们可以表达任意的计算，但它们的最小设计使它们不适合在实践中计算: 现实世界的计算机是基于不同的设计，与图灵机不同的是，它们使用“<font color="’’#ff8000’’">随机存取存储器random-access memory ”</font>。
<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==
==Overview==
A Turing machine is a general example of a [[central processing unit]] (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine ([[automaton]]) capable of [[enumeration|enumerating]] some arbitrary subset of valid strings of an [[Alphabet (formal languages)|alphabet]]; these strings are part of a [[recursively enumerable set]]. A Turing machine has a tape of infinite length on which it can perform read and write operations.
A Turing machine is a general example of a [[central processing unit]] (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine ([[automaton]]) capable of [[enumeration|enumerating]] some arbitrary subset of valid strings of an [[Alphabet (formal languages)|alphabet]]; these strings are part of a [[recursively enumerable set]]. A Turing machine has a tape of infinite length on which it can perform read and write operations.
图灵机是’’’<font color=’’#ff8000’’> 中央处理器central processing unit</font>’’’(CPU)的一个通用例子，它控制着计算机进行的所有数据操作，规范机器使用顺序存储器来存储数据。更具体地说，它是一种能够枚举字母表有效字符串的一些任意子集的机器（自动机）; 这些字符串是字母递归可枚举集的一部分。图灵机有一卷无限长的磁带，它可以在上面执行读写操作。
图灵机是’’’<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.