非确定型图灵机 Non-deterministic Turing machine

（重定向自Nondeterministic Turing machine）

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为

其中 $Q$ 是状态集合， $\Gamma$ 是带字母表， $L, R$ 分别表示读写头向左和向右移动；符号 $2^{A}$ 表示集合 $A$ 的幂集，即

例如，设非确定型图灵机 $M$ 的当前状态为 $q$ ，当前读写头所读的符号为 $x$ ，若

则 $M$ 将任意地选择一个 $(q_i, x_i, d_i)$ ，按其进行操作，然后进入下一步计算。

非确定型图灵机 $M$ 在输入串 $\omega$ 上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称 $M$ 接受 $\omega$ ；只要有任意一个分支进入拒绝状态，则称 $M$ 拒绝 $\omega$ ；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说 $M$ 在输入 $\omega$ 上可停机。注意，我们规定 $M$ 必须是无矛盾的，即它不能有某个分支接受 $\omega$ 而同时另一个分支拒绝 $\omega$ ，这样有矛盾的非确定型图灵机是不合法的。

单词	Nondeterministic Turing machine
释义	Nondeterministic Turing machine 中文百科非确定型图灵机 Non-deterministic Turing machine （重定向自Nondeterministic Turing machine）如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为其中 $Q$ 是状态集合， $\Gamma$ 是带字母表， $L, R$ 分别表示读写头向左和向右移动；符号 $2^{A}$ 表示集合 $A$ 的幂集，即例如，设非确定型图灵机 $M$ 的当前状态为 $q$ ，当前读写头所读的符号为 $x$ ，若则 $M$ 将任意地选择一个 $(q_i, x_i, d_i)$ ，按其进行操作，然后进入下一步计算。非确定型图灵机 $M$ 在输入串 $\omega$ 上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称 $M$ 接受 $\omega$ ；只要有任意一个分支进入拒绝状态，则称 $M$ 拒绝 $\omega$ ；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说 $M$ 在输入 $\omega$ 上可停机。注意，我们规定 $M$ 必须是无矛盾的，即它不能有某个分支接受 $\omega$ 而同时另一个分支拒绝 $\omega$ ，这样有矛盾的非确定型图灵机是不合法的。英语百科 Non-deterministic Turing machine 非确定型图灵机（重定向自Nondeterministic Turing machine） In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', change it to 'B' and move left."
随便看	dolichos lablab l. var purpureus的意思 dolichos lablabs的意思 Dolichos lablab yellow mosaic virus的意思 Dolichos lignosus的意思 dolichos lignosuss的意思 Dolichosoma的意思 dolichosporous的意思 Dolichos rhombifolius的意思 dolichoss的意思 Dolichos sinensis的意思 Dolichos sinensis L.的意思 Dolichos soja的意思 dolichostachya的意思 dolichostachyum的意思 dolichostenomelia的意思 Dolichos tenuicaulis的意思 Dolichos thorelii的意思 Dolichos trilobus的意思 dolichostylous的意思 dolichostylous pistil的意思 dolichos uniflorus lamk.的意思 dolichotetranychus floridanus的意思 Dolichothoraci的意思 Dolichothoracomorpha的意思 Dolichotis的意思

Nondeterministic Turing machine

非确定型图灵机 Non-deterministic Turing machine

Non-deterministic Turing machine 非确定型图灵机