150
个编辑
更改
无编辑摘要
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)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
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:
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)?
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)发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
# 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
# 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
''因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是可判定性(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)”。
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.