图灵机

此词条暂由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').

图灵机的理想模型

图灵机是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.

能够模拟任何其他图灵机的图灵机称为通用图灵机。邱奇（Alonzo Church，美国著名数学家）提出了一个更面向数学的定义，具有普遍性。他将在 λ 演算的工作和图灵在正式计算机理论中的工作融合，被称为邱奇-图灵论题。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。

物理描述

In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:

...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

在1948年的论文《智能机器》中，图灵写道他的机器包括:

...以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号；它被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。

描述

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“等。在原始的文章中（“论可计算的数字，以及对可判定行的影响 On Computable Numbers, with an Application to the Entscheidungsproblem”）。图灵想象的不是一种机制，而是一种他被称之为计算机的“人”，可以严格执行这些决定性的机械规则的人。

More explicitly, a Turing machine consists of:

更切确地说，图灵机由以下部分组成:

A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.
纸带。纸带被分成多个单元，每个紧邻着。每个单元都包涵来自某个有限字母表的一个符号。字母表中包含有一个特殊的空白符号（此处写作“0”）和一个或者多个其他符号。假设纸带可以任意向左/向右扩展，所以图灵机拥有能够支撑起计算所需的纸带数量。没有写入过的单元格被假定用空白符号填充。在某些型号中，胶带的左端标有特殊符号；磁带向右侧延伸或无限延伸。

A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.
读写头。读写头可以在纸带上读写符号，并一次将纸带左右移动一个（有且仅有一个）单元格。在某些型号的机器中，读写头移动而纸带静止。

A state register that stores the state of the Turing machine, one of finitely many. Among these is the special start state with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in.
状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。

状态寄存器，存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。Turing写道，这些状态代替了执行计算的人通常会处于的 "思想状态"。

A finite table^[1] of instructions^[2] that, given the state(q_i) the machine is currently in and the symbol(a_j) 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):
一个有限的指令表，给定机器当前所处的状态(q_i)和它在纸带上读取的符号(a_j)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：

Either erase or write a symbol (replacing a_j with a_j1).
Move the head (which is described by d_k and can have values: 'L' for one step left or 'R' for one step right or 'N' for staying in the same place).
Assume the same or a new state as prescribed (go to state q_i1).

擦除或写入一个符号（将a_j替换为a_j1）。
移动读写头（由d_k描述，如果值为'L'表示向左移动一步，'R'表示向右移动一步，'N'表示停留在原地）。
假设与规定的状态相同或新的状态（进入状态q_i1）

In the 4-tuple models, erasing or writing a symbol (a_j1) and moving the head left or right (d_k) 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.

在四元组模型中，擦除或写入符号（a_j1)）和向左或向右移动读写头（d_k）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。

Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.

机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。

正式定义

Following Hopcroft & Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple where

is a finite, non-empty set of tape alphabet symbols;
is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
is a finite, non-empty set of states;
is the initial state;
is the set of final states or accepting states. The initial tape contents is said to be accepted by if it eventually halts in a state from .
is a partial function called the transition function, where L is left shift, R is right shift. If is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.

在Hopcroft & Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：

Г是有限的、非空的纸带字母符号集；
bᕮГ，是空白符号（唯一允许在计算过程中的任何步骤无限频繁地出现在纸带上的符号）；
Σ⊆Г\{b}是输入符号集，即允许出现在初始纸带内容中的符号集；
Q是有限的、非空的状态集；
q_0ᕮQ是初始状态；
F⊆Q是最终状态或接受状态的集合。初始纸带内容被认为是接受由M如果它最终停止在一个状态 F.
δ: （Q \ F) Χ Г Χ {L, R}是一个偏函数，称为转移函数，其中 L 是左移，R 是右移。如果在当前状态和当前纸带符号上未定义，则机器停止；直观地，转移函数指定了从当前状态转移的下一个状态，哪个符号覆盖读写头指向的当前符号，以及下一个读写头运动。

In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output.

此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。

A relatively uncommon variant allows "no shift", say N, as a third element of the set of directions [math]\displaystyle{ \{L,R\} }[/math].

一个相对不常见的变体允许“无移位”，比如 N，作为方向集的第三个元素{L, R}。

The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):

三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）

Q={A, B, C, HALT}(状态);
Г= {0, 1}(纸带符号);
b=0（空白符号）；
Σ={1}（输入符号）；
q_0 = A（初始状态）；
F={HALT}（最终状态）；
δ=参见下面的状态表（转换函数）。

Initially all tape cells are marked with [math]\displaystyle{ 0 }[/math].

最初，所有的纸带单元格都用0标记。

State table for 3 state, 2 symbol busy beaver
	l	磁带符号	Current state A			当前状态 A	Current state B			当前状态 B	Current state C	当前状态 C
	l
	写入符号	移动磁带	下一个状态	Write symbol	写入符号	Move tape 移动磁带	Next state 下一个状态	Write symbol	写入符号	Move tape 移动磁带	Next state 下一个状态
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	HALT	停止

