113
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + − − − − 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. − − + − 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|缩略图|图灵机的理想模型]] − − 图灵机是1936年由[[阿兰·图灵]](Alan Turing)发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题: − − − + − ''因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语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.+ − − 图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用“随机存取存储器(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. − − 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. − − 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. − 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. − − − 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. −
无编辑摘要
'''图灵机'''是一种数学计算模型，定义了一个抽象的机器，该机器可以根据指定的规则表在纸带上进行操作。虽然图灵机模型非常简单，但是图灵机可以模拟任何给定的计算机算法。
图灵机在一条无限长的纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头在一个单元格上“读取”或“扫描”纸带上的符号。然后，图灵机根据读取的符号和机器自身在用户指定指令的“有限表”中的状态，机器(i)在单元格中写下一个符号（例如，有限字母表中的数字或字母），然后(ii)将纸带向左或向右移动一个单元，然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
图灵机在一条无限长的纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头在一个单元格上“读取”或“扫描”纸带上的符号。然后，图灵机根据读取的符号和机器自身在用户指定指令的“有限表”中的状态，机器(i)在单元格中写下一个符号（例如，有限字母表中的数字或字母），然后(ii)将纸带向左或向右移动一个单元，然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
图灵机是1936年由'''阿兰·图灵（Alan Turing）'''发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
# 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
# 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
# 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
# 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。
[[文件:图灵机.jpg|缩略图|图灵机的理想模型]]
图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器 （Random-access memory）。
'''图灵完备性（Turing completeness）'''是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
==图灵机概述==
==图灵机概述==
图灵机是一种中央处理器单元（Central Processing Unit，即CPU），控制着计算机的所有数据操作，规范及其使用顺序内存来存储数据。更具体的，图灵机是一种能够枚举字母表有效字符串的机器（自动机）;这些字符串是字母递归可枚举集的一部分。理想情况下，图灵机有无限长的纸带，其可以在上面执行读写操作。
图灵机是一种中央处理器单元（Central Processing Unit，即CPU），控制着计算机的所有数据操作，规范及其使用顺序内存来存储数据。更具体的，图灵机是一种能够枚举字母表有效字符串的机器（自动机）;这些字符串是字母递归可枚举集的一部分。理想情况下，图灵机有无限长的纸带，其可以在上面执行读写操作。
假设有一个“黑盒子”，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为停机问题（Halting Problem）是不可解的，停机问题对计算的理论极限有着重大的影响。
假设有一个“黑盒子”，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为停机问题（Halting Problem）是不可解的，停机问题对计算的理论极限有着重大的影响。
图灵机能够处理不受限制的语法，这意味着它能够以无限多的方式鲁棒地评价一阶逻辑。通过λ运算可以证明这一点。
图灵机能够处理不受限制的语法，这意味着它能够以无限多的方式鲁棒地评价一阶逻辑。通过λ运算可以证明这一点。
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（Alonzo Church，美国著名数学家）'''提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（Alonzo Church，美国著名数学家）'''提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
===物理描述===
===物理描述===
在1948年的论文《智能机器（Intelligent Machinery）》中，图灵写道他的机器包括: 以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号，被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
在1948年的论文《智能机器（Intelligent Machinery）》中，图灵写道他的机器包括: 以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号，被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
===描述===
===描述===
图灵机在纸带上进行机械操作的机器进行数学建模。纸带上有符号，机器可以使用读写头一次一个读取和写入这些符号。操作完全由一组有限的基本指令决定，例如“在状态42中，如果看到的符号为0，则写入1；如果看到的符号为1，则改为状态17；在状态17中，如果看到的符号为0，写一个1并更改为状态6”等。在原始的文章中（“论可计算的数字，以及对可判定行的影响”）。图灵想象的不是一种机制，而是一种他被称之为计算机的“人”，可以严格执行这些决定性的机械规则的人。
更切确地说，图灵机由以下部分组成:
更切确地说，图灵机由以下部分组成:
* 纸带。纸带被分成多个单元，每个紧邻着。每个单元都包含来自某个有限字母表的一个符号。字母表中包含有一个特殊的空白符号（此处写作“0”）和一个或者多个其他符号。假设纸带可以任意向左/向右扩展，所以图灵机拥有能够支撑起计算所需的纸带数量。没有写入过的单元格被假定用空白符号填充。在某些型号中，胶带的左端标有特殊符号，磁带向右侧延伸或无限延伸。
* 读写头。读写头可以在纸带上读写符号，并一次将纸带左右移动一个（有且仅有一个）单元格。在某些型号的机器中，读写头移动而纸带静止。
* 读写头。读写头可以在纸带上读写符号，并一次将纸带左右移动一个（有且仅有一个）单元格。在某些型号的机器中，读写头移动而纸带静止。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-tuple models):
* A finite ''table''<ref>Occasionally called an ''action table'' or ''transition function''.</ref> of instructions<ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref> that, given the ''state''(q<sub>i</sub>) the machine is currently in ''and'' the ''symbol''(a<sub>j</sub>) it is reading on the tape (symbol currently under the head), tells the machine to do the following ''in sequence'' (for the 5-tuple models):