集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

图灵机 (查看源代码)

2021年7月25日 (日) 18:53的版本

删除2,221字节 、 2021年7月25日 (日) 18:53
无编辑摘要
第11行： 第11行：       −
图灵机在一个无限大的存储纸带上运行，纸带被分割成若干个离散的单元格。机器头放在一个单元格上“读取”或“扫描”纸上的符号。然后，图灵机根据该符号和机器自身在用户指定指令的 "有限表 "中的状态，机器(i)在单元中写下一个符号（例如，有限字母表中的数字或字母）（有些模型允许符号擦除或不写），然后(ii)将纸带向左或向右移动一个单元（有些模型不允许移动，有些模型移动磁头），然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
+
 
 +
图灵机在一个无限大的存储纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头放在一个单元格上“读取”或“扫描”纸上的符号。然后，图灵机根据该符号和机器自身在用户指定指令的 "有限表 "中的状态，机器(i)在单元中写下一个符号（例如，有限字母表中的数字或字母）（有些模型允许符号擦除或不写），然后(ii)将纸带向左或向右移动一个单元（有些模型不允许移动，有些模型移动读写头），然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
      第71行： 第72行：       −
图灵机在纸带上进行机械操作的机器进行数学建模。在这个纸带上有符号，机器可以使用纸带头一次一个读取和写入这些符号。操作完全由一组有限的基本指令决定，例如“在状态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'''”）。图灵想象的不是一种机制，而是一种他被称之为计算机的“人”，可以严格执行这些决定性的机械规则的人。
      第79行： 第81行：     
* 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'）和一个或多个其他符号。假设磁带是可以向左和向右任意延伸的，所以图灵机总是有它计算所需的磁带。之前没有写过的单元格被假定为用空白符号填充。在某些模型中，磁带的左端标有特殊符号；磁带向右延伸或无限延伸。
      
* 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 ''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.
 
* 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.
 +
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
   −
状态寄存器，存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。Turing写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
+
状态寄存器，存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。Turing写道，这些状态代替了执行计算的人通常会处于的 "思想状态"。
    
* 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):
−
 
+
* 一个有限的指令表，给定机器当前所处的状态(q<sub>i</sub>)和它在纸带上读取的符号(a<sub>j</sub>)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：
−
有限的指令表，给定机器当前所处的状态(q<sub>i</sub>)和它在磁带上读到的符号(a<sub>j</sub>)(当前在磁头下的符号)，告诉机器依次做以下事情(对于五元组模型)。
      
# Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
 
# Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
−
  −
Either erase or write a symbol (replacing a<sub>j</sub> with a<sub>j1</sub>).
  −
  −
擦除或写入一个符号（将a<sub>j</sub>替换为a<sub>j1</sub>）。
  −
   
# Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left ''or'' 'R' for one step right ''or'' 'N' for staying in the same place).
 
# Move the head (which is described by d<sub>k</sub> and can have values: 'L' for one step left ''or'' 'R' for one step right ''or'' 'N' for staying in the same place).
−
  −
移动磁头（由d<sub>k</sub>描述，可以有值。'L'表示向左移动一步，'R'表示向右移动一步，'N'表示停留在原地）。
  −
   
# Assume the same or a ''new state'' as prescribed (go to state q<sub>i1</sub>).
 
# Assume the same or a ''new state'' as prescribed (go to state q<sub>i1</sub>).
   −
假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
+
# 擦除或写入一个符号（将a<sub>j</sub>替换为a<sub>j1</sub>）。
 +
# 移动读写头（由d<sub>k</sub>描述，如果值为'L'表示向左移动一步，'R'表示向右移动一步，'N'表示停留在原地）。
 +
# 假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
    
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
 
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol ''or'' (ib) move the head left or right, ''and then'' (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
   −
In the 4-tuple models, erasing or writing a symbol (a<sub>j1</sub>) and moving the head left or right (d<sub>k</sub>) are specified as separate instructions. The table tells the machine to (ia) erase or write a symbol or (ib) move the head left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled.
+
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
   −
在四元组模型中，擦除或写入符号(a < sub > j1 )和向左或向右移动头(d < sub > k )被指定为单独的指令。该表告诉机器擦除或写入一个符号，或者(ib)向左或向右移动磁头，然后(ii)按照规定假定相同或新的状态，但不能在同一指令中同时进行(ia)和(ib)两个动作。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
  −
  −
  −
  −
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is ''finite'', ''discrete'' and ''distinguishable''; it is the unlimited amount of tape and runtime that gives it an unbounded amount of [[Computer storage|storage space]].
      
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.
 
Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.
   −
机器的每一部分(即它的状态、符号集合和在任何给定时间使用过的磁带)及其动作（如打印、擦除和磁带运动)是有限的、离散的和可区分的，正是磁带和运行时间的无限量使它具有无限制的存储空间。
+
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
−
 
  −
==Formal definition==
  −
正式定义
  −
Following {{harvtxt|Hopcroft|Ullman|1979|p=148}}, a (one-tape) Turing machine can be formally defined as a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
  −
 
  −
Following , Hopcroft & Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> where
  −
 
  −
按照Hopcroft & Ullman(1979，p.148)的说法，一个(单带)图灵机可以被正式定义为一个七元组  <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> 其中
  −
 
  −
* <math>Q</math> is a finite, non-empty set of ''states'';
  −
 
  −
<math>Q</math> 是一个有限的、非空的状态集。
  −
 
  −
* <math>\Gamma</math> is a finite, non-empty set of ''tape alphabet symbols'';
  −
 
  −
<math>\Gamma</math> 是一个有限的、非空的磁带字母符号集。
  −
 
  −
* <math>b \in \Gamma</math> is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
     −
<math>b \in \Gamma</math> 是空白符号（在计算过程中的任何一步，唯一允许在磁带上无限频繁出现的符号）。
+
==正式定义==
 +
Following Hopcroft & Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple  where
   −
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> is the set of ''input symbols'', that is, the set of symbols allowed to appear in the initial tape contents;
+
* is a finite, non-empty set of ''tape alphabet symbols'';
 +
* is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
 +
* is the set of ''input symbols'', that is, the set of symbols allowed to appear in the initial tape contents;
 +
* is a finite, non-empty set of ''states'';
 +
* is the ''initial state'';
 +
* is the set of ''final states'' or ''accepting states''. The initial tape contents is said to be ''accepted'' by  if it eventually halts in a state from .
 +
* is a partial function called the ''transition function'', where L is left shift, R is right shift. If  is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.
   −
<math>\Sigma\subseteq\Gamma\setminus\{b\}</math> 是输入符号的集合，即允许在初始磁带内容中出现的符号的集合。
+
在Hopcroft & Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q,F⟩，其中：
   −
* <math>q_0 \in Q</math> is the ''initial state'';
     −
<math>q_0 \in Q</math> 是初始状态。
+
<nowiki><math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math></nowiki> where <nowiki><math>\Gamma</math></nowiki>
   −
* <math>F \subseteq Q</math> is the set of ''final states'' or ''accepting states''. ’’’<font color=’’#ff8000’’> The initial tape contents is said to be ''accepted'' by <math>M</math> if it eventually halts in a state from <math>F</math>. </font>’’’
     −
<math>F \subseteq Q</math> 是最终状态或接受状态的集合。’’’<font color=’’#ff8000’’> 如果最初的磁带内容最终在 <math>F</math>的状态下停止，则被称为 <math>M</math>''接受''。 </font>’’’
     −
* <math>\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}</math> is a [[partial function]] called the ''[[State transition system|transition function]]'', where L is left shift, R is right shift. If <math>\delta</math> is not defined on the current state and the current tape symbol, then the machine halts;
     −
<math>\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}</math> 是一个局部函数，称为过渡函数，其中L为左移，R为右移。如果 <math>\delta</math> 在当前状态和当前磁带符号上没有被定义，那么机器就会停止。
      
In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output.
 
In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output.
ZQ
150

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/24657”