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

查看原文

C++ Template是图灵完备（turing-complete，或者更确切的说，是图灵等价（turing-equivalent））的，关于这一点是没什么悬念的，只是前几天有位朋友问到为什么说C++ Template是图灵完备的，为了找出当初的连接，于是又去搜了一下wiki和standford encyclopaedia，谁之这一搜之下又带出了一大堆内容，于是又花了好几个时辰将图灵机的相关理论复习了一遍，顺便以四十五度角仰视了一下Alan Turing的生平，神奇的是在追寻链接和搜索的过程中居然翻到了一篇关于constructive mathematics以及一篇关于Intuitionistic Logic的东东，那是后话，占且不提。先来说说C++ Template和图灵机。

图灵机是图灵为了研究可计算问题而构思的一个理论装置，你只要想一想有限状态机就可以大概知道图灵机是个什么概念了，只不过图灵机的内存（纸带）是潜无穷的（也就是可以任意长啦，“潜无穷”是古稀蜡人的说辞）。图灵机的定义形象的说来就像老式的电传机：一个读写头，一根纸带（可能任意长），读写头不断读取纸带上的符号，并根据内在的状态转换规则转换当前状态，同时进行一些动作，譬如插除或改写当前字符，向前/向后移动读写头或保持不动等。至于其抽象的定义大抵就是有限状态机的定义了。图灵机的这一定义现在我们看起来似乎是很显然的，然而当时却代表着一种思想上的革命，一种从无到有。图灵机实质上抽象出了我们平素进行机械式计算的核心规律，所以才等价于“一个人+纸笔+一定的规则”进行机械运算呢。这么个理论机器首先就指明了创建计算机的可能性，然而这还不够，如果为了某一个问题就去创建一个特定的图灵机的话效率就太低了。图灵机理论的一个最美妙的结论就是存在“元图灵机（Universal Turing-Machine，直译应为一般图灵机/通用图灵机，然而“元图灵机”更精确地表达了其意思），所谓元图灵机其实就是把图灵机作为运算对象的图灵机，假设有一个元图灵机M，一个图灵机P以及P的输入数据D，那么将(P,D)喂给元图灵机M，M就能够吐出P(D)（即P在D上的结果）。而这便是现在我们所用的计算机的始祖模型，其中M就好比我们的计算机（元图灵机），P则是程序（编码后的图灵机），D则是程序P的输入数据。元图灵机的存在表明了我们可以用一台机器来解决所有图灵可计算（turing-computable）的问题——只要喂给它解决这个特定问题的图灵机编码（程序）以及问题的输入数据即可，该元图灵机就会模拟我们喂给它的那个图灵机P的行为，最终给出结果。元图灵机的存在性为计算机的诞生点燃了一盏明灯，这是图灵机理论中最漂亮的发现。

关于图灵机还有两个有名的Halt Problem和Busy Beaver Problem，不过前者更有名，但没有后者有意思，所以具体就不说了，可以google。这两个问题说明了图灵机并不是“万能”的，它只能解决可以“机械地”解决的问题，只不过这个“机械地”定义太过含糊，没有准确地界定，所以有必要精确定义一下图灵机到底能解决哪些问题，换句话说，到底哪些问题是图灵可计算的。这里有一个非常漂亮的证明，是关于哪些数是图灵可计算的，说有无穷多个实数是图灵不可计算的。首先说明一下一个数是图灵可计算的是个什么概念，一个数是图灵可计算的就是说存在一个图灵机，给它一个空纸带，最终它能打印出任意逼近该数的结果。像pi、自然常数E以及所有多项式的根就都是图灵可计算的（可由机械步骤任意逼近），这很好理解，因为我们可以写一个程序来迭代任意逼近它们，譬如E就是一个无穷级数的和。但还有其它实数呢？有没有图灵不可计算的实数？要想弄明白这个问题，先要考虑一共存在多少个图灵机（废话，当然是无穷多个了，但“无穷多”也有一个级别问题J），为此先将图灵机进行编码，由于图灵机的状态是有限的，将图灵机编码为一个五元组（5-tuple）（Old_State,Symbol,New_State,New_Symbol,Move）的序列（或更多/更少都有可能，这是比较常见的一种编码方式，但总之一定是N-TUPLE，N有限），那么我们来考虑一个N-state(N个状态)，M-symbol的图灵机一共有多少种可能，为此，先考虑对应N-state、M-symbol的5-tuple（见上面的定义）有多少个，根据简单的排列组合规律，一共是N*M*N*M*3（最后一个3是指Move的可能性——静止/向前/向后），换句话说，也就是以M,N为参数的一个upper-bounded function。OK，现在来考虑一个图灵机的编码形式，一个图灵机其实就是由一集5-tuple所构成，所以既然N-state,M-symbol的5-tuple一共有N*M*N*M*3个，换句话说，这个由所有可能的5-tuple所构成的集合中一共有N*M*N*M*3个元素，那么这个集合的所有子集合的个数也就是N-state,M-symbol的所有图灵机的个数，根据幂集的定义，这也就是2N*M*N*M*3个。这里为了简单起见，我们暂且固定M为M­­0，即symbol的个数，这样所有M0-state的图灵机的个数就是:

21*M0*1*M0*3+22*M0*2*M0*3+23*M0*3*M0*3+… =。

现在我们看到，这个和式的每一项都是coutable的，而Z＋×Z＋尚且是可列集，就别说这里每项都有限的情况了，所以很容易就可以和Z＋建立起单射(injective)，换句话说，所有M0-state的图灵机的集合是一个可列集。好了，现在把M0换成变量，既然所有M0－state的图灵机集合都是可列的，而M0又是自然数（可列集），再加上“可列集个可列集”仍然是可列集这一性质，就容易得出一切图灵机构成的集合是可列集这一结论了。

注：其实证明一切图灵机所构成的集合的可列性还有一种更简单但取巧一点的办法：我们知道计算机语言是图灵等价的，所以讨论“一切图灵机”其实相当于讨论“一切计算机程序”，而从二进制层面来看，一个计算机程序可以被看成0和1的序列，基于这种表示，“一切计算机程序”所成集合的势也就呼之欲出了，因为 “一切计算机程序”=“所有长度为1的计算机程序”+“所有长度为2的计算机程序”+“所有长度为3的计算机程序”+…。把“所有长度为i的计算机程序”所成集合记为Si，“一切计算机程序”所成集合记为S，立即有：;以及。我们记Si中的第j个元素为Si(j)，那么很容易就可以建立S跟Z＋之间的injective function（单射），只须令f: Si(j)->2i3j;显然f就是injective的。这就证明了S的可列性质。

那么，这一结论有什么重要意义呢？非常重要，我们知道，实数集是不可列的，其势（或称“基”）为阿列夫1（而Z，即整数集的势则是阿列夫0），所以即便耗尽所有图灵机仍然还是会有“列不出”的实数。要想严格证明这一点也很简单，只要运用cantor在证明集合论时运用的经典的“对角线”手法，不妨简单描述一下：

首先，既然所有图灵机的集合是一可列集，我们就可以用M0,M1,M2,…来表示它们。现在假设Mi能计算出的实数为Ai0.Ai1Ai2Ai3…。那么我们构造一个新的实数B=B0.B1B2B3...，使其满足B1≠A11,B2≠A22,B3≠A33,…,Bn≠Ann。这样构造出来的一个实数B可以保证不与任何Ai相等，同时这个B并不为任何图灵机所计算出来（因为刚才的Ai序列已经耗尽了所有的图灵机）。这某种程度上就表明图灵机的势为阿列夫0（尽管对图灵机并不能称“势”）。

除此之外，函数空间的所有函数也并不都是图灵可计算的，一个函数为图灵可计算其实就代表存在一个图灵机可以模拟该函数的行为。这一结论通过刚才的证明就很好解释了：因为函数空间的势为阿列夫2，比实数集还要大，怎么可能由图灵机来枚举尽呢？要证明也很简单，同样是对角线法，就不说了。