Additional details required to visualize or implement Turing machines

可视化或实现图灵机所需的其他细节

In the words of van Emde Boas (1990), p. 6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like."

用范·埃姆德·博阿斯 van Emde Boas (1990)的话来说，第6页: “集合理论对象(类似于上面的形式七元组描述)只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”

For instance,

For instance, 例如，

There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely.

符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无限期地读写符号。

The shift left and shift right operations may shift the tape head across the tape, but when actually building a Turing machine it is more practical to make the tape slide back and forth under the head instead.

左移和右移操作可能会使磁头在磁带上移动，但在实际构建图灵机时，更实际的做法是让磁带在磁头下来回滑动。

The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at one or both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on. (This is, of course, not implementable in practice.) The tape cannot be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a linear bounded automaton if the tape was proportional to the input size, or finite state machine if it was strictly fixed-length.

磁带可以是有限的，并根据需要自动延伸出空白（这是最接近数学定义的），但更常见的是将其视为在一端或两端无限延伸，除了磁头所在的明确给定的有限片段外，都会被预先填充空白。(当然，这在实践中是无法实现的。)磁带的长度不能是固定的，因为那不符合给定的定义，而且会严重限制机器可以执行的计算范围，如果磁带与输入大小成正比，则为’’’ 线性有界自动机 linear bounded automaton’’’的计算范围，如果磁带是严格的固定长度，则为’’’有限状态机 finite state machine’’’的计算范围。

Alternative definitions

其他定义

Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from [math]\displaystyle{ \{L,R\} }[/math] to [math]\displaystyle{ \{L,R,N\} }[/math], where N ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power.

文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以这样的方式进行的，即所得机器具有相同的计算能力。例如，集合可以从 [math]\displaystyle{ \{L,R\} }[/math] 改为 [math]\displaystyle{ \{L,R,N\} }[/math]其中N("无 "或 "无操作")将允许机器停留在同一磁带单元上，而不需要左右移动。这不会增加机器的计算能力。

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):

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):

按照Turing/Davis（Turing（1936）在The Undecidable，第126-127页和戴维斯（2000）中的约定），最常见的约定由九个5元组之一表示“ 图灵表”中的每个“ 图灵指令” 。第152页）：

