为造福下要交课程总结（论文）的各位童鞋，特推出课程系列……

对计算理论知识体系的梳理

【摘  要】本文主要针对这学期计算理论课程的一个梳理，从普通的自动机到图灵机，从可判定到不可判定进行相关论述。在可判定问题中着重整理了P问题、NP问题以及NP-Complete问题；而在不可判定问题中主要涉及停机问题，并利用停机问题证明了一个富有哲学意义的命题。

【关键词】图灵机，可判定性，NP问题， P问题， 停机问题

前言

作为20世纪国际七大数学难题之一的P和NP问题源自计算机问题,也完全是一个数学问题，它的意义主要牵涉到密码学、运筹学等多个计算机科学领域。假使某一天能够证明P=NP（虽然大多数的学者猜想他们不相等），那么，整个计算机领域甚至目前的整个人类社会都会为之震撼：例如基于公密钥的加密应用、人工智能领域等等方面都会发生历史性的改变。

计算理论所要研究的也就是可计算性问题。所有的计算问题可分为两类：能用算法解决的和不能用算法解决的；前者虽然在理论上是可计算的，但在现实中，就目前的情况下来看，很多问题都涉及到过度的时间需求，故无法求解；后者则是我们所说的不可计算问题，它们在理论上就是不可计算的。当然，这里所说的可计算与不可计算都是针对图灵机模型所定义的，当前所有计算机的在理论上说，也都是可以被图灵机所模拟的。

有穷自动机、下推自动机和图灵机

图灵机是有Alan Turing所提出的，它主要包括有穷控制器、带和带头等，带头用来在带上进行读或者写。图灵机虽然简陋，但是任何强化它们的尝试都没有获得成功。有个公认观点认为，把“算法”的想法形式化的任何合理方式最终必然等价于图灵机的想法。

如果用所能接受的语言来描述它的计算能力，那么图灵机所能接受的语言就是递归可枚举语言，也就是乔姆斯基所说的0级语言。对于它所说的最弱的3级语言，即正则语言，被有穷自动机就可以接受，而对于上下文无关的语言，可以用下推自动机来接受。

可判定性（计算复杂性和NP完全性）

在可计算问题中，我们用计算复杂性来描述在实际中求解的可行性，这里主要是针对时间复杂度而言。时间复杂度是指当问题的规模足够大时，求解问题的时间增长速度，当然最理想的莫过于O(1)了，也就是常数级时间复杂度。但通常来说，只要是多项式级的时间复杂度都还是可以接受的，即O(1),O(log(n)),O(n^k)等，在这个时间复杂度能解决的问题则称为P类问题；如果不能，例如有很多问题可能需要在O(k^n)和O(n!)的时间复杂度下求解，则认为它们是非多项式级的，现实中的计算机往往难以承受。而通常我们所说的NP问题则是指能在多项式时间内进行认证的问题。例如，在Hamilton回路问题中，要在Hamilton Graph中查找可能很困难，目前只能进行搜索，但要进行认证则完全是可以在多项式时间内进行的，只需要沿着这个回路走下去，看是否覆盖了每个节点即可。因此，很容易想到的就是P类问题属于NP类问题，毕竟在多项式时间内能进行求解的必然也能在多项式时间内进行认证。但最为核心的问题是“P=NP?”。如果这个问题被证明是成立的话，当前所有的NP难题，至少在理论上都是可以在多项式时间内求解的，也就是说，像现在基于大素数相乘公私密钥算法的攻破、经典的TSP问题等等都是可以在现实可接受时间内求解的，这将绝对是一次突破性的变革，多数计算机科学教材都将重写。即便是被证明不成立，人们也就不用再花时间去这里进行过多研究了（虽然很具有诱惑性），这样也就没有那么多必要深入研究NP-Complete问题了。

NP-Complete问题是NP问题中比较特殊的一类。根据定义，它是指所有的NP问题都可以归约到某另一个NP问题，这样的NP问题就是NP-Complete问题。打个比方，如果你能解决一元二次方程，那么用同样的办法也可以求解一元一次方程，你只需要把该二次项系数设置乘0就可以了；以此类推，n次可解了，那么n-1次也是可解了。这样的逐步进行就归约到这样一个问题上，求解它的难度越来越大，但应用面越来越广。例如，TSP问题就可以归约到Hamilton Graph，同时还可以归约到有界铺砖问题上，而有Hamilton Graph和界铺砖问题则是NP-Complete问题。因此可以看到，只要判断任意一个NP-Complete问题是否等于P问题就在事实上等价解决了“P=NP?”。

目前，针对于NP类问题还主要是通过近似算法来求解，笔者也曾写过利用GA（遗传算法）求解TSP问题，效果是还可以。

不可判定性

当然，并不是所有问题都可以被求解（或者说判定），其中最有名和最基本的不可判定问题就是辨别给定的图灵机在给定的输入上是否停机的问题，即图灵机的停机问题。

停机问题的证明思想可以解决很多富有哲学意义的问题，例如曾有人证明这样一个命题：人不能用自己的方法来判定自己方法的有效性。下面我利用停机问题思想来证明，即，假设否命题成立，那么令这个方法为Halt(M,I)，M是方法，I是输入；若M可以判定I有效则返回true，否则输入false。现在再设计如下方法一个新的方法Y：

Y(M): Loop: if Halt(M,M)

then

goto Loop;

                     else

                            return;

当我们用自己的Y方法来判定自己的Y方法是否有效时，出现：（1）如果Y方法有效，由Y(M)可知Halt(Y,Y)为false，即Halt这个方法已经判断它是无效的了，矛盾；（2）如果Y方法有效，即Halt返回的是true，但由Y来看它却进入了死循环，又是矛盾的。因此，可以得出结论就是最初的假设错误，进而得证原命题成立。但也有人反驳人脑不能抽象成图灵机，因此不受该停机模型的限制，这好比没有任何一个编译器能够分辨出代码中的死循环，但一个优秀的程序员却可以看得出。这确实也有道理，或许人工智能领域所提出的生物芯片，基于神经网络的模型也正是试图摆脱图灵机的可计算束缚。当然，对于这些的讨论，还有待于对计算理论的进一步深入研究。