更改

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.

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.

 

图灵机在一条无限长的纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头在一个单元格上“读取”或“扫描”纸带上的符号。然后，图灵机根据读取的符号和机器自身在用户指定指令的“有限表”中的状态，机器(i)在单元格中写下一个符号（例如，有限字母表中的数字或字母），然后(ii)将纸带向左或向右移动一个单元，然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。

图灵机在一个无限大的存储纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头放在一个单元格上“读取”或“扫描”纸上的符号。然后，图灵机根据该符号和机器自身在用户指定指令的 "有限表 "中的状态，机器(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:

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

1.Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task)?

# Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?

2.Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?

Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the ''Entscheidungsproblem'' ('decision problem').[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]

Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the ''Entscheidungsproblem'' ('decision problem').[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]

图灵机是1936年由阿兰 · 图灵Alan Turing发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:  

图灵机是1936年由[[阿兰·图灵]](Alan Turing)发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:  

(1)是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?

# 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?

(2)是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？

# 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？

''因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是可判定性(Entscheidungsproblem, 决策问题)的不可计算性。''

''因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。''

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.

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)”。

图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用“随机存取存储器(Random-access memory)”。

Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.

Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.