(definition 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

(definition 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

(定义1) : (q_i, S_j, S_k/E/N, L/R/N, q_m)

( current state q_i , symbol scanned S_j , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N , new state q_m )

( current state q_i , symbol scanned S_j , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N , new state q_m )

(当前状态 q_i , 已扫描符号S_j , 打印符号S_k/擦除 E/无 N , move_tape_one_square left L/right R/none N , 新状态 q_m )

Other authors (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) adopt a different convention, with new state q_m listed immediately after the scanned symbol S_j:

Other authors (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) adopt a different convention, with new state q_m listed immediately after the scanned symbol S_j:

其他作者(Minsky(1967)第119页，霍普克罗夫特Hopcroft和乌尔曼Ullman(1979)第158页，斯通Stone(1972)第9页)采用了另一种约定，在扫描符号s j 之后立即列出新状态q m :

(definition 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

(definition 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

(定义2) : (q i ，s j ，q m ，s k /E/N，L/R/N)

( current state q_i , symbol scanned S_j , new state q_m , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N )

( current state q_i , symbol scanned S_j , new state q_m , print symbol S_k/erase E/none N , move_tape_one_square left L/right R/none N )

(当前状态 q _i ，符号扫描 s j ，新状态 q m ，打印符号 s k /擦除 E/无 n，move _ tape one _ square left L/right R/none n)

For the remainder of this article "definition 1" (the Turing/Davis convention) will be used.

本文的其余部分将使用“定义1”(Turing/Davis约定)。

|+ Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples

| + 示例: 将3状态2符号穷忙的状态表减少为5元组

Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples
Current state 当前状态	Scanned symbol 扫描符号	Print symbol 打印符号	Move tape 移动磁带	Final (i.e. next) state 最终（即下一个）状态	5-tuples 5元组
A	0	1	R	B	(A, 0, 1, R, B)
A	1	1	L	C	(A, 1, 1, L, C)
B	0	1	L	A	(B, 0, 1, L, A)
B	1	1	R	B	(B, 1, 1, R, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	H	(C, 1, 1, N, H)

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₀ = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S_k" 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:

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₀ = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol S_k" 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:

在下表中，图灵最初的模型只允许前三行，他称之为 N1，N2，N3。参见图灵在The Undecidable一书中，第126页)。他通过命名第0个符号 s 0 = “ 擦除”或“ 空白”等，允许擦除“扫描方块”。但是，他不允许不打印，所以每条指令行都包括“打印符号 s k ”或“ 擦除”(参见Post（1947），The Undecidable，第300页中的脚注12 ）。这些缩写是图灵的(The Undecidable，第119页)。在图灵于1936-1937年发表原始论文之后，机器模型已经允许所有九种可能的五元组类型:

	Current m-configuration (Turing state) 当前的m配置（图灵状态）	Tape symbol 磁带符号	Print-operation 打印	Tape-motion 磁带运动	Final m-configuration (Turing state) 最终的M配置（图灵状态）	5-tuple 5元组	5-tuple comments 5元组注释	4-tuple 4元组
N1	q_i	S_j	Print(S_k)	Left L	q_m	(q_i, S_j, S_k, L, q_m)	"blank" = S₀, 1=S₁, etc.
N2	q_i	S_j	Print(S_k)	Right R	q_m	(q_i, S_j, S_k, R, q_m)	"blank" = S₀, 1=S₁, etc.
N3	q_i	S_j	Print(S_k)	None N	q_m	(q_i, S_j, S_k, N, q_m)	"blank" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	None N	Left L	q_m	(q_i, S_j, N, L, q_m)		(q_i, S_j, L, q_m)
5	q_i	S_j	None N	Right R	q_m	(q_i, S_j, N, R, q_m)		(q_i, S_j, R, q_m)
6	q_i	S_j	None N	None N	q_m	(q_i, S_j, N, N, q_m)	Direct "jump"	(q_i, S_j, N, q_m)
7	q_i	S_j	Erase	Left L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	Erase	Right R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	Erase	None N	q_m	(q_i, S_j, E, N, q_m)		(q_i, S_j, E, q_m)

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.

任何图灵表(指令列表)都可以由上面的9个5元组构成。由于技术原因，通常可以省去三个不打印或“ N”指令（4、5、6）。有关示例，请参见图灵机示例。

| S_j

| Erase

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.

较少遇到使用4元组的情况：这些代表了图灵机指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；也可参见更多的图灵机。

The "state"

“状态” 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:

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:

在图灵机的情况中使用 "状态 "一词可能会引起混淆，因为它可以有两种含义。Turing之后的大多数评论家都用 "状态 "来表示当前要执行的指令的名称/代号--即状态寄存器的内容。但Turing(1936)对他所谓的机器 "m配置 "的记录，和机器(或人)通过计算的 "进展状态"--即整个系统的当前状态--作了强烈的区分。Turing所说的 "状态公式 "既包括当前指令，也包括磁带上的所有符号。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

因此，在任何阶段，计算的进展状态完全由指令符和磁带上的符号决定。也就是说，系统的状态可以用一个单一的表达式(符号序列)来描述，这个表达式是由磁带上的符号组成的，后面是Δ(我们假定它不会出现在其他地方)，然后是指令符。这个表达式称为 "状态公式"。

- The Undecidable》，第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.

早些时候，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-构型 "的符号（指令的标签）和磁带上的所有符号一起放在扫描的方块下面（The Undecidable，第121页）；他把这个称为 "完整的构型"（The Undecidable，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。

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₄ 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₄" 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展示了如何写出一台机器的 "情况 "的’’’ 哥德尔数Gödel number ’’’：他把 "m-配置 "符号q₄放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-磁带图)，并把它放在扫描方格的右边。但Kleene把 "q₄ "本身称为 "机器状态"（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):

1A1

示例：3次“移动”后，三态2符号穷忙的总状态（取自下图中的示例“运行”）：

1A1

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: B01; the tape has a single 1 on it, but the head is scanning the 0 ("blank") to its left and the state is B.

这意味着：经过三次移动后，磁带上有......000110000......，磁头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；磁带上有一个 "1"，但磁头正在扫描它左边的 "0"（"空白"），状态是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.

"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.

图灵机情况中，应阐明 "状态 "是哪种状态。(i)当前指令，或(ii)磁带上的符号列表连同当前指令，或(iii)磁带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。

Turing's biographer Andrew Hodges (1983: 107) has noted and discussed this confusion.

图灵的传记作者安德鲁 · 霍奇斯Andrew Hodges (1983:107)注意到并讨论了这种混淆。

Turing machine "state" diagrams

图灵机的状态图

The table for the 3-state busy beaver ("P" = print/write a "1") 3状态穷忙的表格("P" = 打印/写入 a "1")
Tape symbol 磁带符号	Current state A 当前状态A			Current state B 当前状态B			Current state C 当前状态C
	Write symbol 写入符号	Move tape 移动磁带	Next state 下一个状态	Write symbol 写入符号	Move tape 移动磁带	Next state 下一个状态	Write symbol 写入符号	Move tape 移动磁带	Next state 下一个状态
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	HALT

文件:State diagram 3 state busy beaver 2B.svg

The "3-state busy beaver" Turing machine in a 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 Print" then move tape "R Right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).

"3态穷忙"图灵机的有限状态表示。每个圆圈代表表的一个 "状态"--一个 "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.

通常大表最好是以表的形式留下（Booth，第74页）。它们更容易由计算机以表格形式模拟出来（Booth，p.74）。然而，某些概念，例如具有 "复位 "状态的机器和具有重复模式的机器（参见Hill和Peterson p. 244ff）在被视为图纸时更容易被看到。

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.

图纸是否代表了对其表的改进，必须由读者针对特定的情况来决定。详见有限状态机。

文件:Moves of a 3-state Busy Beaver.jpg

The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom.

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", 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).

“计算进度 "图显示了三态穷忙从开始到结束的计算过程中的 "状态"（指令）进度。最右边是每一步的图灵 "完整配置"（Kleene "情况"，Hopcroft-Ullman "瞬时描述"）。如果机器被停止并清空 "状态寄存器 "和整个磁带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。

Models equivalent to the Turing machine model

等价于图灵机的模型 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. nbsp;159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能更强大地计算(即更多的数学函数)。(回想一下，’’’Church–Turing理论Church–Turing thesis ’’’ Church–Turing 论文假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。)

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.

在另一个极端，一些非常简单的模型变成了’’’图灵等价Turing-equivalent ’’’模型，即具有与图灵机模型相同的计算能力。

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.

常见的等价模型是’’’多带图灵机 multi-tape Turing machine’’’、’’’多道图灵机 multi-track Turing machine’’’、有输入和输出的机器，以及与确定型图灵机(DTM)相对的’’’ 非确定型图灵机 non-deterministic Turing machine ’’’(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.

对于实际的和教学的意图，等价的’’’ 寄存器机器register machine ’’’可以作为通常的汇编’’’ 编程语言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.

一个有趣的问题是用具体编程语言表示的计算模型是否是图灵等价的。虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人，2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，’’’ ANSI C’’’ 并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如’’’ Pascal’’’ ，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。

Choice c-machines, oracle o-machines

选择c型机、oracle o型机 Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":

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年)，Turing就对 "运动......完全由配置决定 "的 "自动机"和 "选择机 "进行了区分： ——Solitude意译 /* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

...它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况

 ——The Undecidable，第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₁, i₂, ..., i_n (i₁ = 0 or 1, i₂ = 0 or 1, ..., i_n = 0 or 1), and hence the number 2ⁿ + i₁2^n-1 + i₂2^n-2 + ... +i_n completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, The Undecidable, p. 138)

Turing(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i₁, i₂, ..., i_n (i₁ = 0 或 1, i₂ = 0 或 1, ..., i_n = 0 或 1) 的选择序列决定，因此数字 2ⁿ + i₁2^n-1 + i₂2^n-2 + ... +i_n 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”(侧重于脚注，The Undecidable，第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 -)图灵机可以用来模拟一个非确定型的图灵机的动作; Turing在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。

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).

预言机或 o-machine 是一种图灵机器，它将计算暂停在“ o”状态，同时，为了完成计算，它“等待”“oracle”- 一个未指定的实体“除了说它不可能是一台机器”的决定(Turing(1939) ，The undecutable，p. 166-168)。

Universal Turing machines

通用图灵机

主条目：’’’通用图灵机 Universal Turing machine’’’

文件: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页(斜体) :

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

我们可以发明一个机器，用来计算任何可计算的序列。如果向这台机器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年) ，它被认为是惊人的。Turing称之为“通用机器”(缩写为“U”)的计算模型被一些人(参见Davis(2000))认为是产生存储程序计算机概念的基础理论突破。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

图灵的论文......实质上包含了现代计算机的发明以及伴随着它的一些编程技术。

——Minsky（1967），第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)

就计算复杂度而言，多带通用图灵机与它所模拟的机器相比，只需要慢上一个对数系数。这个结果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)

Comparison with real machines

与真实机器的比较

文件:Lego Turing Machine.jpg

A Turing machine realization using Lego pieces

使用乐高积木实现的图灵机

It is often said模板:By whom 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.

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:

有很多方法可以解释为什么图灵机是真实计算机的有用模型:

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.

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.

凡是真实计算机能计算的东西，图灵机也能计算。例如："图灵机可以模拟真实的计算机，也可以计算真实的计算机。"图灵机可以模拟编程语言中任何类型的子程序，包括递归程序和任何已知的参数传递机制" (Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真实的计算机，而不用考虑IO。因此，关于图灵机的局限性的说法也将适用于真实计算机。

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.

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.

区别只在于图灵机操纵无限制的数据量的能力。然而，给定有限的时间，图灵机（像真实的机器一样）只能处理有限的数据量。

Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.

3.Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.

像图灵机一样，真实的机器可以根据需要，通过获取更多的磁盘或其他存储介质来扩大其存储空间。

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.

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.

使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机（DFA）却有四千亿个状态。这使得DFA的表示方式无法分析。

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.

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.

图灵机描述的算法与它们使用多少内存无关。当前任何一台机器所拥有的内存都是有限制的，但这个限度可以随着时间的推移而任意上升。图灵机让我们可以对算法做出（理论上）永恒的陈述，无论传统计算机架构如何进步。

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).

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).

图灵机简化了算法的陈述。运行在图灵机等效的抽象机上的算法通常比运行在真实机器上的同类算法更通用，因为它们有任意精度的数据类型可用，而且永远不用处理意外情况（包括但不限于内存耗尽）。

文件:Turingmachine.jpg

An experimental prototype of a Turing machine

图灵机的实验原型

Limitations of Turing machines

图灵机的局限性

Computational complexity theory

计算复杂性理论

模板:Further

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.

图灵机的一个局限性在于它们不能很好地模拟特定排列的优势。例如，现代存储程序计算机实际上是一种更具体的抽象机器的实例，这种抽象机器被称为随机存取存储程序机器或 RASP 机器模型。与通用图灵机一样，RASP 将其“程序”存储在有限状态机的“指令”之外的“内存”中。与通用图灵机不同的是，RASP 具有无限数量可区分的、有编号但无限制的“寄存器”ー可以包含任何整数的内存 "单元"(参见Elgot和Robinson(1964)，Hartmanis(1971)，特别是Cook-Rechow(1973)；参考随机存取机) RASP 的有限状态机可以间接寻址(例如，一个寄存器的内容可以用作另一个寄存器的地址) ，因此当图灵机被用作约束运行时间的基础时，可以证明某些算法的运行时间有一个 "假下限"（由于图灵机的假简化假设）。这方面的一个例子是二进制搜索，当使用 RASP 计算模型而不是图灵机模型时，可以证明这种算法的运行速度更快。

Concurrency

并发性 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.)

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.)

图灵机的另一个局限性是它们不能很好地模拟并发性。例如，可以由始终停止的非确定型图灵机从空白磁带上开始计算整数大小的界限。(见关于无界不可判定论的文章)相比之下，有一些没有输入的总是停止的并发系统可以计算无界大小的整数。(可以用本地存储创建一个进程，这个进程的初始化计数为0，它同时给自己发送一个停止和继续的消息。当它收到一个继续消息时，它将自己的计数增加1，并给自己发送一个继续消息。当它收到停止消息时，它在本地存储中以一个无限制的数字停止）。)

Interaction

交互

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, 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 I/O automata are usually preferred.

自20世纪70年代以来，计算机的交互式使用变得更加普遍。原则上，可以通过让外部代理与图灵机同时从磁带中读出并写入磁带的方式进行建模，但这很少与交互的实际发生方式相吻合；因此，在描述交互性时，通常首选I/O自动机等替代程序。

History

历史

They were described in 1936 by Alan Turing.

Alan Turing在1936年描述了它们。

Historical background: computational machinery

历史背景：计算机器

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":

罗宾•甘迪Robin Gandy (1919-1995)是 Alan Turing (1912-1954)的学生，也是他一生的朋友，他将“计算机器”这一概念的渊源追溯到查尔斯•巴贝奇Charles Babbage (大约1834年) ，并提出了“ 巴贝奇论” :

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

整个发展和分析的操作现在都可以由机器来执行.

Gandy's analysis of Babbage's Analytical Engine describes the following five operations (cf. p. 52–53):

甘迪对巴贝奇分析机的分析描述了以下五种操作(参见。第52-53页) :

The arithmetic functions +, −, ×, where − indicates "proper" subtraction x − y = 0 if y ≥ x.

The arithmetic functions +, −, ×, where − indicates "proper" subtraction 0}} if y ≥ x. 算术函数 + ,-，× ，其中-表示“适当的”减法x-y=0,如果y ≥x。

Any sequence of operations is an operation.

Any sequence of operations is an operation.

任何运算序列都是一个运算。

Iteration of an operation (repeating n times an operation P).

Iteration of an operation (repeating n times an operation P). Iteration of an operation (repeating n times an operation P).

操作的迭代(重复 n 次操作 p)。

Conditional iteration (repeating n times an operation P conditional on the "success" of test T).

Conditional iteration (repeating n times an operation P conditional on the "success" of test T).

条件迭代(以测试 t 的“成功”为条件重复 n 次操作 p)。

Conditional transfer (i.e., conditional "goto").

Conditional transfer (i.e., conditional "goto").

条件转移(即有条件的“ goto”)。

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指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机”的提议，包括珀西 · 卢德盖特Percy Ludgate (1909年)、莱昂纳多 · 托雷斯 · 奎维多Leonardo Torres y Quevedo(1914年)、莫里斯 · d’奥卡涅Maurice d'Ocagne (1922年)、路易斯 · 库夫尼纳尔Louis Couffignal(1933年)、万尼瓦尔 · 布什Vannevar Bush (1936年)、霍华德 · 艾肯Howard Aiken(1937年)。然而:

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

...强调的是一个固定的可迭代的算术运算序列的编程。没有认识到条件迭代和条件转移对一般计算机理论的根本重要性......。

- Gandy，第55页

The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900

“决策问题”:希尔伯特Hilbert 1900年提出的第10号问题 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:

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年提出的Hilbert问题，10号问题的一个方面已经浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}

当我们知道一个程序，允许任何给定的逻辑表达式通过有限多的操作来决定其有效性或可满足性时，判定问题[一阶逻辑的决策问题]就被解决了。可判定性问题必须被认为是数理逻辑的主要问题。—2008年，德尔肖维茨Dershowitz和古列维奇Gurevich引用了此译文和德文原文

By 1922, this notion of "Entscheidungsproblem" had developed a bit, and H. Behmann stated that

到了1922年，这个“可判定问题”的概念有了些许发展，h. Behmann 指出：

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

需要一个相当明确的、普遍适用的处方，它将允许人们在有限的步骤中决定一个给定的纯逻辑论断的真假... .. —Gandy，第57页，引用Behmann的话。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

Behmann指出，......一般问题相当于决定哪些数学命题是真的问题。 —同上 /* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

如果一能够解决判定问题，那么人们就会有一个 "解决许多（甚至所有）数学问题的程序"。

- 同上，第92页

By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics 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.

By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete ... Second, was mathematics consistent ... And thirdly, was mathematics 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年的国际数学家大会，Hilbert把他的问题说得非常精确。第一，数学是完整的吗? 第二，数学是一致的吗? 第三，数学是可判定的吗? ”(Hodges p. 91，Hawking p. 1121)。1930年，在Hilbert发表退休演讲的同一次会议上，库尔特 · 哥德尔(Kurt Gödel)回答了前两个问题(这让Hilbert颇为懊恼) ; 而第三个问题（判定问题）不得不等到上世纪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.

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），Church和他的两个学生斯蒂芬•克莱恩Stephen Kleene和 j.B. Rosser也是如此，利用 Church 的 λ微积分和哥德尔的递归理论。Church的论文(发表于1936年4月15日)表明，判定问题确实是“无法判定的” ，比Turing早了将近一年(Turing的论文1936年5月28日提交，1937年1月发表)。与此同时，Emil Post 在1936年秋天提交了一篇简短的论文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明Church的λ 微积分和他的机器可以计算同样的函数。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

但Church所做的是完全不同的事情，而且在某种意义上是较弱的。......Turing的构造更直接，并提供了最初原则的论据，从而弥补了 Church证明中的空白。

—Hodges，第112页

And Post had only proposed a definition of calculability and criticized Church's "definition", but had proved nothing.

Post只是提出了一个可计算性的定义，并批评了Church的“定义” ，但没有证明任何事情。

Alan Turing's a-machine

Alan Turing的机器

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:

1935年春天，Turing作为英国剑桥大学国王学院的一名年轻的硕士生接受了这个挑战，他曾受到逻辑学家纽曼m. h. a. Newman 的演讲的鼓舞，从他们那里学到了哥德尔的作品和判定问题。在Turing1955年的讣告中，Newman写道:

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

对于 "什么是'机械'过程 "？图灵回答了一个特有的答案'可以由机器完成的事情'，然后他开始着手分析计算机的一般概念。

—Gandy，第74页

Gandy states that:

甘迪表示:

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

我想，但我不知道，图灵，从他的工作开始，就把证明判定问题的不可判定性作为他的目标。他告诉我，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的上述言论有“误导性” ，但并非所有人都赞同这一观点。Turing一生都对机器有着浓厚的兴趣: “Alan从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械的'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的如下定义。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么这个函数就是有效的可计算函数"。我们可以从字面上理解这句话，将纯机械过程理解为可以由机器完成的过程。可以用一定的正常形式对这些机器的结构进行数学描述。这些思想的发展导致了作者对可计算函数的定义，以及对具有有效可计算性的计算认同。要证明这三个定义第3个是λ可计算性是等价的并不困难，虽然有些费力。

- 图灵(1939)在The Undecidable一书中，第160页。

When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE (Automatic Computing Engine), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the EDVAC [the USA's initiative], but in his own universal machine" (Hodges p. 318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) Turing's Thesis. But what Turing did prove with his computational-machine model appears in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (1937):

When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE (Automatic Computing Engine), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the EDVAC [the USA's initiative], but in his own universal machine" (Hodges p. 318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) Turing's Thesis. But what Turing did prove with his computational-machine model appears in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (1937):

当Turing回到英国后，他他最终成为了破译德国密码“英格玛”的共同负责人的加密机所创造的德国秘密密码；他还参与了ACE（自动计算引擎）的设计，"Turing的ACE提案实际上是自成一体的，它的根源不在于EDVAC，而在于他自己的通用机器"（Hodges p.318）。关于被Kleene(1952)命名为图灵论文的起源和性质的争论仍在继续。但图灵用他的计算机模型确实证明了什么，出现在他的论文《论可计算的数字，以及对可判定性的应用》(1937)中:

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

希尔伯特-判定问题不可能有解......。因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。

- 摘自Turing的论文，详见The Undecidable，第145页。

Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".

Turing的例子(他的第二个证明):如果有人要求用一般程序来告诉我们:“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。

=1937–1970: The "digital computer", the birth of "computer science"

1937–1970: "数字计算机"，"计算机科学 "的诞生。

In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical relays (Hodges p. 138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p. 138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany (Konrad Zuse (1938)), and in the United States (Howard Aiken) and George Stibitz (1937); the fruits of their labors were used by both the Axis and Allied militaries in World War II (cf. Hodges p. 298–299). In the early to mid-1950s Hao Wang and Marvin Minsky reduced the Turing machine to a simpler form (a precursor to the Post–Turing machine of Martin Davis); simultaneously European researchers were reducing the new-fangled electronic computer to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the counter machine; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the register machine and random-access machine models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set.

1937年，在普林斯顿写博士论文的时候，Turing从零开始制造了一个数字(布尔逻辑)乘法器，自制了机电继电器(Hodges p. 138)。“Alan的任务是将图灵机的逻辑设计体现在继电器操作的开关网络中......”(Hodges p. 138)。虽然Turing最初可能只是好奇和试验，但是在德国(Konrad Zuse，1938年)和美国(Howard Aiken，1937年)都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。Hodges p. 298-299)。在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–present: the Turing machine as a model of computation

1970年至今：作为计算模型的图灵机

Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the theory of computation. In particular, computational complexity theory makes use of the Turing machine:

今天，计数器、寄存器和随机存取机以及它们的祖先图灵机仍然是理论家们研究计算理论问题的首选模型。特别是，计算复杂性理论利用了图灵机。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

离线多带图灵机... ，它代表了面向字符串计算的标准模型，以及 Cook 和 Reckhow... 提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。 - van Emde Boas 1990:4

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

只有在算法分析的相关领域，这个角色才被RAM模型所取代。

- van Emde Boas 1990:16

Notes

↑ Occasionally called an action table or transition function.
↑ Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].

References

Primary literature, reprints, and compilations

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 (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY.

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 first and second proofs.

Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 2 (published 1937). 42: 230–265. doi:10.1112/plms/s2-42.1.230. (and Turing, A.M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. 2 (published 1937). 43 (6): 544–6. doi:10.1112/plms/s2-43.6.544.). 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 Turing, A. M. (1996). "Intelligent Machinery, A Heretical Theory". Philosophia Mathematica. 4 (3): 256–260. doi:10.1093/philmat/4.3.256.

F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, 13(4):533–546, 1966.

Computability theory

Boolos, George; Richard Jeffrey (1999) [1989]. Computability and Logic (3rd ed.). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X. https://archive.org/details/computabilitylog0000bool_r8y9.

Boolos, George; John Burgess; Richard Jeffrey (2002). Computability and Logic (4th ed.). Cambridge UK: Cambridge University Press. 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 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.

Martin Davis (1958). Computability and Unsolvability. 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.

Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.

Hennie, Fredrick (1977). Introduction to Computability. Addison–Wesley, Reading, Mass. QA248.5H4 1977. . On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.

John Hopcroft and Jeffrey Ullman (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X. Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.

Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Reading Mass: Addison–Wesley. ISBN 0-201-44124-1. Distinctly different and less intimidating than the first edition.

Stephen Kleene (1952), Introduction to Metamathematics, North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII Computable functions is on Turing machine proofs of computability of recursive functions, etc.

Knuth, Donald E. (1973). Volume 1/Fundamental Algorithms: The Art of computer Programming (2nd ed.). Reading, Mass.: Addison–Wesley Publishing Company. . With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 History and Bibliography pp. 225ff and 2.6 History and Bibliographypp. 456ff.

Zohar Manna, 1974, Mathematical Theory of Computation. Reprinted, Dover, 2003.

Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.

Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19–56.

Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability, The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition 1967,

(pbk.)

Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. https://archive.org/details/introductiontoth00sips. Chapter 3: The Church–Turing Thesis, pp. 125–149.

Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1st ed.). New York: McGraw–Hill Book Company. ISBN 0-07-061726-0.

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?],

(Volume A). QA76.H279 1990. Valuable survey, with 141 references.

Church's thesis

Nachum Dershowitz; Yuri Gurevich (September 2008). "A natural axiomatization of computability and proof of Church's Thesis" (PDF). Bulletin of Symbolic Logic. 14 (3). Retrieved 2008-10-15.

Roger Penrose (1990) [1989]. The Emperor's New Mind (2nd ed.). Oxford University Press, New York. ISBN 0-19-851973-7.

Small Turing machines

Rogozhin, Yurii, 1998, "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)

Stephen Wolfram, 2002, A New Kind of Science, Wolfram Media,

Brunfiel, Geoff, Student snags maths prize, Nature, October 24. 2007.

Jim Giles (2007), Simplest 'universal computer' wins student $25,000, New Scientist, October 24, 2007.

Alex Smith, Universality of Wolfram’s 2, 3 Turing Machine, Submission for the Wolfram 2, 3 Turing Machine Research Prize.

Vaughan Pratt, 2007, "Simple Turing machines, Universality, Encodings, etc.", FOM email list. October 29, 2007.

Martin Davis, 2007, "Smallest universal machine", and Definition of universal Turing machine FOM email list. October 26–27, 2007.

Alasdair Urquhart, 2007 "Smallest universal machine", FOM email list. October 26, 2007.

Hector Zenil (Wolfram Research), 2007 "smallest universal machine", FOM email list. October 29, 2007.

Todd Rowland, 2007, "Confusion on FOM", Wolfram Science message board, October 30, 2007.

Olivier and Marc RAYNAUD, 2014, A programmable prototype to achieve Turing machines" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).

Other

Martin Davis (2000). Engines of Logic: Mathematicians and the origin of the Computer (1st ed.). W. W. Norton & Company, New York. ISBN 978-0-393-32229-3.

Robin Gandy, "The Confluence of Ideas in 1936", pp. 51–102 in Rolf Herken, see below.

Stephen Hawking (editor), 2005, God Created the Integers: The Mathematical Breakthroughs that Changed History, Running Press, Philadelphia,

. Includes Turing's 1936–1937 paper, with brief commentary and biography of Turing as written by Hawking.

Rolf Herken (1995). The Universal Turing Machine—A Half-Century Survey. Springer Verlag. ISBN 978-3-211-82637-9.

Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.

Ivars Peterson (1988). The Mathematical Tourist: Snapshots of Modern Mathematics (1st ed.). W. H. Freeman and Company, New York. ISBN 978-0-7167-2064-5. https://archive.org/details/mathematicaltour00pete.

Roger Penrose, The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, Oxford and New York, 1989 (1990 corrections),

.

Paul Strathern (1997). Turing and the Computer—The Big Idea. Anchor Books/Doubleday. ISBN 978-0-385-49243-0. https://archive.org/details/turingcomputer00stra.

Hao Wang, "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63–92 (1957).

Charles Petzold, Petzold, Charles, The Annotated Turing, John Wiley & Sons, Inc.,

Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, 2009,

, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

Kantorovitz, Isaiah Pinchas (December 1, 2005). "A note on turing machine computability of rule driven systems". SIGACT News. 36 (4): 109–110. doi:10.1145/1107523.1107525. S2CID 31117713.

Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: "On Undecidability Results of Real Programming Languages", In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.

External links

模板:Commons category

模板:Springer

Turing Machine in the Stanford Encyclopedia of Philosophy

Turing Machine Causal Networks by Enrique Zeleny as part of the Wolfram Demonstrations Project.

Category:1936 in computing

类别: 1936年

模板:Curlie

Category:1937 in computing

类别: 1937年

Category:Educational abstract machines

类别: 教育摘要机器

Category:Theoretical computer science

类别: 理论计算机科学

模板:Formal languages and grammars

Category:Alan Turing

分类: 阿兰 · 图灵

Category:Models of computation

类别: 计算模型

Category:Formal methods

类别: 正式方法

Category:Computability theory

类别: 可计算性理论

Category:English inventions

类别: 英国发明

Category:Automata (computation)

类别: 自动机(计算)

Category:Formal languages

类别: 正式语言

Category:Abstract machines

类别: 抽象机器

This page was moved from wikipedia:en:Turing machine. Its edit history can be viewed at 图灵机/edithistory

[1] Occasionally called an action table or transition function.

[2] Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].

[1]

[2]

图灵机

目录

图灵机概述

物理描述

描述

正式定义

Additional details required to visualize or implement Turing machines

Alternative definitions

The "state"

Turing machine "state" diagrams

Models equivalent to the Turing machine model

Choice c-machines, oracle o-machines

Universal Turing machines

Comparison with real machines

Limitations of Turing machines

Computational complexity theory

Concurrency

Interaction

History

Historical background: computational machinery

The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900

Alan Turing's a-machine

=1937–1970: The "digital computer", the birth of "computer science"

1970–present: the Turing machine as a model of computation

See also

Notes

References

Primary literature, reprints, and compilations

Computability theory

Church's thesis

Small Turing machines

Other

External links

导航菜单

搜索