什么是可计算理论

这个学期刚好上完这门课，此课绝对是CS课程中的神课，需要一定的决心和耐心才能啃下来。

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

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

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

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

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

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

什么是不可计算函数？
考虑这样一个问题：是否存在一个程序，它能够计算任何程序在给定输入下是否会运行结束？
答案是不存在。这就是著名的停机问题。
现在让我们来证明一下，证明思想相当精妙和精简。
假设这样的函数存在，设为halt(char* program, char* input)，那么这个函数编写出来就是这样的：
bool halt(char* program, char* input)
{
     if(<program> halts on <input>)
          return true;
     else
          return false;
}
然后我们考虑这样一个函数，这个函数就像它的程序名一样那么邪恶：
void Evil(char *p)
{
     if(halt(p,p))
          while(1); //死循环
     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》，写得算比较详细了。

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

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