数学联邦政治世界观
超小超大

NP猜想(二) (3-1)

为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成:

(1)一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字母表的符号,字母表中有一个特殊的符号“B”表示空白。纸带上的格子从左到右依次被编号为 0,1,2,... ,纸带的右端可以无限伸展。

(2)一个读写头HEAD。该读写头可以在纸带上左右移动,它能读出当前所指的格子上的符号,并能改变当前格子上的符号。

(3)一套控制规则TABLE。根据当前机器所处的状态(相当于当前所执行的指令)以及当前读写头所指的格子上的符号来确定读写头下一步的动作,改变纸带当前格子里面的符号(如需要),并令机器进入一个新的状态(相当于确定下一步要执行的指令)。这个TABLE其实就是一套指令集,它在某种意义上就相当于我们今天计算机里面的程序。它至少包括以下内容:改写当前格子为某个符号、读写头向左或者向右移动一步、确定下一步执行的指令。

为了让大家更容易理解图灵机,举个例子吧。下图就是某个图灵机的一张控制规则TABLE,这个图灵机假设输入是只有“a”和“b”两种字符组成的字符串,它能够判断这个字符串是否是类似“aaabbb”形式的,也就是由同样数量连续个a和连续个b组成的字符串。在图灵机中,“B”表示“空”(Blank),如果后续状态是“Qaccept”或者“Qreject”,则分别表示运行结束且判断结果为“是”或“否”。

当前状态 读B 读a 读b

Q0(写B,右移,Q0) (写B,右移,Q1) (写b,右移,Qreject)

Q1(写B,左移,Q2) (写a,右移、Q1) (写b、右移、Q1)

Q2 (写B、左移、Qreject) (写a.左移Qreject) (写B、左移、Q3)

Q3(写B,左移,Qaccept) (写a,左移,Qreject) (写b,左移,Q4)

Q4 (写B,右移,Q0) (写a,左移,Q4) (写b、左移,Q4)

(4)一个状态寄存器。它用来保存图灵机当前所处的状态,也就是当前需要执行的指令(上图中的Q0~Q4)。

某一些指令运行完毕后,图灵机就进入了“停机状态”,这时纸带上的符号或者“Accept”、“Reject”状态就是本次运行的结果。

图灵设计的这样一台机器能模拟人类所能进行的任何计算过程。不考虑效率的前提下,今天人类的再高端的计算机的程序运算都可以通过图灵机实现。

2、非确定图灵机(NDTM,Non-Deterministic Turing Machine)

非确定图灵机与前面说的图灵机的区别在于,“控制规则TABLE”中的确定的下一步动作不是一个,而是多个。在实际运行过程中,NDTM会随机选择某一个动作继续运行下去,形成一个运行分支。因此,NDTM针对同一个输入,实际运行结果是不确定的。但是有一点需要明确,就是NDTM中不会产生矛盾,某一个输入如果某个分支给出的结果是“接受”,那么无论选择哪一条道路,最终的结果都不会是“拒绝”(这里我们没有排除某种分支下某个NDTM无限运行下去,永不停机的可能)。

3、库克定理证明思路

做了这么多铺垫,我们来开始说库克定理的证明思路。请大家千万别跳过这一部分,这是NPC问题存在的鼻祖式证明。

(1)按照NPC问题的定义,先要证明SAT问题是一个NP问题。

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

一起去骑行吧 连载中
一起去骑行吧
是境啊
我和我做了四年的的同桌一起出去骑行的路上,出现的些有趣的事情
0.0万字9个月前
漂亮炮灰翻车了 连载中
漂亮炮灰翻车了
路楼
简介正在更新
24.7万字9个月前
来自时间 连载中
来自时间
聆风归暮
半失踪状态,欢迎来找我聊天哦,评论必回(QQ:478428304)未经许可不得擅自转载!!!我们生活在一个可控时间的时代,但是当这些时间失去......
17.7万字9个月前
重生女配抢机缘 连载中
重生女配抢机缘
可乐吐司
一朝重生,且看我绽放出万丈光芒!
0.7万字9个月前
颜色拟人:恰似心动的感觉 连载中
颜色拟人:恰似心动的感觉
酸死你c
“哎哎哎?!red息怒息怒哇,下手轻一点,别把blue打死哇”“我当然知道,放心吧!(坏笑)”“你们真是好队友,见死不救”一路上,大家们经历......
2.4万字9个月前
妖界公主升职记 连载中
妖界公主升职记
钟离奈落
听说,妖界公主苏玖玖落落大方,倾国倾城。听说,妖界公主苏玖玖温柔体贴,清纯可爱…事实证明,听说只能是听说,本公主是个能屈能伸的沙雕!本公主摊......
9.5万字9个月前