非确定型图灵机
非确定型图灵机
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为
formula_1
其中formula_2是状态集合，formula_3是带字母表，formula_4分别表示读写头向左和向右移动；符号formula_5 表示集合formula_6的幂集，即
formula_7
例如，设非确定型图灵机formula_8的当前状态为formula_9，当前读写头所读的符号为formula_10，若
formula_11
则formula_8将"任意地"选择一个formula_13，按其进行操作，然后进入下一步计算。
非确定型图灵机formula_8在输入串formula_15上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称formula_8接受formula_15；只要有任意一个分支进入拒绝状态，则称formula_8拒绝formula_15；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说formula_8在输入formula_15上可停机。注意，我们规定formula_8必须是无矛盾的，即它不能有某个分支接受formula_15而同时另一个分支拒绝formula_15，这样有矛盾的非确定型图灵机是不合法的。
定理：对于任意一个非确定型图灵机formula_8，存在一个确定型图灵机formula_26，使得它们的语言相等，即formula_27。
证明：因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历formula_8的计算树，但这样行不通，因为formula_8的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为迭代加深搜索的技巧来遍历formula_8的计算树。具体证明如下：
对于非确定型图灵机formula_8，构造一个确定型图灵机formula_26如下：
显然，若formula_8有某个分支可以停机，则此formula_26也一定会找到该分支并停机。因此formula_27。
定理2：如果语言L被非确定型图灵机formula_8在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为formula_43的确定型图灵机程序所接受。
定理2说明了为什么在证明P = NP之前，所有的NPC问题都只有指数时间复杂度算法。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.