刘未鹏-图灵机杂思(增改版)

那么，既然我们已经从原则上肯定了有些函数是不可计算的，换句话说，有些函数你虽然知道它是函数，但你就是无法用图灵机来将它模拟出来，用今天的话说，就是无法编程实现！这可比较令人沮丧，居然有无法编程实现的函数。那么究竟能否造出这么一个函数来让人瞧瞧怎么个不能编程实现法呢？这就是所谓的Busy Beaver问题。Busy Beaver问题就是要构造这么一个函数，它用于计算任意一个N-state的图灵机的最大“生产率（Productivity）”，生产率的定义就是给一个图灵机一条空纸带，最终当该图灵机halt的时候数纸带上的1的个数，就是其生产率。所有N-state的图灵机的最大生产率就是指一切N状态的图灵机的生产率中的最大者。很显然，这是一个N的函数。记为L(n)。那么问题是，这个L(n)是否是图灵可计算的？答案是不行！用反证法：假设存在这么一个图灵机B，能够模仿L(n)的行为，那么我们将它接到一个特殊的n-state的图灵机I后面（I的作用是在纸带上留下n个1，作为B的输入，可以证明，这样的I是存在的），这样形成一个新的图灵机IB，这个新的图灵机的作用就是计算L(n)，其中n就是I的状态数，也是I的输出，B的输入。我们再在后面接上一个B，得到IBB这么一个图灵机，其效果为L(L(n))。那么现在考虑IBB自身的状态数，是I的状态数（即n）+2倍的B的状态数，假设B的状态数为b（b为有限值），那么IBB的状态数就是n+2b，那么可想而知n+2b状态的图灵机的最大productivity是肯定大于等于L(L(n))的，因为已经有一个图灵机的productivity是L(L(n))了，它就是IBB。这个不等式就是 L(n+2b)>=L(L(n))，由此我们可以推出n+2b>=L(n)（L(i)>=L(j)=>i>=j这一结论易证），又根据n的任意性，我们可以令其等于n+11，于是得 n+11+2b>=L(n+11)，而我们知道11状态可以实现出一个将纸带上的1的数目翻倍的这样一个图灵机（试试看吧:)很简单），于是L(n+11)>=2n（只要把前面的n状态用于一个产生n个1的图灵机，后面的11状态做成一个翻倍1的数目的图灵机即可），于是得到n+11+2b>=2n，于是得到11+2b>=n。根据n的任意性，b的有限性，这就得到了矛盾！（其实这里还隐含着另一层意思，即要实现这么一个图灵机，必须要有无穷多个状态才行，即b要任意大，而根据图灵机的定义，b是有限的）。

说到这里，想起还有一个经典的函数也是图灵不可计算的。上面已经提到，所有图灵可计算的实数所构成的集合是一可列集，记为S={s|s为图灵可计算的}（这是因为所有图灵机构成的集合是可列集），现构造这样一个函数f，使得f(j,i)=Sj(i)；其中Sj就是S中的以j为下标的元素,Sj(i)则是指Sj的第i位的值。我们断言这样一个f就是图灵不可计算的。欲证明这一点，我们假设存在一个图灵机P，满足P(j,i)=Sj(i)。现使用对角线法构造出一个新的不属于集合S的实数r，r满足：

我们发现，只要P存在，那么r就也是图灵可计算的，而这又跟r不属于S是矛盾的，所以推出“P不存在”这一结论。（注：为什么只要P存在r就也是图灵可计算的呢？这样想，我们构造一个新的图灵机Q，使满足：

这么个新的图灵机Q，只要喂给它一个下标i，就会吐出r的第i位，于是r就成了图灵可计算的了。

Church-Turing Thesis大意就是说，在所有以自然数为定义域的函数中，只有那些递归函数（这里递归函数也包括有限步骤的函数）才是图灵可计算的。这一结论界定了图灵机的计算能力。乃是非常重要的。其实想想也很直观，一个无穷不循环的函数自然需要无穷多个状态才能计算了。而一个图灵机的状态是有限的，在这个有限空间中转来转去最终肯定是坠入循环，这就好像两整数相除一样，要么除尽，要么无限循环小数，用鸽弄原理可以很容易地证明。

来简单说说C++ Template的图灵完备性（turing-complete，更准确地说是turing-equivalent，因为turing-complete一般是指一个问题是turing-computable的）。要想证明一门语言的图灵完备性从原则上来说就是要证明它可以解决图灵可计算的所有问题。或者构造出一种转换途径，能够把任何图灵可计算问题的解决方法转换为这门语言的程序。但这里还有一个更取巧的方法，用这门语言实现一个Universal Turing Machine（其实差不多就是有限状态机啦）。C++ Template就可以做到这一点，实际上这早已有人做过了。另外，一般来说一门语言只要有if判断，递归或循环结构以及最基本的赋值能力和四则运算就是图灵完备的了，而C++ Template恰巧这些都具备，其中if判断和递归结构是借助模板偏特化能力实现的，估计语言的设计者当初也没有料到这一点会给现代C++带来这么大的影响:)

另外，严格来说，现今任何计算机其实都不是turing-equivalent的，因为它们的内存是有穷的。而图灵机的内存则是潜无穷的。只不过只要不出现内存不耗尽的情况都一样啦:)

前面提到的constructive mathematics和intuitive logic不属于图灵机的内容，有空再写吧。