150
个编辑
更改
跳到导航
跳到搜索
第60行：
第60行： − + 第67行：
第67行： + + + + + + + +
无编辑摘要
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（Alonzo Church，美国著名数学家）'''提出了一个更面向数学的定义，具有普遍性。他将在 λ 演算的工作和图灵在正式计算机理论中的工作融合，被称为邱奇-图灵论题。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（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.
...以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号；它被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
...以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号；它被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
=== 描述 ===
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.
* 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'）和一个或多个其他符号。假设磁带是可以向左和向右任意延伸的，所以图灵机总是有它计算所需的磁带。之前没有写过的单元格被假定为用空白符号填充。在某些模型中，磁带的左端标有特殊符号；磁带向右延伸或无限延伸。
磁带被分成多个单元, 一个挨着一个.。每一个单元都包含一个来自某个有限字母表的符号。字母表包含一个特殊的空白符号（这里写成'0'）和一个或多个其他符号。假设磁带是可以向左和向右任意延伸的，所以图灵机总是有它计算所需的磁带。之前没有写过的单元格被假定为用空白符号填充。在某些模型中，磁带的左端标有特殊符号；磁带向右延伸或无限延伸。