更改

删除1,045字节 、 2021年7月28日 (三) 16:31
第101行: 第101行:  
机器的每一部分(即它的状态、符号收集和在任何特定时间使用的纸带)和它的行动(如打印、擦除和纸带运动)都是有限的、离散的和可区分的;是无限的纸带和运行时间给了它无限制的存储空间。
 
机器的每一部分(即它的状态、符号收集和在任何特定时间使用的纸带)和它的行动(如打印、擦除和纸带运动)都是有限的、离散的和可区分的;是无限的纸带和运行时间给了它无限制的存储空间。
   −
==正式定义==
  −
Following Hopcroft & Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple  where
     −
* is a finite, non-empty set of ''tape alphabet symbols'';
+
在Hopcroft和Ullman之后,单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩,其中:
* 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.
  −
 
  −
在Hopcroft & Ullman之后,单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩,其中:
      
* Г是有限的、非空的纸带''字母符号集'';
 
* Г是有限的、非空的纸带''字母符号集'';
150

个编辑