| 第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⟩，其中：
| |
| | | | |
| | * Г是有限的、非空的纸带''字母符号集''； | | * Г是有限的、非空的纸带''字母符号集''； |