什么是可计算理论

这个学期刚好上这门课,此课绝对是CS课程中的神课,需要一定的决心和耐心才能啃下来。这篇文章可以说是一篇科普文,争求通俗易懂。

可计算理论是计算理论的一个分支,还有两个分支分别是自动机和计算复杂性。

这些名词都顾名思义,自动机讲的是计算的模型,比如图灵机,它是由无限长磁带,读写磁头和一些状态转移序列组成;可计算理论,研究的是一个函数(或程序)是不是能被计算,但是什么叫能被计算呢,比如说给定x,你给我计算出2x,这个函数就是可计算的,那又有什么函数是不可计算的呢?稍后你会看到著名的停机问题,这个程序就是不可计算的;计算复杂性研究的是如何有效地解决问题。

这刚好是计算的三个方面:计算的模型,计算的界限,计算的代价。

现在让我们关注可计算性这个方面。

什么是可计算函数? 如果存在一段程序来计算一个函数,那么这个函数就是可计算的。通俗来讲,你能用编程语言写出来并运行的都是可计算函数,更通俗来讲,你写完程序,在windows下会生成一个exe执行文件,假设打开后会提示你给一个程序的输入,这个程序根据这个输入能计算出相应的结果,可以把这个程序看为一个函数,给定x,输出f(x)。以后你每次想计算f(x),只要运行相同的程序就可以了。处理一类问题有相同的算法,这样的函数叫可计算函数。比如给x,输出x2+6,就是可计算的。

这里需要把程序P和函数f的概念说清楚。如果一个程序P的效果可以和一个函数f的效果一样,也就是说给定x,P(x)=f(x),我们就说P能够计算f。但是他们不是一一对应的关系,即多个程序可以对应同一个f。比如说给定x,输出2x,函数f是唯一确定的,即f(x)=2x,但程序不是确定的,比如我可以给每个程序最后加个不相关赋值语句,程序的输出是不变的,但每个程序都是不一样的。

什么是不可计算函数? 考虑这样一个问题:是否存在一个程序,它能够计算任何程序在给定输入下是否会运行结束? 答案是不存在。这就是著名的停机问题。 现在让我们来证明一下,证明思想相当精妙和精简。 假设这样的函数存在,设为halt(char program, char input),那么这个函数编写出来就是这样的:

1
2
3
4
5
6
7
bool halt(char* program, char* input)  
{  
    if(<program> halts on <input>)  
      return true;  
    else  
        return false;  
}

然后我们考虑这样一个函数,这个函数就像它的程序名一样那么邪恶:

1
2
3
4
5
6
7
void Evil(char *p)  
{  
    if(halt(p,p))  
        while(1);   //forever loop  
    else  
        return;  
}

然后我们考虑Evil(Evil)是否会停机(即Evil这个程序的输入是它本身)。

如果Evil(Evil)会停机,那么必然执行的是else语句里的return,那么if的判定条件为false,那么halt(Evil,Evil)必返回false,即Evil程序不会在Evil输入上停机,而假设是会停机,矛盾。

如果Evil(Evil)不会停机,那么必然执行的if语句里的死循环,所以if的判定条件为true,那么halt(Evil,Evil)必返回true,即Evil程序会在Evil输入上停机,而假设是不会停机,矛盾。

所以它停也矛盾,不停也矛盾,于是得出 halt(char* program, char* input) 这个函数是不存在的。

实际上还有很多函数都是不可计算的。比如, 不存在一个程序,它能够判断任何程序是否是0函数。(0函数就是说对于所有输入输出都是0)。 不存在一个程序,它能够判断任意两个程序是否计算同样的f。

那么是否有一个比较系统的方法来判断哪些函数是不可计算的呢?答案是有的,这就是著名的Rice’s Theorem。这个定理说的是,有一个函数集合B(即这个集合B是函数f的集合),并且B不是空集,也不是全部函数f,那么程序P是否属于B是不可计算的。

什么意思呢,举个形象的例子。比如说你是程序设计这门课的助教。你布置了一个作业,要求学生写一个程序,任意给定x,输出2x。学生马上写完交给你了,你惊奇地发现这门课竟然有200名学生,然后一个偷懒的想法在你脑中诞生了:我是不是能写一个程序,来自动判断学生上交的程序是否满足要求呢?Rice‘s theorem打破了你的幻想,这样的程序是不存在的。

这个例子中,令B包含f(x)=2x这个函数,助教想做的是判断一个程序是否属于这个集合B,Rice‘s theorem告诉我们这样的程序不存在。

除了研究函数的可计算性,可计算理论还关注什么? 实际上,这门课包含的内容远远不止上文这些东西。还有一些很重要的概念,比如: 1. 康托提出的对角线方法; 2. 哥德尔不完备定理也可以通过这门课的后续内容推导出来; 3. 归约的思想,问题难度的划分。 4. 第一和第二递归定理。 这些都是相当美妙,计算理论里相当关注的问题。

本文不可能全部介绍这些概念,如果你有兴趣,请参考Nigel Gutland写的《An introduction to recursive function theory》,写得算比较详细了。

至此,你应该懂了什么是停机问题,什么是可计算函数,什么是不可计算的,作为科普,这些就够了。计算理论本身就是需要钻研才能明白的学科。

这门课可能对找工作的人没有太大帮助,但是它让人体会到了美和伟大。

参考资料:
[1] 《An introduction to recursive function theory》. Nigel Gutland
[2] http://book.douban.com/review/1321006/
[3] 《暗时间》 刘未鹏
[4] http://www.cnblogs.com/lienhua34/archive/2012/03/05/2381296.html

欢迎关注微信公众号
qrcode