150
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由Solitude初步翻译。+ − {{Short description|Mathematical model of computation that defines an abstract machine}} − {{turing}} − {{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> + − 机器在一个无限<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> ; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。+ − ==图灵机概述==+ − 图灵机是一种“<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. + − 假设有一个“<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]].+ − 图灵机能够处理不受限制的语法，这进一步意味着它能够以无限多的方式稳健地评价一阶逻辑。通过λ演算可以证明这一点。 − 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提出了一个具有更强数学取向的定义，具有类似的“普遍性”。他关于 λ 微积分的工作与图灵的工作相互交织，形成了一个被称为“丘奇-图灵理论”的计算形式理论。该论文指出，图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。+ − ===实体描述===+ + − In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:+ − 在他1948年的论文《智能机器》中，Turing写道，他的机器包括:+ − {{quote|...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.<ref>See the definition of "[[wikt:innings|innings]]" on [[Wiktionary]]</ref>|Turing 1948, p. 3<ref>+ − {{cite web+ − | title=Intelligent Machinery (manuscript)+ − | author=A.M. Turing − | year=1948+ − ...以无限的磁带形式获得无限存储容量，磁带上标有方块，每个方块上都可以打印一个符号。在任何时刻，机器里都有一个符号，它被称为扫描符号。机器可以更改扫描的符号，其行为部分地由这个符号决定，但磁带上其他地方的符号不影响机器的行为。但是，磁带可以在机器中来回移动，这是机器的基本操作之一。因此，磁带上的任何符号最终都可能有局数。 − —Turing 1948年，第3页+ − + − 描述+ − + − {{for|visualizations of Turing machines|Turing machine gallery}} − − The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("[[On Computable Numbers, with an Application to the Entscheidungsproblem]]", see also [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner"). − − The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("On Computable Numbers, with an Application to the Entscheidungsproblem", see also references below), Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner"). − − 图灵机对在磁带上机械操作的机器进行数学建模。这个磁带上有符号，机器可以用磁头一次一个地读写。操作完全由一组有限的基本指令决定，如“在状态42中，如果看到的符号是0，写一个1; 如果看到的符号是1，就改为状态17; 在状态17中，如果看到的符号是0，就写一个1，然后改为状态6; ”等等。在原文中(《论可计算的数字，以及对可判定性的应用》，也可参见下面的参考文献) ，Turing想象的不是一种机械装置，而是一个被他称为“计算机”的人，他奴隶般地执行这些确定性的机械规则(或者像Turing所说的那样，“以一种杂乱无章的方式”)。 − − | page=3 − − | url=http://www.alanturing.net/Turing_archive/archive/l/l32/L32-004.html − − The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q<sub>4</sub>) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.) − − 磁头始终位于磁带的某个特定方格上，只显示有限的方格。要执行的指令(q < sub > 4 </sub >)显示在扫描的方格上。(克莱尼Kleene (1952) p.375.) − − | publisher=The Turing Archive − }}+ − Here, the internal state (q<sub>1</sub>) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)+ − 这里，内部状态(q < sub > 1 </sub >)显示在磁头内部，图中将磁带描述为无限的，并预先填充了“0” ，该符号作为空白。系统的完整状态(其“完整配置”) 由内部状态、磁带上的任何非空白符号（在图中为 "11B"），以及磁头相对于这些符号（包括空白）的位置，即 "011B "组成。(根据明斯基Minsky (1967) p.121.) − </ref>}}
图灵机翻译暂存版本
此词条暂由[[用户:ZQ|ZQ]]初步翻译。
A '''Turing machine''' is a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
图灵机是一个数学计算模型，定义了一个抽象的机器，这个机器根据一个规则表在一条纸带上进行操作。虽然这个模型非常的简单，但是任何给定的计算机算法，图灵机都可以模拟出来。
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, based on 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) based on the observed symbol and the machine's own state in the table either proceeds to another instruction or halts the computation.
图灵机在一个无限大的存储纸带上运行，纸带被分割成若干个离散的单元格。机器头放在一个单元格上“读取”或“扫描”纸上的符号。然后，图灵机根据该符号和机器自身在用户指定指令的 "有限表 "中的状态，机器(i)在单元中写下一个符号（例如，有限字母表中的数字或字母）（有些模型允许符号擦除或不写），然后(ii)将纸带向左或向右移动一个单元（有些模型不允许移动，有些模型移动磁头），然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
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:
# 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)?
# 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 ''Entscheidungsproblem'' ('decision problem').[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]
图灵机是1936年由阿兰 · 图灵Alan Turing发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
(1)是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
(2)是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
''因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是可判定性(Entscheidungsproblem, 决策问题)的不可计算性。''
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.
图灵机证明了机械计算能力的基本限制的存在。虽然它们可以表达任意的计算，但它们的最小设计使它们不适合在实践中计算: 现实世界的计算机是基于另外一种设计，与图灵机不同的是，它们使用“随机存取存储器(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）”是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
==图灵机概述==
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.
图灵机是一种中央处理器单元（Central Processing Unit，即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.
假设有一个“黑盒子”，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为停机问题（Halting Problem）是不可解的，停机问题对计算的理论极限有着重大的影响。
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.
==Description==
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（Alonzo Church，美国著名数学家）'''提出了一个更面向数学的定义，具有普遍性。他将在 λ 演算的工作和图灵在正式计算机理论中的工作融合，被称为邱奇-图灵论题。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
===实体描述===
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:<blockquote>...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.
— Turing 1948, p. 3</blockquote>在1948年的论文《智能机器》中，图灵写道他的机器包括:
...以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号；它被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
更切确地说，图灵机由以下部分组成:
更切确地说，图灵机由以下部分组成: