Automata Theory 简明教程
Non-Deterministic Turing Machine
在非确定图灵机中,对于每个状态和符号,TM 有一组操作。因此,这里的转换不是确定的。非确定图灵机的计算是从开始配置可以到达的一系列配置树。
In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.
如果树至少有一个节点是接受配置,则接受输入,否则不接受。如果计算树的所有分支在所有输入上停止,则非确定图灵机被称为 Decider ,如果对于某个输入,所有分支都被拒绝,则输入也被拒绝。
An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.
一个非确定图灵机可以形式地定义为一个 6 元组 (Q, X, ∑, δ, q0, B, F),其中 -
A non-deterministic Turing machine can be formally defined as a 6-tuple (Q, X, ∑, δ, q0, B, F) where −
-
Q is a finite set of states
-
X is the tape alphabet
-
∑ is the input alphabet
-
δ is a transition function; δ : Q × X → P(Q × X × {Left_shift, Right_shift}).
-
q0 is the initial state
-
B is the blank symbol
-
F is the set of final states