113
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − + 第39行：
第39行： − + − * 一个有限的指令表，给定机器当前所处的状态(q<sub>i</sub>)和它在纸带上读取的符号(a<sub>j</sub>)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）： − − In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled. − 第63行：
第59行： − − A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions <math>\{L,R\}</math>. − − The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples): 第78行：
第70行： − − − Initially all tape cells are marked with <math>0</math>. 第125行：
第114行： − + − 第137行：
第125行： − − The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) in ''The Undecidable'', p. 126-127 and Davis (2000) p. 152): − − Other authors (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) adopt a different convention, with new state '''q<sub>m</sub>''' listed immediately after the scanned symbol S<sub>j</sub>: − − − :: '''(''' current state '''q<sub>i</sub>''' ''',''' symbol scanned '''S<sub>j</sub>''' ''',''' new state '''q<sub>m</sub>''' ''',''' print symbol '''S<sub>k</sub>'''/erase '''E'''/none '''N''' ''',''' move_tape_one_square left '''L'''/right '''R'''/none '''N''' ''')'''+ − − （当前状态 q<sub>i</sub> , 扫描符号 S<sub>j</sub> , 新状态 q<sub>m</sub> , 打印 S<sub>k</sub>/擦除 E/none N , L/right R/none N） − For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.+ − − 本文的其余部分将使用“定义1”(图灵/戴维斯规则)。 第227行：
第205行： − − − In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in ''The Undecidable'', p. 126). He allowed for erasure of the "scanned square" by naming a 0th symbol S<sub>0</sub> = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S<sub>k</sub>" or "erase" (cf. footnote 12 in Post (1947), ''The Undecidable'', p. 300). The abbreviations are Turing's (''The Undecidable'', p. 119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples: 第343行：
第318行： − − Any Turing table (list of instructions) can be constructed from the above nine 5-tuples. For technical reasons, the three non-printing or "N" instructions (4, 5, 6) can usually be dispensed with. For examples see Turing machine examples. − − − Less frequently the use of 4-tuples are encountered: these represent a further atomization of the Turing instructions (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); also see more at Post–Turing machine. − − The word "state" used in context of Turing machines can be a source of confusion, as it can mean two things. Most commentators after Turing have used "state" to mean the name/designator of the current instruction to be performed—i.e. the contents of the state register. But Turing (1936) made a strong distinction between a record of what he called the machine's "m-configuration", and the machine's (or person's) "state of progress" through the computation - the current state of the total system. What Turing called "the state formula" includes both the current instruction and ''all'' the symbols on the tape: − − + − Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the '''state of the system''' may be described by a single expression (sequence of symbols) consisting of the symbols on the tape followed by Δ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression is called the 'state formula'.|''《The Undecidable》'', pp. 139–140, − − − — 《The Undecidable》,图灵，p.139–140 − − − Earlier in his paper Turing carried this even further: he gives an example where he placed a symbol of the current "m-configuration"—the instruction's label—beneath the scanned square, together with all the symbols on the tape (《The Undecidable》, p. 121); this he calls "the complete configuration" (《The Undecidable》, p. 118). To print the "complete configuration" on one line, he places the state-label/m-configuration to the left of the scanned symbol. − A variant of this is seen in Kleene (1952) where Kleene shows how to write the Gödel number of a machine's "situation": he places the "m-configuration" symbol q<sub>4</sub> over the scanned square in roughly the center of the 6 non-blank squares on the tape (see the Turing-tape figure in this article) and puts it to the right of the scanned square. But Kleene refers to "q<sub>4</sub>" itself as "the machine state" (Kleene, p. 374-375). Hopcroft and Ullman call this composite the "instantaneous description" and follow the Turing convention of putting the "current state" (instruction-label, m-configuration) to the left of the scanned symbol (p. 149).+ − − 在Kleene(1952)中可以看到这样的一个变体，Kleene展示了如何写出一台机器的 "状态"的哥德尔数：他把 "m-配置 "符号q<sub>4</sub>放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-纸带图)，并把它放在扫描方格的右边。但Kleene把 "q<sub>4</sub> "本身称为 "机器状态"（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为 "瞬时描述"，并遵循图灵规定，把 "当前状态"（指令标签，m-配置）放在扫描符号的左边（第149页）。 − − Example: total state of 3-state 2-symbol busy beaver after 3 "moves" (taken from example "run" in the figure below): − − − This means: after three moves the tape has ... 000110000 ... on it, the head is scanning the right-most 1, and the state is '''A'''. Blanks (in this case represented by "0"s) can be part of the total state as shown here: '''B'''01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is '''B'''. − − "State" in the context of Turing machines should be clarified as to which is being described: (''i'') the current instruction, or (''ii'') the list of symbols on the tape together with the current instruction, or (''iii'') the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol. − − − − Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion. − 第453行：
第399行： + − [[File:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|The "3-state busy beaver" Turing machine in a [[Finite State Machine|finite state representation]]. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state ''transition'' is shown by an arrow. The label (e.g. '''0/P,R''') near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. '''0''') followed by a slash '''/''', followed by the subsequent "behaviors" of the machine, e.g. "'''P''' '''P'''rint" then move tape "'''R''' '''R'''ight". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).|链接=Special:FilePath/State_diagram_3_state_busy_beaver_2B.svg]]+ − "三态繁忙的海狸"图灵机的有限状态表示。每个圆圈代表表的一个 "状态"--一个 "m-配置"或"指令"。状态转换的"方向"用箭头表示。出状态附近的标签(如0/P,R)(在箭头的"尾部")指定了引起特定转换的扫描符号(如0)，后面是斜线/，接着是机器的后续 "行为"，如“P打印”然后移动纸带"R向右"。没有普遍接受的格式存在。所显示的规则是以McClusky（1965）、Booth（1967）、Hill和Peterson（1974）为蓝本。+ − − To the right: the above table as expressed as a "state transition" diagram. − − 右边：上面的表格表示为"状态转换"图。 − − − Usually large tables are better left as tables (Booth, p. 74). They are more readily simulated by computer in tabular form (Booth, p. 74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p. 244ff)—can be more readily seen when viewed as a drawing. − − − − Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See Finite state machine for more. − − − [[File:Moves of a 3-state Busy Beaver.jpg|thumbnail|500px|right|The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.|链接=Special:FilePath/Moves_of_a_3-state_Busy_Beaver.jpg]]i − − The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom. − The reader should again be cautioned that such diagrams represent a snapshot of their table frozen in time, not the course ("trajectory") of a computation through time and space. While every time the busy beaver machine "runs" it will always follow the same state-trajectory, this is not true for the "copy" machine that can be provided with variable input "parameters".+ − − − The diagram "Progress of the computation" shows the three-state busy beaver's "state" (instruction) progress through its computation from start to finish. On the far right is the Turing "complete configuration" (Kleene "situation"<!-- Stuation? Not Situation? Is that the right word? Yes, it is, cf. page 375 for example "The Godel number of the stiuation..." and then he shows a tape, etc. This usage runs throughout the chapter. wvbailey~~~~ --><!--So is it "stuation" or "stiuation"?-->, Hopcroft–Ullman "instantaneous description") at each step. If the machine were to be stopped and cleared to blank both the "state register" and entire tape, these "configurations" could be used to rekindle a computation anywhere in its progress (cf. Turing (1936) The Undecidable, pp. 139–140).+ − − + − Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)+ − − 许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力(Hopcroft和Ullman p.159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能计算更多的数学函数。(邱奇-图灵理论假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。) − − A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard last-in-first-out semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right. − − 图灵机相当于单堆栈下推自动机(Pushdown Automaton，PDA) ，它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对读写头左侧的纸带进行建模，使用另一个堆栈对读写头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈PDA。 − − At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model. − Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.+ − − 常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机(Deterministic Turing Machine，DTM)和非确定型图灵机（ non-Deterministic Turing Machine , NDTM）(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。 − − Read-only, right-moving Turing machines are equivalent to DFAs (as well as NFAs by conversion using the NDFA to DFA conversion algorithm). − − 只读、右移动的图灵机相当于 DFAs (以及通过使用 NDFA 到 DFA 转换算法转换的 NFA)。 − + − For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language. − − An interesting question is whether the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, ANSI C is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language. However, other programming languages like Pascal do not have this feature, which allows them to be Turing complete in principle. It is just Turing complete in principle, as memory allocation in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot. − + − Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":+ − − − 早在1936年的论文中，图灵就对 "运动......完全由配置决定 "的 "自动机"和 "选择机 "进行了区分： − − − 它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况。——The Undecidable，p.118 − − − − Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 or 1, i<sub>2</sub> = 0 or 1, ..., i<sub>n</sub> = 0 or 1), and hence the number 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, The Undecidable, p. 138) − This is indeed the technique by which a deterministic (i.e., a-) Turing machine can be used to mimic the action of a nondeterministic Turing machine; Turing solved the matter in a footnote and appears to dismiss it from further consideration.+ − − 这通过这种技术，一个确定型的(比如，a-)图灵机可以用来模拟一个非确定型的图灵机的行为; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。 − − An oracle machine or o-machine is a Turing a-machine that pauses its computation at state "o" while, to complete its calculation, it "awaits the decision" of "the oracle"—an unspecified entity "apart from saying that it cannot be a machine" (Turing (1939), The Undecidable, p. 166–168). − + − − − [[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine|链接=Special:FilePath/Model_of_a_Turing_machine.jpg]] − − An implementation of a Turing machine − − As Turing wrote in The Undecidable, p. 128 (italics added):+ − + − 正如图灵在<The Undecidable>一书中所写，第128页 : − − − − 我们可以发明一种机器，用来计算任何可计算序列。如果向机器U提供纸带，纸带的开头写着计算机M用分号隔开的五元数组，那么机器U将计算出与机器M相同的序列。 − − − − This finding is now taken for granted, but at the time (1936) it was considered astonishing. The model of computation that Turing called his "universal machine"—"U" for short—is considered by some (cf. Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the stored-program computer. − − 虽然这一发现现在被认为是很常见的，但在当时(1936年) ，很多人认为这是不可思议的。图灵称之为“通用机器”(缩写为“U”)的计算模型被一些人(参见Davis(2000))认为是产生存储程序计算机概念的基础理论的突破。 − − − 实质上包含了现代计算机的发明以及伴随着它的一些编程技术。——Minsky（1967），P.104 − − + − In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and R. E. Stearns. (Arora and Barak, 2009, theorem 1.9)+ − + − − [[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces|链接=Special:FilePath/Lego_Turing_Machine.jpg]] − − A Turing machine realization using [[Lego pieces]] − − 使用乐高积木实现的图灵机[[Lego pieces]] − − It is often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is neglected in this statement is that, because a real machine can only have a finite number of configurations, this "real machine" is really nothing but a finite state machine. On the other hand, Turing machines are equivalent to machines that have an unlimited amount of storage space for their computations. − − There are a number of ways to explain why Turing machines are useful models of real computers: − + − 1.Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter-passing mechanisms" (Hopcroft and Ullman p. 157). A large enough FSA can also model any real computer, disregarding IO. Thus, a statement about the limitations of Turing machines will also apply to real computers. − − 2.The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data. − − 3.Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media. − − 4.Descriptions of real machine programs using simpler abstract models are often much more complex than descriptions using Turing machines. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent deterministic finite automaton (DFA) on a given real machine has quadrillions. This makes the DFA representation infeasible to analyze. − − − 5.Turing machines describe algorithms independent of how much memory they use. There is a limit to the memory possessed by any current machine, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in ''conventional'' computing machine architecture. − − 6.Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not limited to, running [[out of memory]]). − − − 第611行：
第462行： − − [[File:Turingmachine.jpg|thumb|图灵机的实验原型|链接=Special:FilePath/Turingmachine.jpg]] − − − − − + − A limitation of Turing machines is that they do not model the strengths of a particular arrangement well. For instance, modern stored-program computers are actually instances of a more specific form of [[abstract machine]] known as the [[random-access stored-program machine]] or RASP machine model. Like the [[universal Turing machine]], the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the universal Turing machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory "cells" that can contain any integer (cf. Elgot and Robinson (1964), Hartmanis (1971), and in particular Cook-Rechow (1973); references at [[random access machine]]). The RASP's finite-state machine is equipped with the capability for indirect addressing (e.g., the contents of one register can be used as an address to specify another register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing machine). An example of this is [[binary search]], an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model. − − − − + − Another limitation of Turing machines is that they do not model concurrency well. For example, there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape. (See article on [[unbounded nondeterminism]].) By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size. (A process can be created with local storage that is initialized with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it increments its count by 1 and sends itself a go message. When it receives a stop message, it stops with an unbounded number in its local storage.) − − − − − In the early days of computing, computer use was typically limited to [[batch processing]], i.e., non-interactive tasks, each producing output data from given input data. Computability theory, which studies computability of functions from inputs to outputs, and for which Turing machines were invented, reflects this practice. − − − − Since the 1970s, [[interactivity|interactive]] use of computers became much more common. In principle, it is possible to model this by having an external agent read from the tape and write to it at the same time as a Turing machine, but this rarely matches how interaction actually happens; therefore, when describing interactivity, alternatives such as [[Input/output automaton|I/O automata]] are usually preferred. − 第648行：
第478行： − + − [[Robin Gandy]] (1919–1995)—a student of Alan Turing (1912–1954), and his lifelong friend—traces the lineage of the notion of "calculating machine" back to [[Charles Babbage]] (circa 1834) and actually proposes "Babbage's Thesis":+ − − − − − 整个发展和分析的操作现在都可以由机器来执行。(italics in Babbage as cited by Gandy, p.54) − − − Gandy's analysis of Babbage's [[Analytical Engine]] describes the following five operations (cf. p. 52–53): − − + − − + − + − + − Gandy states that "the functions which can be calculated by (1), (2), and (4) are precisely those which are [[Turing computable]]." (p. 53). He cites other proposals for "universal calculating machines" including those of [[Percy Ludgate]] (1909), [[Leonardo Torres y Quevedo]] (1914), [[Maurice d'Ocagne]] (1922), [[Louis Couffignal]] (1933), [[Vannevar Bush]] (1936), [[Howard Aiken]] (1937). However:+ − + − − − − 重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认...- Gandy，第55页 − + − With regard to [[Hilbert's problems]] posed by the famous mathematician [[David Hilbert]] in 1900, an aspect of problem #10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for #10 is as follows:+ − − 关于著名数学家大卫•希尔伯特（David Hilbert）在1900年提出的希尔伯特问题中，第10号问题的一个方面浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下： − − 10. Diophantine方程的可解性的确定。给出一个具有任意数量的未知量和有理积分系数的Diophantine方程。设计一个过程，根据这个过程可以在有限的操作中确定该方程是否可以用有理整数来解。当我们知道一个程序，允许任何给定的逻辑表达式通过有限的多次操作来决定其有效性或可满足性时，判定问题（一阶逻辑的决定问题）就解决了......判定问题必须被认为是数理逻辑的主要问题。--2008年，德尔肖维茨（Dershowitz）和古列维奇（Gurevich）引用了此译文和德文原文 − − By 1922, this notion of "[[Entscheidungsproblem]]" had developed a bit, and [[Heinrich Behmann|H. Behmann]] stated that + − 判定问题的一般形式如下:需要一个相当明确的、普遍适用的处方，它将允许人们在有限的步骤中决定一个给定的纯逻辑论断的真假... ..+ − —Gandy，第57页，引用Behmann的话。 − Behmann指出：一般问题相当于决定哪些数学命题是真的问题。如果能够解决判定问题，那么人们就会有一个"解决许多（甚至所有）数学问题的程序"。+ + − By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics ''[[Completeness (logic)|complete]]'' ... Second, was mathematics ''[[Consistency proof|consistent]]'' ... And thirdly, was mathematics ''[[Decidability (logic)|decidable]]''?" (Hodges p. 91, Hawking p. 1121). The first two questions were answered in 1930 by [[Kurt Gödel]] at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.+ − 1928年的国际数学家大会，希尔伯特把他的问题描述的非常的细致。第一，数学是完整的吗? 第二，数学是一致的吗? 第三，数学是可判定的吗? ”1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特 · 哥德尔(Kurt Gödel)回答了前两个问题; 而第三个问题（判定问题）不得不等到上世纪30年代中期。+ − − The problem was that an answer first required a precise definition of "''definite general applicable prescription''", which Princeton professor [[Alonzo Church]] would come to call "[[effective calculability]]", and in 1928 no such definition existed. But over the next 6–7 years [[Emil Post]] developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students [[Stephen Kleene]] and [[J. B. Rosser]] by use of Church's [[lambda-calculus]] and Gödel's [[recursion theory]] (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions. − − 问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇（Alonzo Church）将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特（Emil Post）拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生斯蒂芬•克莱恩（Stephen Kleene）和（j.B. Rosser）利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文(发表于1936年4月15日)表明，判定问题确实是“无法决策的” ，比图灵早了将近一年(图灵的论文1936年5月28日提交，1937年1月发表)。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。 − − − 但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。......图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页 − − And Post had only proposed a definition of [[Church–Turing thesis|calculability]] and criticized Church's "definition", but had proved nothing. − − 波斯特只是提出了一个可计算性的定义，并批评了邱奇的“定义” ，但没有证明任何事情。 − − In the spring of 1935, Turing as a young Master's student at [[King's College Cambridge]], [[UK]], took on the challenge; he had been stimulated by the lectures of the logician [[M. H. A. Newman]] "and learned from them of Gödel's work and the Entscheidungsproblem ... Newman used the word 'mechanical' ... In his obituary of Turing 1955 Newman writes: − − + + + − 对于 "什么是'机械'过程 "？图灵回答了一个特有的答案'可以由机器完成的事情'，接着他开始着手分析计算机的一般概念。—Gandy，第74页 + − Gandy states that:+ − − Gandy表示: − I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a [[Cantor's diagonal argument|diagonal argument]] to prove unsolvability.|''ibid.'', p. 76+ − 我想，但我不知道，图灵从他工作的一开始，就把证明判定问题的不可解性作为他的目标。1935年夏天，他告诉我，当他躺在格兰切斯特草地的时候，他完成了这篇论文的构想。这个 "构想"可能是他对计算的分析，也可能是他意识到有一个普遍的机器，因此有一个对角线论证来证明不可解性。- 同上，第76页+ − − While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p. 96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "[[Systems of Logic Based on Ordinals]]", contains the following definition of "a computable function": − − − 尽管Gandy认为Newman的上述言论有“误导性” ，但这一观点并不为所有人所认同。图灵一生都对机器有着浓厚的兴趣: “阿兰（图灵）从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械的'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的定义: − − 上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的"。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。 - 图灵(1939)在The Undecidable一书中，第160页。 − − 当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器”（Hodges p.318）。关于被Kleene（1952年）命名为 “图灵论文 ”的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中"On Computable Numbers, with an Application to the Entscheidungsproblem"。 − − − + − + 第748行：
第534行： − + − {{divcol|colwidth=22em}}+ − − − − * [[算术层次结构]] − − * [[Bekenstein bound]], showing the impossibility of infinite-tape Turing machines of finite size and bounded energy − − * [[贝肯斯坦约束]]，表明不可能出现有限大小和有限能量的无限带图灵机。 − − * [[BlooP and FlooP]] − * [[BlooP 和 FlooP]]（这是两种编程语言） − − * [[Busy beaver]] − * [[繁忙的海狸]] − − * [[Chaitin constant]] or [[Omega (computer science)]] for information relating to the halting problem − + − + − * [[中文房间]] − + − + − + − + − + − + − + − * [[枚举器（理论计算机科学）]] − * [[Genetix]] + − + − + − + − * [[停机问题]] − + − * [[哈佛结构]] − + − * [[命令式编程]] − + − * [[朗顿蚂蚁]]和[[Turmite]]，图灵机的二维模型 − + − * [[修正后的哈佛结构]] − + − * [[概率图灵机]] − + − * [[随机存取图灵机]] − + − * [[量子图灵机]] − + − + − + − * [[图灵机实例]] − + − * [[调协开关]] − + − * [[图灵图谱]]，任何计算系统或语言，尽管是图灵完备的，但通常被认为对实际计算无用。 − − − * [[Unorganized machine]], for Turing's very early ideas on neural networks − * [[无组织的机器]]，图灵关于神经网络的早期想法 − − * [[Von Neumann architecture]] − * [[冯-诺依曼结构]] − − − − {{divcol-end}} − − ==Notes== + − + − − − + + − + − ===Primary literature, reprints, and compilations=== − − − − * [[Martin Davis (mathematician)|Martin Davis]] (ed.) (1965), ''The Undecidable'', Raven Press, Hewlett, NY. − + 第867行：
第606行： − + − − − − ===Computability theory=== + − + − + 第907行：
第643行： − + − − − − + − − − 第941行：
第671行： − + − − − 第971行：
第698行： + + − + − ==External links== − − {{Commons category|Turing machines}} − − * {{springer|title=Turing machine|id=p/t094460}} − − * [http://plato.stanford.edu/entries/turing-machine/ Turing Machine] in the [[Stanford Encyclopedia of Philosophy]] − − − − Category:1936 in computing − − * {{curlie|Computers/Computer_Science/Theoretical/Automata_Theory/Turing_Machines|Turing Machines}} − − Category:1937 in computing − − − − Category:Educational abstract machines − − − − Category:Theoretical computer science − {{Formal languages and grammars}}+ − − Category:Alan Turing − − 分类: 阿兰 · 图灵 − − − − Category:Models of computation − − {{Authority control}} − − Category:Formal methods − − − − Category:Computability theory − − {{DEFAULTSORT:Turing machine}} − − Category:English inventions − − [[Category:Turing machine| ]] − − Category:Automata (computation) − − [[Category:1936 in computing]] − − Category:Formal languages − − [[Category:1937 in computing]] − − Category:Abstract machines − − <noinclude> − − <small>This page was moved from [[wikipedia:en:Turing machine]]. Its edit history can be viewed at [[图灵机/edithistory]]</small></noinclude> − − [[Category:待整理页面]] − −
无编辑摘要
因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。
因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。
[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]
[[[文件:图灵机.jpg|缩略图| right| 图灵机的理想模型]]]
图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器 （Random-access memory）。
图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器 （Random-access memory）。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-tuple models):
* 一个有限的指令表<ref>Occasionally called an ''action table'' or ''transition function''.</ref><ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref>，给定机器当前所处的状态(q<sub>i</sub>)和它在纸带上读取的符号(a<sub>j</sub>)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：
# 擦除或写入一个符号（将a<sub>j</sub>替换为a<sub>j1</sub>）。
# 擦除或写入一个符号（将a<sub>j</sub>替换为a<sub>j1</sub>）。
# 移动读写头（由d<sub>k</sub>描述，如果值为'L'表示向左移动一步，'R'表示向右移动一步，'N'表示停留在原地）。
# 移动读写头（由d<sub>k</sub>描述，如果值为'L'表示向左移动一步，'R'表示向右移动一步，'N'表示停留在原地）。
# 假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
# 假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
一个相对不常见的变体允许“无移位”，比如 N，作为方向集的第三个元素{L, R}。
一个相对不常见的变体允许“无移位”，比如 N，作为方向集的第三个元素{L, R}。
三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
* F={HALT}（最终状态）；
* F={HALT}（最终状态）；
* δ=参见下面的状态表（转换函数）。
* δ=参见下面的状态表（转换函数）。
空白的时候，所有的纸带单元格都用0标记。
空白的时候，所有的纸带单元格都用0标记。
==可视化或实现图灵机所需的其他细节==
==可视化或实现图灵机所需的其他细节==
用Van Emde Boas (1990)的话来说: “集合论对象(类似于上面的七元组描述形式)只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”
用Van Emde Boas（1990）的话来说: “集合论对象（类似于上面的七元组描述形式）只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”
例如，
例如，
* 符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无穷尽地读写符号。
* 符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无穷尽地读写符号。
===其他定义===
===其他定义===
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。
最常见的规则是根据图灵/戴维斯的规则，在“图灵表”钟永9个5元组中的一个表示每个“图灵指令”（图灵1936年在《The Undecidable》p.126-127）：
最常见的规则是根据图灵/戴维斯的规则，在“图灵表”钟永9个5元组中的一个表示每个“图灵指令”（图灵1936年在《The Undecidable》p.126-127）：
（定义1） ：（(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)）
（定义1） ：（(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)）
其中q<sub>i</sub>,是当前状态，S<sub>j</sub>是已扫描符号，S<sub>k</sub>是打印符号，E是擦除，N是无状态，L是向左移动，R是向右，q<sub>m</sub> 是新状态。
其中q<sub>i</sub>,是当前状态，S<sub>j</sub>是已扫描符号，S<sub>k</sub>是打印符号，E是擦除，N是无状态，L是向左移动，R是向右，q<sub>m</sub> 是新状态。
其他作者(Minsky，Hopcroft和Ullman，Stone采用了另一种规定，在扫描符号S<sub>j</sub>之后立即列出新状态q<sub>m</sub>:
其他作者(Minsky，Hopcroft和Ullman，Stone采用了另一种规定，在扫描符号S<sub>j</sub>之后立即列出新状态q<sub>m</sub>:
(定义2): (q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)
(定义2): (q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)
（当前状态 q<sub>i</sub> , 扫描符号 S<sub>j</sub> , 新状态 q<sub>m</sub> , 打印 S<sub>k</sub>/擦除 E/none N , L/right R/none N）
其中q<sub>i</sub>,是当前状态，S<sub>j</sub>是已扫描符号，S<sub>k</sub>是打印符号，E是擦除，N是无状态，L是向左移动，R是向右，q<sub>m</sub> 是新状态。
其中q<sub>i</sub>,是当前状态，S<sub>j</sub>是已扫描符号，S<sub>k</sub>是打印符号，E是擦除，N是无状态，L是向左移动，R是向右，q<sub>m</sub> 是新状态。
文的其余部分将使用“定义1”(图灵/戴维斯规则)。
例子: 将3状态2符号“繁忙的海狸”简化为5元组
例子: 将3状态2符号“繁忙的海狸”简化为5元组
| ('''C''', 1, 1, N, '''H''')
| ('''C''', 1, 1, N, '''H''')
|}
|}
在下表中，图灵的原始模型只允许前三行，他称之为N1, N2, N3(参见图灵书籍《The Undecidable》p.126）。他允许通过命名第0个S<sub>0</sub>="E"或"N"，即“擦除”或者“空白”等。但是，他不允许“不打印”，所以每个指令行都包括“打印符号S<sub>k</sub>”或者“擦除E”。这些缩写是图灵在1936-1937年的原始论文之后，机器模型已经允许所有九种可能的五元组类型。
在下表中，图灵的原始模型只允许前三行，他称之为N1, N2, N3(参见图灵书籍《The Undecidable》p.126）。他允许通过命名第0个S<sub>0</sub>="E"或"N"，即“擦除”或者“空白”等。但是，他不允许“不打印”，所以每个指令行都包括“打印符号S<sub>k</sub>”或者“擦除E”。这些缩写是图灵在1936-1937年的原始论文之后，机器模型已经允许所有九种可能的五元组类型。
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
|}
|}
任何图灵表（指令列表）都可以由上述九个5元组构成。由于技术原因，三个非打印或 "N "指令（4、5、6）通常可以省去。
任何图灵表（指令列表）都可以由上述九个5元组构成。由于技术原因，三个非打印或 "N "指令（4、5、6）通常可以省去。
较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；
较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；
===状态===
===状态===
图灵机上下文中使用的“状态”一词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数研究者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵 (1936) 在他所谓的机器“m-配置”的记录和机器（或人）通过计算的“进展状态”——整个系统的当前状态——之间做出了强有力的区分。图灵所说的“状态公式”包括当前指令和纸带上的所有符号：
图灵机上下文中使用的“状态”一词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数研究者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵 (1936) 在他所谓的机器“m-配置”的记录和机器（或人）通过计算的“进展状态”——整个系统的当前状态——之间做出了强有力的区分。图灵所说的“状态公式”包括当前指令和纸带上的所有符号：
因此，任何阶段的计算进度状态完全由指令注释和纸带上的符号决定。也就是说，系统的状态可以由单个表达式（符号序列）来描述，该表达式由纸带上的符号后跟 Δ（我们假设不会出现在其他地方）和指令注释组成。这个表达式被称为“状态公式”。——《The Undecidable》,图灵，p.139–140
因此，任何阶段的计算进度状态完全由指令注释和纸带上的符号决定。也就是说，系统的状态可以由单个表达式（符号序列）来描述，该表达式由纸带上的符号后跟 Δ（我们假设不会出现在其他地方）和指令注释组成。这个表达式被称为“状态公式”。
更早时期，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-配置 "的符号（指令的标签）和纸带上的所有符号一起放在扫描的方块下面（《The Undecidable》，第121页）；他把这个称为"完整的配置"（《The Undecidable》，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。
更早时期，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-配置 "的符号（指令的标签）和纸带上的所有符号一起放在扫描的方块下面（《The Undecidable》，第121页）；他把这个称为"完整的配置"（《The Undecidable》，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。
在Kleene（1952）中可以看到这样的一个变体，Kleene展示了如何写出一台机器的 "状态"的哥德尔数：他把 "m-配置 "符号q<sub>4</sub>放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-纸带图)，并把它放在扫描方格的右边。但Kleene把 "q<sub>4</sub> "本身称为 "机器状态"（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为 "瞬时描述"，并遵循图灵规定，把 "当前状态"（指令标签，m-配置）放在扫描符号的左边（第149页）。
示例：3次“移动”后，三态2符号繁忙的海狸的总状态（取自下图中的示例“运行”）：
示例：3次“移动”后，三态2符号繁忙的海狸的总状态（取自下图中的示例“运行”）：
:: 1'''A'''1
:: 1'''A'''1
这意味着：经过三次移动后，纸带上有......000110000......，读写头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；纸带上有一个 "1"，但读写头正在扫描它左边的 "0"（"空白"），状态是B。
这意味着：经过三次移动后，纸带上有......000110000......，读写头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；纸带上有一个 "1"，但读写头正在扫描它左边的 "0"（"空白"），状态是B。
图灵机情况中，应阐明 "状态 "是哪种状态。(i)当前指令，或(ii)纸带上的符号列表连同当前指令，或(iii)纸带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。
图灵机情况中，应阐明 "状态 "是哪种状态。(i)当前指令，或(ii)纸带上的符号列表连同当前指令，或(iii)纸带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。
图灵的传记作者Andrew Hodges (1983:107)注意到并讨论了这种混淆。
图灵的传记作者Andrew Hodges (1983:107)注意到并讨论了这种混淆。
===图灵机的状态图===
===图灵机的状态图===
{|class="wikitable"
{|class="wikitable"
|+
|+
|}
|}
“三态繁忙的海狸”图灵机的有限状态表示。每个圆圈代表表的一个“状态”——一个“m-配置”或“指令”。状态转换的"方向"用箭头表示。出状态附近的标签（如0/P,R）（在箭头的“尾部”）指定了引起特定转换的扫描符号（如0），后面是斜线/，接着是机器的后续“行为”，如“P打印”然后移动纸带“R向右”。没有普遍接受的格式存在。所显示的规则是以McClusky（1965）、Booth（1967）、Hill和Peterson（1974）为蓝本。
右边：上面的表格表示为“状态转换”图。
通常大的表格最好是留作表格（Booth，p.74）。它们更容易由计算机以表格形式模拟出来（Booth，p.74）。然而，某些概念，例如具有“复位”状态的机器和具有重复模式的机器（参见Hill和Peterson p.244）在被视为图纸时更容易被看到。
通常大的表格最好是留作表格（Booth，p.74）。它们更容易由计算机以表格形式模拟出来（Booth，p.74）。然而，某些概念，例如具有 "复位 "状态的机器和具有重复模式的机器（参见Hill和Peterson p. 244）在被视为图纸时更容易被看到。
图纸是否代表了对其表的改进，必须由读者针对特定的情况来决定。详见有限状态机。
图纸是否代表了对其表的改进，必须由读者针对特定的情况来决定。详见有限状态机。
繁忙的海狸的计算进化从顶部开始，一直到底部。
繁忙的海狸的计算进化从顶部开始，一直到底部。
再次提醒读者，这种图表示的是在时间上冻结的表的快照，而不是计算在时间和空间上的过程(“轨迹”)。虽然繁忙的海狸的机器每次“运行”都会遵循相同的状态轨迹，但对于可以为变量输入“参数”提供信息的“复制”机器而言，情况并非如此。
再次提醒读者，这种图表示的是在时间上冻结的表的快照，而不是计算在时间和空间上的过程("轨迹")。虽然繁忙的海狸的机器每次 "运行 "都会遵循相同的状态轨迹，但对于可以为变量输入“参数”提供信息的“复制”机器而言，情况并非如此。
“计算进度 "图显示了三态繁忙的海狸从开始到结束的计算过程中的“状态”（指令）进度。最右边是每一步的图灵“完整配置”。如果机器停止并清空“状态寄存器”和整个纸带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。
“计算进度 "图显示了三态繁忙的海狸从开始到结束的计算过程中的 "状态"（指令）进度。最右边是每一步的图灵 "完整配置"。如果机器停止并清空 "状态寄存器 "和整个纸带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。
==图灵机的等价模型==
==图灵机的等价模型==
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力（Hopcroft和Ullman p.159, cf. Minsky(1967)）。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能计算更多的数学函数。（邱奇-图灵理论假设这对任何机器都是正确的：任何可以被“计算”的东西都可以被某些图灵机器计算。）
图灵机相当于单堆栈下推自动机（Pushdown Automaton，PDA），它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对读写头左侧的纸带进行建模，使用另一个堆栈对读写头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈PDA。
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机（Deterministic Turing Machine，DTM）和非确定型图灵机（non-Deterministic Turing Machine , NDTM）(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。
只读、右移动的图灵机相当于 DFAs（以及通过使用 NDFA 到 DFA 转换算法转换的 NFA）。
对于实际的和教学的意图，等价的 寄存器机器可以作为通常的汇编编程语言使用。
对于实际的和教学的意图，等价的 寄存器机器可以作为通常的汇编编程语言使用。
一个有趣的问题是：用具体编程语言表示的计算模型是否是图灵等价的？虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人在2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，ANSI C并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如Pascal，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。
一个有趣的问题是：用具体编程语言表示的计算模型是否是图灵等价的？虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人在2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，ANSI C并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如Pascal，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。
==选择C型机器、Oracle的O型机器==
==选择C型机器、Oracle的O型机器==
早在1936年的论文中，图灵就对“运动......完全由配置决定”的“自动机”和“选择机”进行了区分：
它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况。——The Undecidable，p.118
图灵(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”
图灵(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”
这通过这种技术，一个确定型的（比如，a-）图灵机可以用来模拟一个非确定型的图灵机的行为; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
Oracle机或o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”——一个未指定的实体（不是一台机器）“的决定(The undecutable，p.166-168)。
Oracle机或o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”——一个未指定的实体（不是一台机器）“的决定（The undecutable，p.166-168）。
==通用图灵机==
==通用图灵机==
图灵机的实现
图灵机的实现
正如图灵在《The Undecidable》一书中所写，第128页：
我们可以发明一种机器，用来计算任何可计算序列。如果向机器U提供纸带，纸带的开头写着计算机M用分号隔开的五元数组，那么机器U将计算出与机器M相同的序列。
虽然这一发现现在被认为是很常见的，但在当时（1936年），很多人认为这是不可思议的。图灵称之为“通用机器”（缩写为“U”）的计算模型被一些人（参见Davis(2000)）认为是产生存储程序计算机概念的基础理论的突破。
实质上包含了现代计算机的发明以及伴随着它的一些编程技术。——Minsky（1967），P.104
就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数倍。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
==与实际机器的比较==
==与实际机器的比较==
使用乐高积木实现的图灵机（Lego pieces）
人们常说，图灵机不同于简单的自动机，它和实际的机器一样强大，能够执行真实程序所能执行的任何操作。在这种说法中被忽略的是，由于实际的机器只能有有限的配置，所以这里的“真正的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
人们常说，图灵机不同于简单的自动机，它和实际的机器一样强大，能够执行真实程序所能执行的任何操作。在这种说法中被忽略的是，由于实际的机器只能有有限的配置，所以这里的“真正的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
有很多方法可以解释为什么图灵机是实际计算机的有用模型:
有很多方法可以解释为什么图灵机是实际计算机的有用模型:
# 凡是真正的计算机能计算的东西，图灵机也能计算。例如，“图灵机可以模拟编程语言中的任何类型的子程序，包括递归程序和任何已知的参数传递机制”（Hopcroft and Ullman 第157页）。一个足够大的FSA也可以模拟任何真正的计算机，而不用考虑IO。因此，关于图灵机的局限性的说法也将适用于实际计算机。
# 凡是真正的计算机能计算的东西，图灵机也能计算。例如，"图灵机可以模拟编程语言中的任何类型的子程序，包括递归程序和任何已知的参数传递机制"(Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真正的计算机，而不用考虑IO。因此，关于图灵机的局限性的说法也将适用于实际计算机。
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用，因为它们有任意精度的数据类型可用，而且永远不必处理意外情况（包括但不限于内存耗尽）。
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用，因为它们有任意精度的数据类型可用，而且永远不必处理意外情况（包括但不限于内存耗尽）。
===图灵机的局限性===
===图灵机的局限性===
====计算复杂性理论====
====计算复杂性理论====
图灵机的一个局限性在于，其不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP机器模型。与通用图灵机一样，RASP将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同的是，RASP具有无限数量可区分的、有编号但无限制的“寄存器”——可以包含任何整数的内存“单元”（参见Elgot和Robinson(1964)，Hartmanis(1971)，特别是Cook-Rechow(1973)）；RASP的有限状态机可以间接寻址（例如，一个寄存器的内容可以用作另一个寄存器的地址），因此当图灵机被用作约束运行时间的基础时，可以证明某些算法的运行时间有一个“假下限”（由于图灵机的假简化假设）。这方面的一个例子是二进制搜索，当使用RASP计算模型而不是图灵机模型时，可以证明这种算法的运行速度更快。
图灵机的一个局限性在于，其不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP机器模型。与通用图灵机一样，RASP将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同的是，RASP具有无限数量可区分的、有编号但无限制的“寄存器”ー可以包含任何整数的内存 "单元"(参见Elgot和Robinson(1964)，Hartmanis(1971)，特别是Cook-Rechow(1973)；) RASP的有限状态机可以间接寻址(例如，一个寄存器的内容可以用作另一个寄存器的地址) ，因此当图灵机被用作约束运行时间的基础时，可以证明某些算法的运行时间有一个 "假下限"（由于图灵机的假简化假设）。这方面的一个例子是二进制搜索，当使用RASP计算模型而不是图灵机模型时，可以证明这种算法的运行速度更快。
====并发性====
====并发性====
图灵机的另一个局限是，其不能很好地模拟并发。例如，一个始终保持非确定性的图灵机在空白纸带上开始计算的整数大小是有限制的。相比之下，有一些没有输入的始终保持一致的并发系统，可以计算出无界大小的整数。(可以用本地存储创建一个初始化为0的进程，它同时向自己发送一个“停止”和一个“运行”的消息。当它收到一个“运行”信息时，它的计数增加1，并向自己发送一个去信息。当它收到一个“停止”消息时，它就停止，在它的本地存储区有一个无限制的数字）。
图灵机的另一个局限是，其不能很好地模拟并发。例如，一个始终保持非确定性的图灵机在空白纸带上开始计算的整数大小是有限制的。相比之下，有一些没有输入的始终保持一致的并发系统，可以计算出无界大小的整数。(可以用本地存储创建一个初始化为0的进程，它同时向自己发送一个“停止”和一个“运行”的消息。当它收到一个“运行”信息时，它的计数增加1，并向自己发送一个去信息。当它收到一个“停止”消息时，它就停止，在它的本地存储区有一个无限制的数字)。
====交互====
====交互====
在计算机的早期，计算机的使用通常仅限于批处理，即非交互式任务，每个任务从给定的输入数据中产生输出数据。可计算性理论研究从输入到输出的函数的可计算性，图灵机就是为此而发明的，其反映了这种做法。
在计算机的早期，计算机的使用通常仅限于批处理，即非交互式任务，每个任务从给定的输入数据中产生输出数据。可计算性理论研究从输入到输出的函数的可计算性，图灵机就是为此而发明的，其反映了这种做法。
自20世纪70年代以来，计算机的交互式使用变得更加普遍。原则上，可以通过让外部代理与图灵机同时从纸带中读出并写入纸带的方式进行建模，但这很少与交互的实际发生方式相吻合；因此，在描述交互性时，通常首选I/O自动机等替代程序。
自20世纪70年代以来，计算机的交互式使用变得更加普遍。原则上，可以通过让外部代理与图灵机同时从纸带中读出并写入纸带的方式进行建模，但这很少与交互的实际发生方式相吻合；因此，在描述交互性时，通常首选I/O自动机等替代程序。
===历史背景：计算机器===
===历史背景：计算机器===
罗宾•甘迪（Robin Gandy，1919-1995）是图灵（1912-1954）的学生，也是他一生的朋友，他将“计算机器”这一概念的渊源追溯到查尔斯•巴贝奇（Charles Babbage）（大约1834年），并提出了“巴贝奇论”：
整个发展和分析的操作现在都可以由机器来执行。（italics in Babbage as cited by Gandy, p.54）
罗宾•甘迪（Robin Gandy，1919-1995)是图灵(1912-1954)的学生，也是他一生的朋友，他将“计算机器”这一概念的渊源追溯到查尔斯•巴贝奇（Charles Babbage） (大约1834年) ，并提出了“ 巴贝奇论” :
甘迪对巴贝奇分析机的分析描述了以下五种操作:
甘迪对巴贝奇分析机的分析描述了以下五种操作:
# 算术函数+，-，×，其中“-”表示“适当的”减法，即满足某种条件，比如y≥x，x-y=0。
# 算术函数 +, -，×，其中“-”表示“适当的”减法，即满足某种条件，比如y≥x，x-y=0。
# 任何运算序列都是一个运算。
# 任何运算序列都是一个运算。
# 操作的迭代(重复n次操作p)。
# 操作的迭代（重复n次操作p）。
# 条件迭代(以测试t的“成功”为条件重复n次操作p)。
# 条件迭代（以测试t的“成功”为条件重复n次操作p）。
# 条件转移(即有条件的“goto”)。
# 条件转移（即有条件的“goto”）。
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p.53)。他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特（Percy Ludgate， 1909年）、莱昂纳多·托雷斯·奎维多（Leonardo Torres y Quevedo，1914年）、莫里斯·d’奥卡涅（Maurice d'Ocagne，1922年）、路易斯·库夫尼纳尔（Louis Couffignal，1933年）、万尼瓦尔·布什V（annevar Bush，1936年）、霍华德·艾肯（Howard Aiken，1937年）。然而:
重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认……——Gandy，第55页
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特（Percy Ludgate， 1909年)、莱昂纳多 · 托雷斯 · 奎维多（Leonardo Torres y Quevedo，1914年)、莫里斯 · d’奥卡涅（Maurice d'Ocagne，1922年)、路易斯 · 库夫尼纳尔（Louis Couffignal，1933年)、万尼瓦尔 · 布什V（annevar Bush，1936年)、霍华德 · 艾肯（Howard Aiken，1937年)。然而:
===判定问题: 希尔伯特1900年提出的第10号问题===
===判定问题: 希尔伯特1900年提出的第10号问题===
关于著名数学家大卫·希尔伯特（David Hilbert）在1900年提出的希尔伯特问题中，第10号问题的一个方面浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下：
10. Diophantine方程的可解性的确定。给出一个具有任意数量的未知量和有理积分系数的Diophantine方程。设计一个过程，根据这个过程可以在有限的操作中确定该方程是否可以用有理整数来解。当我们知道一个程序，允许任何给定的逻辑表达式通过有限的多次操作来决定其有效性或可满足性时，判定问题（一阶逻辑的决定问题）就解决了……判定问题必须被认为是数理逻辑的主要问题。——2008年，德尔肖维茨（Dershowitz）和古列维奇（Gurevich）引用了此译文和德文原文
到了1922年，“判定问题”的概念有了进一步的发展，Behmann指出：
到了1922年，“判定问题”的概念有了进一步的发展，Behmann指出：
判定问题的一般形式如下:需要一个相当明确的、普遍适用的处方，它将允许人们在有限的步骤中决定一个给定的纯逻辑论断的真假……——Gandy，第57页，引用Behmann的话
Behmann指出：一般问题相当于决定哪些数学命题是真的问题。如果能够解决判定问题，那么人们就会有一个“解决许多（甚至所有）数学问题的程序”。
1928年的国际数学家大会，希尔伯特把他的问题描述的非常的细致。第一，数学是完整的吗？第二，数学是一致的吗？第三，数学是可判定的吗？”1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特·哥德尔（Kurt Gödel）回答了前两个问题；而第三个问题（判定问题）不得不等到上世纪30年代中期。
问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇（Alonzo Church）将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特（Emil Post）拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生斯蒂芬·克莱恩（Stephen Kleene）和（j.B. Rosser）利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文（发表于1936年4月15日）表明，判定问题确实是“无法决策的”，比图灵早了将近一年（图灵的论文1936年5月28日提交，1937年1月发表）。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。
但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。……图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页
波斯特只是提出了一个可计算性的定义，并批评了邱奇的“定义”，但没有证明任何事情。
===阿兰图灵的机器===
===阿兰图灵的机器===
1935年春天，图灵作为英国剑桥大学国王学院的一名年轻硕士生，接受了这个挑战；他受到逻辑学家纽曼（Newman）的讲座的鼓舞，并从他们那里了解了哥德尔的工作和判定问题。在图灵1955年的讣告中，纽曼写道:
1935年春天，图灵作为英国剑桥大学国王学院的一名年轻硕士生，接受了这个挑战；他受到逻辑学家纽曼（Newman）的讲座的鼓舞，并从他们那里了解了哥德尔的工作和判定问题。在图灵1955年的讣告中，纽曼写道:
对于“什么是'机械'过程”？图灵回答了一个特有的答案“可以由机器完成的事情”，接着他开始着手分析计算机的一般概念。——Gandy，第74页
Gandy表示：
我想，但我不知道，图灵从他工作的一开始，就把证明判定问题的不可解性作为他的目标。1935年夏天，他告诉我，当他躺在格兰切斯特草地的时候，他完成了这篇论文的构想。这个“构想”可能是他对计算的分析，也可能是他意识到有一个普遍的机器，因此有一个对角线论证来证明不可解性。——同上，第76页
尽管Gandy认为Newman的上述言论有“误导性”，但这一观点并不为所有人所认同。图灵一生都对机器有着浓厚的兴趣：“阿兰（图灵）从小就梦想发明打字机；（他的母亲）图灵夫人有一台打字机；他很可能一开始就问自己，把打字机称为‘机械的’是什么意思”（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为“基于序数的逻辑系统”，包含了“可计算函数”的定义：
上面说过，“如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的”。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。——图灵（1939）在《The Undecidable》一书中，第160页
当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器”（Hodges p.318）。关于被Kleene（1952年）命名为 “图灵论文”的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中“On Computable Numbers, with an Application to the Entscheidungsproblem”。
希尔伯特-判定问题不可能有解……因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。——摘自图灵的论文，详见《The Undecidable》，第145页
希尔伯特-判定问题不可能有解……因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。——摘自图灵的论文，详见《The Undecidable》，第145页。
图灵的例子（他的第二个证明）：如果有人要求用一般程序来告诉我们：“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。
图灵的例子（他的第二个证明）：如果有人要求用一般程序来告诉我们：“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。
===1937–1970“数字计算机”“计算机科学 ”的诞生===
===1937-1970“数字计算机”“计算机科学”的诞生===
1937年，图灵在普林斯顿大学写博士论文时，从零开始建立了一个数字（布尔逻辑）乘法器，自制了机电继电器（Hodges p.138）。“艾伦的任务是将图灵机的逻辑设计体现在一个由继电器操作的开关网络中……”（Hodges p.138）。德国（Konrad Zuse，1938年）和美国（Howard Aiken，1937年）都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。在20世纪50年代初至中期，Hao Wang和Marvin Minsky将图灵机简化为一种更简单的形式（它是 Martin Davis的后图灵机的前身）；与此同时，欧洲研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代后期和60年代初期，Melzak和Lambek（1961）、Minsky（1961）和Shepherdson and Sturgis（1961）等人不约而同地展开进一步的研究，推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器;；Elgot和Robinson（1964）、 Hartmanis（1971）、Cook 和 Reckhow（1973）将这项工作进一步推进到寄存器和随机存取机器模型——但基本上所有这些都只是带有类似算术指令集的多带图灵机。
1937年，图灵在普林斯顿大学写博士论文时，从零开始建立了一个数字（布尔逻辑）乘法器，自制了机电继电器（Hodges p.138）。“艾伦的任务是将图灵机的逻辑设计体现在一个由继电器操作的开关网络中……”（Hodges p.138）。德国（Konrad Zuse，1938年）和美国（Howard Aiken，1937年）都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。在20世纪50年代初至中期，Hao Wang和Marvin Minsky将图灵机简化为一种更简单的形式（它是 Martin Davis的后图灵机的前身）；与此同时，欧洲研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代后期和60年代初期，Melzak和Lambek（1961）、Minsky（1961）和Shepherdson and Sturgis（1961）等人不约而同地展开进一步的研究，推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器；Elgot和Robinson（1964）、 Hartmanis（1971）、Cook 和 Reckhow（1973）将这项工作进一步推进到寄存器和随机存取机器模型——但基本上所有这些都只是带有类似算术指令集的多带图灵机。
===1970年至今：作为计算模型的图灵机===
===1970年至今：作为计算模型的图灵机===
只有在算法分析的相关领域，这个角色才能被RAM模型所取代。——van Emde Boas 1990:4
只有在算法分析的相关领域，这个角色才能被RAM模型所取代。——van Emde Boas 1990:4
==See also==
==另参见==
* 算术层次结构
* [[Arithmetical hierarchy]]
* [[Chaitin常数]]或[[Omega(计算机科学)]]以获取有关停止问题的信息。
* 贝肯斯坦约束，表明不可能出现有限大小和有限能量的无限带图灵机。
* [[Chinese Room]]
* BlooP 和 FlooP（这是两种编程语言）
* [[Conway's Game of Life]], a Turing-complete cellular automaton
* 繁忙的海狸
* [[康威生命游戏]]，一个图灵完备的细胞自动机
* Chaitin常数或Omega（计算机科学）以获取有关停止问题的信息。
* [[Digital infinity]]
* 中文房间
* [[数字无限]]
* 康威生命游戏，一个图灵完备的细胞自动机
* [[The Emperor's New Mind]]
* 数字无限
* [[皇帝的新脑]]
* 皇帝的新脑
* [[Enumerator (in theoretical computer science)]]
* 枚举器（理论计算机科学）
* 遗传
* ''[[Gödel, Escher, Bach: An Eternal Golden Braid]]'', a famous book that discusses, among other topics, the Church–Turing thesis
* 哥德尔、艾舍尔、巴赫——集异璧之大成，这是一本讨论邱奇-图灵论等话题的名著。
* [[哥德尔、艾舍尔、巴赫——集异璧之大成]]，这是一本讨论邱奇-图灵论等话题的名著。
* 停机问题
* [[Halting problem]]
* 哈佛结构
* [[Harvard architecture]]
* 命令式编程
* [[Imperative programming]]
* 朗顿蚂蚁和白蚁，图灵机的二维模型
* [[Langton's ant]] and [[Turmite]]s, simple two-dimensional analogues of the Turing machine
* 修正后的哈佛结构
* [[Modified Harvard architecture]]
* 概率图灵机
* [[Probabilistic Turing machine]]
* 随机存取图灵机
* [[Random-access Turing machine]]
* 量子图灵机
* [[Quantum Turing machine]]
* 香农，另一位信息理论的领军科学家
* [[Claude Shannon]], another leading thinker in information theory
* 图灵机实例
* [[香农]]，另一位信息理论的领军科学家
* 调协开关
* [[Turing machine examples]]
* 图灵图谱，任何计算系统或语言，尽管是图灵完备的，但通常被认为对实际计算无用。
* [[Turing switch]]
* 无组织的机器，图灵关于神经网络的早期想法
* [[Turing tarpit]], any computing system or language that, despite being Turing complete, is generally considered useless for practical computing
* 冯-诺依曼结构
==笔记==
<references responsive="0" />
<references responsive="0" />
==参考文献==
==References==
{{Reflist}}
{{Reflist}}
===原始文献、重印和汇编===
* B. Jack Copeland (ed.)(2004), ''The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,'' Clarendon Press (Oxford University Press), Oxford UK. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' ''Corrections to Turing's Universal Computing Machine''
* Martin Davis (mathematician)|Martin Davis (ed.) (1965), ''The Undecidable'', Raven Press, Hewlett, NY.
* B. [[Jack Copeland]] ed. (2004), ''The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,'' Clarendon Press (Oxford University Press), Oxford UK, {{isbn|0-19-825079-7}}. Contains the Turing papers plus a draft letter to [[Emil Post]] re his criticism of "Turing's convention", and Donald W. Davies' ''Corrections to Turing's Universal Computing Machine''
* Emil Post (1936), "Finite Combinatory Processes—Formulation 1", ''Journal of Symbolic Logic'', 1, 103–105, 1936. Reprinted in ''The Undecidable'', pp. 289ff.
* Emil Post (1936), "Finite Combinatory Processes—Formulation 1", ''Journal of Symbolic Logic'', 1, 103–105, 1936. Reprinted in ''The Undecidable'', pp. 289ff.
* Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", ''Journal of Symbolic Logic'', vol. 12, pp. 1–11. Reprinted in ''The Undecidable'', pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on [[Turing's proof|Turing's first and second proofs]].
* Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", ''Journal of Symbolic Logic'', vol. 12, pp. 1–11. Reprinted in ''The Undecidable'', pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's proof|Turing's first and second proofs.
* {{Cite journal | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi= 10.1112/plms/s2-42.1.230 }} (and {{Cite journal | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 | issue = 6 }}). Reprinted in many collections, e.g. in ''The Undecidable'', pp. 115–154; available on the web in many places.
* {{Cite journal | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi= 10.1112/plms/s2-42.1.230 }} (and {{Cite journal | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 | issue = 6 }}). Reprinted in many collections, e.g. in ''The Undecidable'', pp. 115–154; available on the web in many places.
* Alan Turing, 1948, "Intelligent Machinery." Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson. Baltimore: University Park Press, 1968. p. 31. Reprinted in {{Cite journal | doi = 10.1093/philmat/4.3.256| title = Intelligent Machinery, A Heretical Theory| journal = Philosophia Mathematica| volume = 4| issue = 3| pages = 256–260| year = 1996| last1 = Turing | first1 = A. M.}}
* Alan Turing, 1948, "Intelligent Machinery." Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson. Baltimore: University Park Press, 1968. p. 31. Reprinted in {{Cite journal | doi = 10.1093/philmat/4.3.256| title = Intelligent Machinery, A Heretical Theory| journal = Philosophia Mathematica| volume = 4| issue = 3| pages = 256–260| year = 1996| last1 = Turing | first1 = A. M.}}
* F. C. Hennie and [[R. E. Stearns]]. ''Two-tape simulation of multitape Turing machines''. [[JACM]], 13(4):533–546, 1966.
* F. C. Hennie and R. E. Stearns. ''Two-tape simulation of multitape Turing machines''. JACM, 13(4):533–546, 1966.
===可计算性理论===
* {{cite book | last = Boolos | first = George |author2=Richard Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool_r8y9 | url-access = registration | edition = 3rd | publisher = Cambridge University Press | location = Cambridge UK | origyear = 1989| year = 1999| isbn = 0-521-20402-X }}
* {{cite book | last = Boolos | first = George |author2=Richard Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool_r8y9 | url-access = registration | edition = 3rd | publisher = Cambridge University Press | location = Cambridge UK | origyear = 1989| year = 1999| isbn = 0-521-20402-X }}
* {{cite book | last = Boolos | first = George |author2=John Burgess |author3=Richard Jeffrey | title = Computability and Logic | edition = 4th | publisher = Cambridge University Press | location = Cambridge UK | year = 2002 | isbn = 0-521-00758-5 }} Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. [[Register machine]]) and [[Computable function|recursive functions]], showing their equivalence.
* {{cite book | last = Boolos | first = George |author2=John Burgess |author3=Richard Jeffrey | title = Computability and Logic | edition = 4th | publisher = Cambridge University Press | location = Cambridge UK | year = 2002 | isbn = 0-521-00758-5 }} Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. [[Register machine]]) and [[Computable function|recursive functions]], showing their equivalence.
* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX ''Turing Machines'' includes some recursion theory.
* Taylor L. Booth (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX ''Turing Machines'' includes some recursion theory.
* {{cite book|author = Martin Davis | year = 1958| title = Computability and Unsolvability| publisher = McGraw-Hill Book Company, Inc, New York | author-link = Martin Davis (mathematician)}}. On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
* {{cite book|author = Martin Davis | year = 1958| title = Computability and Unsolvability| publisher = McGraw-Hill Book Company, Inc, New York}} On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
* {{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker|author3-link=Elaine Weyuker | title = Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994 | isbn = 0-12-206382-1}}
* {{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker|author3-link=Elaine Weyuker | title = Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994 | isbn = 0-12-206382-1}}
* [[Peter van Emde Boas]] 1990, ''Machine Models and Simulations'', pp. 3–66, in [[Jan van Leeuwen]], ed., ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier, [place?], {{isbn|0-444-88071-2}} (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
* [[Peter van Emde Boas]] 1990, ''Machine Models and Simulations'', pp. 3–66, in [[Jan van Leeuwen]], ed., ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier, [place?], {{isbn|0-444-88071-2}} (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
===丘奇的论文===
===Church's thesis===
* {{cite journal |author=Nachum Dershowitz |author2=Yuri Gurevich |date=September 2008 |title=A natural axiomatization of computability and proof of Church's Thesis |journal=Bulletin of Symbolic Logic |volume=14 |issue=3 |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |accessdate=2008-10-15}}
* {{cite journal |author=Nachum Dershowitz |author2=Yuri Gurevich |date=September 2008 |title=A natural axiomatization of computability and proof of Church's Thesis |journal=Bulletin of Symbolic Logic |volume=14 |issue=3 |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |accessdate=2008-10-15}}
* {{cite book|author = Roger Penrose | origyear = 1989| year = 1990 | title = The Emperor's New Mind | publisher = Oxford University Press, New York| edition = 2nd | isbn = 0-19-851973-7| author-link = Roger Penrose}}
* {{cite book|author = Roger Penrose | origyear = 1989| year = 1990 | title = The Emperor's New Mind | publisher = Oxford University Press, New York| edition = 2nd | isbn = 0-19-851973-7| author-link = Roger Penrose}}
===小型图灵机===
===Small Turing machines===
* Rogozhin, Yurii, 1998, "[https://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm A Universal Turing Machine with 22 States and 2 Symbols]", ''Romanian Journal of Information Science and Technology'', 1(3), 259–265, 1998. (surveys known results about small universal Turing machines)
* Rogozhin, Yurii, 1998, "[https://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm A Universal Turing Machine with 22 States and 2 Symbols]", ''Romanian Journal of Information Science and Technology'', 1(3), 259–265, 1998. (surveys known results about small universal Turing machines)
* Olivier and Marc RAYNAUD, 2014, [http://www.machinedeturing.com/ang_default.asp A programmable prototype to achieve Turing machines]" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).
* Olivier and Marc RAYNAUD, 2014, [http://www.machinedeturing.com/ang_default.asp A programmable prototype to achieve Turing machines]" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).
===其他===
===Other===
* {{cite book|author = Martin Davis | year = 2000| title = Engines of Logic: Mathematicians and the origin of the Computer| publisher = W. W. Norton & Company, New York| edition = 1st | isbn = 978-0-393-32229-3| author-link = Martin Davis (mathematician)}}
* {{cite book|author = Martin Davis | year = 2000| title = Engines of Logic: Mathematicians and the origin of the Computer| publisher = W. W. Norton & Company, New York| edition = 1st | isbn = 978-0-393-32229-3| author-link = Martin Davis (mathematician)}}
* Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: [http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html "On Undecidability Results of Real Programming Languages"], In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.
* Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: [http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html "On Undecidability Results of Real Programming Languages"], In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.
==外部链接==
* [http://plato.stanford.edu/entries/turing-machine/ Turing Machine] in the Stanford Encyclopedia of Philosophy
* [http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the Wolfram Demonstrations Project.
*[http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the [[Wolfram Demonstrations Project]].
类别: 1936年
类别: 1936年
类别: 1937年
类别: 1937年
类别: 教育摘要机器
类别: 教育摘要机器
类别: 理论计算机科学
类别: 理论计算机科学
类别: 阿兰·图灵
类别: 计算模型
类别: 计算模型
类别: 正式方法
类别: 正式方法
类别: 可计算性理论
类别: 可计算性理论
类别: 英国发明
类别: 英国发明
类别: 自动机(计算)
类别: 自动机(计算)
类别: 正式语言
类别: 正式语言
类别: 抽象机器
类别: 抽象机器
此词条暂由初步翻译。
此词条暂由初步翻译。