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），接着再看更方便。