更改

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.

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），它控制着计算机正在进行的所有数据操作，规范及其使用顺序内存来存储数据。更具体的，图灵机是一种能够枚举字母表有效字符串的一些任意子集的机器（自动机）; 这些字符串是字母递归可枚举集的一部分。图灵机有一卷无限长的磁带，它可以在上面执行读写操作。

图灵机是一种中央处理器单元（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.

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.

The Turing machine is capable of processing an unrestricted grammar, which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus.

The Turing machine is capable of processing an unrestricted grammar, which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus.

 

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective 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:<blockquote>...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.

In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:<blockquote>...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.

— Turing 1948, p. 3</blockquote>在1948年的论文《智能机器》中，图灵写道他的机器包括:

— Turing 1948, p. 3

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

 

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

=== 描述 ===

=== 描述 ===

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

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”）。图灵想象的不是一种机制，而是一种他被称之为计算机的“人”，可以严格执行这些决定性的机械规则的人。

 

图灵机在纸带上进行机械操作的机器进行数学建模。在这个纸带上有符号，机器可以使用读写头一次一个读取和写入这些符号。操作完全由一组有限的基本指令决定，例如“在状态42中，如果看到的符号为0，则写入1；如果看到的符号为1，则改为状态17；在状态17中，如果看到的符号为0.写一个1并更改为状态6“等。在原始的文章中（“论可计算的数字，以及对可判定行的影响 '''On Computable Numbers, with an Application to the Entscheidungsproblem'''”）。图灵想象的不是一种机制，而是一种他被称之为计算机的“人”，可以严格执行这些决定性的机械规则的人。

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

* 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”）和一个或者多个其他符号。假设纸带可以任意向左/向右扩展，所以图灵机拥有能够支撑起计算所需的纸带数量。没有写入过的单元格被假定用空白符号填充。在某些型号中，胶带的左端标有特殊符号；磁带向右侧延伸或无限延伸。

* 纸带。纸带被分成多个单元，每个紧邻着。每个单元都包含来自某个有限字母表的一个符号。字母表中包含有一个特殊的空白符号（此处写作“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 ''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 finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].</ref> 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):

* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].</ref> 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元组模型）：

* 一个有限的指令表，给定机器当前所处的状态(q_i)和它在纸带上读取的符号(a_j)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：

# 擦除或写入一个符号（将a_j替换为a_j1）。

# 擦除或写入一个符号（将a_j替换为a_j1）。