中财网80婚约演员:非确定性图灵机
来源：百度文库 编辑：中财网 时间：2024/05/07 16:43:50
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机 的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为 止。
定理：对于任意一个非确定型图灵机M，存在一个确定型图灵机M'，使得它们的语言相等，即L(M) = L(M')。
定理2：如果语言L被非确定型图灵机M在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为O(2P(n))的确定型图灵机程序所接受。
定理2说明了为什么在证明P = NP之前，所有的NPC问题都只有指数时间复杂度算法。
在（确定性）图灵机计算模型下，有一类问题的计算复杂性至今未知。为此，提出能力更强的计算模型——非确定性图灵机计算模型，NDTM（Nondeterministic Turing Machine）。在该计算模型下，许多问题可在多项式时间内求解。
k带非确定性图灵机M的形式化描述：一个7元组（Q, T, I, δ, b, q0, qf），与确定性图灵机不同的是，其允许转移函数δ具有不确定性。即对于Q*Tk中的每个元素(q, x1, x2, …, xk)，当它属于δ的定义域时，(Q*（T*{L，R，S})k中有唯一的子集δ(q, x1, x2, …, xk)与之对应。我们可以在δ(q, x1, x2, …, xk)中任意选择一个作为其函数值。
非确定性图灵机的时间复杂性T(n)
非确定性图灵机的空间复杂性S(n)
确定性图灵机和非确定性图灵机的区别。
a) DTM每步只有一个选择，而NDTM每步有多个选择。NDTM的计算能力远强于DTM。
b) 对于一台时间复杂性为T(n)的非确定性图灵机，可以用一台时间复杂性为O(CT(n))的确定性图灵机模拟，其中C为常数。即对于一台时间复杂性为T(n)的非确定性图灵机M，可以找到一个常数C和一台确定性图灵机M’，使得二者可接受的语言相同，且M’的时间复杂性为O(CT(n))。