150
个编辑
更改
跳到导航
跳到搜索
第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'';+ − * 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⟩，其中：
→正式定义
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
在Hopcroft和Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：
* Г是有限的、非空的纸带''字母符号集''；
* Г是有限的、非空的纸带''字母符号集''；