计算理论 Theory of Computation

Presentation on theme: "计算理论 Theory of Computation"— Presentation transcript:

1 计算理论 Theory of Computation
Qilong Han College of Computer Science and Technology Harbin Engineering University

2 图灵机与计算问题 如何理解图灵机？ 计算 模拟 万能图灵机（通用图灵机） 停机问题

3 图灵机与计算问题 如何理解图灵机？ 小虫的比喻 如何理解图灵机模型

4 如何理解图灵机——小虫的比喻 假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？
首先，我们需要对小虫所在的环境进行建模。 另外，我们当然还需要为小虫建立输出装置，也就是说它能够动起来。 首先，我们需要对小虫所在的环境进行建模。 我们不妨就假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。很显然，这个小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息，我们不妨把模型简化，假设它仅仅具有一个感觉器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。 另外，我们当然还需要为小虫建立输出装置，也就是说它能够动起来。我们仍然考虑最简单的情况：小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。 仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则，这就是程序！

5 如何理解图灵机——小虫的比喻 假设我们记小虫的输入信息集合为I={黑色，白色}，它的输出可能行动的集合就是：O={前移，后移}，那么程序就是要告诉它在给定了输入比如黑色情况下，它应该选择什么输出。因而，一个程序就是一个从I集合到O集合的映射。我们也可以用列表的方式来表示程序，比如： 程序1： 输入 输出 黑色 前移 白色 后移 这个程序非常简单，它告诉小虫当读到一个黑色方格的时候就往前走一个方格，当读到一个白色方格的时候就后退一个格。

6 如何理解图灵机——小虫的比喻 我们不妨假设，小虫所处的世界的一个片断是：黑黑黑白白黑白……，小虫从左端开始。
那么小虫读到这个片断会怎样行动呢？它先读到黑色，然后根据程序前移一个方格，于是就会得到另外一个黑色信息，这个时候它会根据程序再次前移一个方格，仍然是黑色，再前移，这个时候就读到白色方格了，根据程序它应该后退一个格，这个时候输入就是黑色了，前移，白色，后移……，可以预见小虫会无限的循环下去。

7 如何理解图灵机——小虫的比喻 然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个最简单的模型。
首先，我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身造成影响，因而改变这个世界。比如虫子看到旁边有食物，它就会把那个东西吃掉了。在我们这个模型中，也就相当于我们必须假设小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O={前移，后移，涂黑，涂白}。这个时候，我们可以把程序1改为比如：

8 如何理解图灵机——小虫的比喻 程序2： 输入 输出 黑 前移 白 涂黑
输入 输出 黑 前移 白 涂黑 纸带是黑黑白白黑……，小虫会怎样行动呢？下面的图表示出了这个例子中每一步小虫的位置（标有圆点的方格就是小虫的当前位置），以及纸带的状况。 开始：小虫在最左边的方格，根据程序的第一行，读入黑色应该前移。

9 如何理解图灵机——小虫的比喻 小虫的动作还会持续下去……。我们看到，小虫将会不停的重复上面的动作不断往前走，并会把所有的纸带涂黑。

10 如何理解图灵机——小虫的比喻 如果你给它固定的输入信息，它都会给你固定的输出信息！因为我们知道程序是固死的，因此，每当黑色信息输入的时候，无论如何它都仅仅前移一个方格，而不会做出其他的反应。它似乎真的是机械的！ 进一步更改小虫模型，那么它就会有所改进，至少在给定相同输入的情况下，小虫会有不同的输出情况。这就是加入小虫的内部状态！ 假设黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会感觉到自己饥饿了。因而，我们说小虫具有两个内部状态，并把它内部状态的集合记为：S={饥饿，吃饱}。这样小虫行为的时候就会不仅根据它的输入信息，而且也会根据它当前的内部状态来决定它的输出动作，并且还要更改它的内部状态。而它的这一行动仍然要用程序控制，只不过跟上面的程序比起来，现在的程序就更复杂一些了，比如： 程序3：

11 如何理解图灵机——小虫的比喻 程序3： 输入 当前内部状态 输出 下时刻的内部状态 黑 饥饿 涂白 吃饱 黑 吃饱 后移 饥饿
输入 当前内部状态 输出 下时刻的内部状态 黑 饥饿 涂白 吃饱 黑 吃饱 后移 饥饿 白 饥饿 涂黑 饥饿 白 吃饱 前移 吃饱 这个程序复杂多了，有四行，原因是你不仅需要指定每一种输入情况下小虫应该采取的动作，而且还要指定在每种输入和内部状态的组合情况下小虫应该怎样行动。

12

13

14 如何理解图灵机——理解图灵机模型 小虫的行为比以前的程序复杂了一些。尽管从长期来看，它最后仍然会落入机械的循环或者无休止的重复。然而这从本质上已经与前面的程序完全不同了，因为当你输入给小虫白色信息的时候，它的反应是你不能预测的！它有可能涂黑方格也有可能前移一个。当然前提是你不能打开小虫看到它的内部结构，也不能知道它的程序，那么你所看到的就是一个不能预测的满地乱爬的小虫。如果小虫的内部状态数再增多呢，那么它的行为会更加的不可预测！ 好了，如果你已经彻底搞懂了我们的小虫是怎么工作的，那么你已经明白了图灵机的工作原理了！因为从本质上讲，最后的小虫模型就是一个图灵机！

15 如何理解图灵机——理解图灵机模型 这样的模型太简单了！他根本说明不了现实世界中的任何问题！下面，我就要试图说服你，图灵机这个模型是伟大的！
其实我们每一个会决策、会思考的人就可以被抽象的看成一个图灵机。

16 如何理解图灵机——理解图灵机模型 为什么可以做这种抽象呢？首先我们可以考虑扩展刚才说的小虫模型。因为小虫模型是以一切都简化的前提开始的，所以它的确是太太简单了。然而，我们可以把小虫的输入集合、输出行动集合、内部状态集合进行扩大，这个模型就一下子实用多了。首先，小虫完全可以处于一个三维的空间中而不是简简单单的纸带。并且小虫的视力很好，它一下子能读到方圆500米的信息，当然，小虫也可以拥有其他的感觉器官，比如嗅觉、听觉等等，而这些改变都仅仅是扩大了输入集合的维数和范围，并没有其他更本质的改变。同样道理，小虫可能的输出集合也是异常的丰富，它不仅仅能移动自己，还可以尽情的改造它所在的自然界。进一步的，小虫的内部状态可能非常的多，而且控制它行为的程序可能异常复杂，那么小虫会有什么本事呢？这就很难说了，因为随着小虫内部的状态数的增加，随着它所处环境的复杂度的增加，我们正在逐渐失去对小虫行为的预测能力。但是所有这些改变仍然没有逃出图灵机的模型：输入集合、输出集合、内部状态、固定的程序！就是这四样东西抓住了小虫信息处理的根本。

17 图灵机与计算问题 计算 神马是计算 计算的组合 征服无限的方法！ 归纳

18 计算——神马是计算 图灵机和计算有什么关系？
而实际上，图灵机是一个理论计算机模型，它最主要的能耐还是在于计算上！所以，下面我们就来看看什么是计算！ 广义上讲，一个函数变化如把x变成了f(x)就是一个计算！如果我们把一切都看作是信息，那么更精确的讲，计算就是对信息的变换！如果采用这种观点，你会发现，其实自然界充满了计算！ 如果我们把一个小球扔到地上，小球又弹起来了，那么大地就完成了一次对小球的计算。因为你完全可以把小球的运动都抽象成信息，它无非是一些比如位置、速度、形状等等能用信息描述的东西嘛，而大地把小球弹起来就无非是对小球的这些信息进行了某种变换，因而大地就完成了一次计算！你可以把整个大地看作是一个系统，而扔下去的小球是对这个系统的输入，那么弹回来的小球就是该系统的输出，因而也可以说，计算就是某个系统完成了一次从输入到输出的变换！

19 计算——神马是计算 这样理解不要紧，你会发现，现实世界到处都是计算了！因为我们完全可以把所有的自然界存在的过程都抽象成这样的输入输出系统，所有的大自然存在的变量都看作是信息，因而计算无处不在！也的确，正是采取了这样的观点，国外才有可能发明什么DNA计算机、生物计算机、量子计算机这些新鲜玩艺！因为人家把DNA的化学反应、量子世界的波函数变换都看作是计算了，自然就会人为地把这些计算组合起来构成计算机了。然而，似乎我们的理论家们还在力图证明关于图灵机的某个定理呢，却完全没有意识到计算其实就是这样简单！

20 计算——神马是计算 下面回到图灵机！为什么说图灵机是一个计算的装置呢？
很简单，图灵机也是一个会对输入信息进行变换给出输出信息的系统。比如前面说的小虫，纸带上的一个方格一个方格的颜色信息就是对小虫的输入，而小虫所采取的行动就是它的输出。不过这么看，你会发现，似乎小虫的输出太简单了。因为它仅仅就有那么几种简单的输出动作。然而，不要忘了，复杂性来源于组合！虽然每一次小虫的输出动作很简单，然而当把所有这些输出动作组合在一起，就有可能非常复杂！比如我们可以把初始时刻的纸带看作是输入信息，那么经过任意长的时间比如说100年后，小虫通过不断的涂抹纸带最后留下的信息就是输出信息了。那么小虫完成的过程就是一次计算。事实上，在图灵机的正规定义中，存在一个所谓的停机状态，当图灵机一到停机状态，我们就认为它计算完毕了，因而不用费劲的等上100年。

21 计算——计算的组合 更有意思的是，我们可以把若干个计算系统进行合并构成更大的计算系统。
比如还是那个小球吧，如果往地上放了一个跷跷板，这样小球掉到地上会弹起这个跷跷板的另一端，而跷跷板的另一边可能还是一个小球，于是这个弹起的小球又会砸向另一个跷跷板……。 我们自然可以通过组合若干图灵机完成更大更多的计算，如果把一个图灵机对纸带信息变换的结果又输入给另一台图灵机，然后再输入给别的图灵机……，这就是把计算进行了组合！也许你还在为前面说的无限多的内部状态，无限复杂的程序而苦恼，那么到现在，你不难明白，实际上我们并不需要写出无限复杂的程序列表，而仅仅将这些图灵机组合到一起就可以产生复杂的行为了。

22 计算——计算的组合 有了图灵机的组合，我们就能够从最简单的图灵机开始构造复杂的图灵机。那么最简单的图灵机是什么呢？我们知道最简单的信息就是0和1，而最简单的计算就是对0或1进行布尔运算。而布尔运算本质上其实就三种：与、或、非。从最简单的逻辑运算操作最简单的二进制信息出发我们其实可以构造任意的图灵机！这点不难理解：任何图灵机都可以把输入、输出信息进行01的编码，而任何一个变换也可以最终分解为对01编码的变换，而对01编码的所有计算都可分解成前面说的三种运算。也许，现在你明白了为什么研究计算机的人都要去研究基本的布尔电路。奥秘就在于，用布尔电路可以组合出任意的图灵机！

23 计算——征服无限的方法 回忆你小时候是如何学会加法运算的。刚开始的时候，你仅仅会死记硬背。比如你记住了1+1=2，记住了2+4=6，……。然而无论你记住多少固定数字的运算，你都不叫学会了加法。原因很简单，假如你记住了n对数的加法，那么我总会拿出第n+1对数是你没有记住的，因此你还是不会计算。原则上。自然数的个数是无穷的，所以任何两个数的加法可能结果也是无穷的，而如果采用死记硬背的方法，我们头脑怎么可能记住无穷数字的计算法则呢？但是随着年龄的增长，你毕竟还是最终学会了加法运算！说来奇怪，你肯定明白其实加法运算并不需要记住所有数字的运算结果，而仅仅需要记住10以内的任意两个数的和，并且懂得了进位法则就可以了。

24 计算——征服无限的方法 这个计算加法的方法能够让你找到运用有限的规则应对无限可能情况的方法！
规则、元规则我们人似乎总能在一些个别的事件中归纳出规则。 机器可以归纳么？这就相当于说：可以为归纳方法编出程序么？这也是一个很有趣的问题，下面将要详细讨论！可以设想，假如我们找到了真正归纳的方法，那么编写出这样的程序，它就会一劳永逸的自己进行学习归纳了。我们完全再也不用给他编制程序和规则了。这正是人工智能的终极目标！

25 计算——归纳 《倚天屠龙记》——武林泰斗张三丰——“太极拳”传授给——张无忌。
张无忌之所以能学会太极拳，正是因为他已经能够从具体的一招一式之中抽象出了更高一层次的武学规律，因而，当他把所有的有形的武功招数都忘记的时候，已经掌握了太极拳的精髓。而太极武功讲究的就是借力打力，以柔克刚。说白了就是事先并没有固定招式存在，而等到敌人向我进攻的时候我再动态的生成破解的招术。

26 计算——归纳 用到图灵机模型中，我们不难发现，如果把具体的武功招术比喻成一些输入，而应对招术比喻成图灵机的输出，那么太极所讲究的借力打力、以柔克刚的方法其实就是类似的图灵程序！因而张无忌学太极拳的过程就是从特殊的输入输出提升到了一般的算法的过程。也可以说，张无忌运用了归纳学习法！ 自动的从若干个具体事例中归纳出一般的通用规律来 计算机能不能具有真正的归纳能力呢？ 如果计算机能自动归纳，也就意味着我们可以为归纳方法来编写一段程序P。这个程序可以理解为输入的是一些特殊的数对，输出的是能够生成这些数对的程序。也就是说输入具体的“招术”，输出的是这些“招术”的一般规律。

27 计算——归纳 如果说程序P真正可以自己归纳，那么P就必然可以归纳出所有的规律。我们已经讨论过了，其实任何一个程序都能够被看作是对输入的一个变换而得到输出。那么程序P自然也是。假设这些对(a,b),(c,d),(e,f),……都是程序P的输入输出对，那么我们挑选出前1000个（总而言之是足够多的对）。把这1000个特殊情况输入到P中，那么P就应该能够产生这些对子的共性，也就是P自己这个程序了！换句话说，程序P产生了它自己，P自己把自己给归纳出来了！这似乎陷入了怪圈之中！另外，我们人类设计出来P，如果P可以归纳所有的规律，那么P能否也能归纳出“人归纳P”本身这个规律呢？仍然是怪圈问题！这样的问题似乎还有很多。反过来讲，如果假设归纳出所有规律的程序P不存在，那么为什么我们人类总能归纳出规律呢？什么样的具体问题是可归纳的，什么问题是不可归纳的？然而这些看起来非常重要的问题在目前还没有统一的答案！

28 计算——归纳 我们还将会看到很多问题都涉及到逻辑中的怪圈，而由于计算理论已经触及了逻辑、信息的根本，所以把一些问题引向逻辑怪圈并不奇怪。

29 图灵机与计算问题 模拟 神马是模拟？ 图灵机之间的模拟 计算等价性 意义

30 模拟——神马是模拟 什么是模拟？ 又是一个基本的问题，爱因斯坦说过，越是基本的概念就越是难以刻画清楚。模拟这个概念就是一个很难说清的问题。
如果你站在一个朋友面前，冲着他做了一些鬼脸。那么他也会学着你的动作冲你做鬼脸，那么他就对你进行了模拟。 很明显，在你和你朋友之间存在着一系列的对应关系：你的手对应他的手，你的眼睛对应它的眼睛，你的嘴巴对应他的嘴巴……。而且你的手、眼睛、嘴巴做出来的动作也会对应他的手、眼睛、嘴巴做出来的动作。因而，模拟的关键是对应！如果集合A中的元素可以完全对应B中的元素，那么A就可以模拟B。

31 模拟——神马是模拟 什么是模拟？ 仍然用你冲你的朋友做鬼脸的例子，假如这次你做出的鬼脸以及动作没有被他立即模仿而是被他用某种符号语言记录到了日记本上了。比如：“X年X月X日，疯子XX冲我做了一个鬼脸：他伸出了左手食指放到了右眼下面往下拉他脸上的肉，并且吐出了他长长的舌头！”。过了N多天后，你的这位朋友掏出了日记本，按照上面的描述冲着大家做了这个鬼脸。很显然他仍然模拟了你当时的动作。那么，你朋友日记本上的那段对话描述是不是对你鬼脸动作的模拟呢？

32 模拟——神马是模拟 似乎答案是否，因为这段文字跟你没有半点相像。
然而你的朋友正是根据这段描述才做出了对鬼脸动作的模拟。也就是说，他把那段文字翻译成了他的动作，而他这个动作就是对你的模拟。这个翻译的过程很显然就是某种信息的变换，我们完全可以把它理解为一个计算的过程，也就是可以用图灵机来实现的算法过程。所以，我们说日记本上的那段指令也构成了对你鬼脸动作的模拟，原因是这些信息也与你的鬼脸动作构成了对应。具体的，我们可以用下面的图表示：

33 模拟——神马是模拟 A是你的鬼脸动作，B是你朋友做出来的鬼脸动作，C是日记本上的描述。
你朋友的动作B模拟了你的动作A，而B的动作信息是通过执行C上的描述得到的，也就是说存在着一个从C到B上信息的变换。这样我们认为C也对A进行了模拟。

34 模拟——图灵机之间的模拟 一台图灵机包括：输入集合I，输出集合O，内部状态集合S，程序规则表T四个要素。那么如果两个图灵机之间的这些元素都存在刚才说的对应关系，就认为两个图灵机可以相互模拟了。然而图灵机的功能是完成对输入信息进行变换得到输出信息的计算。我们关心的也仅仅是输入输出之间的对应关系。因而一台图灵机A如果要模拟B并不一定要模拟B中的所有输入、输出、内部状态、程序规则表这些元素，而只要在给定输入信息的时候，能够模拟B的输出信息就可以了。 因此，可以用下面的图来表示图灵机之间的模拟：

35 模拟——图灵机之间的模拟 也就是说在给定相同输入信息的情况下，只要输出信息o’能够模拟信息o就可以，也就认为B模拟了A。而信息o’对信息o的模拟又符合我们上面对一般集合之间模拟的定义。也就是说如果存在另外一台图灵机能够把信息o’计算并映射成信息o，就认为o’模拟了o。也就是o’可以与o不一样，但是只要你能用一个图灵机把o’经过一系列运算变换到相同的o，就认为o’模拟了o。因而也就是图灵机B模拟了图灵机A。

36 模拟——图灵机之间的模拟 进一步，我们可以假设A和B输入的信息也不一样，一个i，另一个是i’，那么如果i和i’之间也存在着模拟对应关系的话，我们仍然认为B可以模拟A。也就是下面的图： 有一点需要注意，如果A图灵机模拟了B图灵机，那么并不一定B图灵机可以模拟A图灵机。因为有可能A图灵机比B图灵机处理的信息更多。也就是说假如B能处理的信息就是1，2，3，4，而A处理的信息除了这四个数之外，还有5,6,7,8，那么显然当输入1234的时候A能够模拟B，而当输入5678的时候B没定义了，不能完成任何操作。在这个时候B显然不能模拟A了。

37 模拟——计算等价性 讲了这么多关于模拟的知识有什么用呢？模拟的一个关键作用就是阐明什么是等价的。比如为了完成加法运算，你写了一段程序，而我也写了另一段程序，虽然我们两个的程序可能完全不一样，然而只要我们两个程序之间能够相互模拟，也就是说只要给定两个数，我们都能正确的一模一样的算出它们的和，那么我们两个程序就是等价的 ！ 具体地说，如果A能够模拟B，并且B也能模拟A，那么A和B就是计算等价的。计算等价性是非常强有力的，因为它揭示了在我们这个宇宙中某种非常普遍的规律。我们仍然用刚才说的加法算法为例子来说明。虽然计算两个数的加法的方法可能有无穷多种，也有可能用各种各样的计算机语言，什么C,Basic,JAVA等等来实现，更有可能奔跑在不同的计算机上，然而所有这些程序，这些计算的结果意义都是相同的。也就是说所有与加法运算算法计算等价的计算机程序都是一回事儿，因而加法算法这个东西是某种永恒而独立的！

38 模拟——计算等价性 为了进一步理解计算等价性的威力所在，我们不妨科幻一下。假设我们能够用计算机模拟某个人，比如说张三的思维过程了（也就是假设真正的人工智能可以实现了）。那也就是说我们可以用一个计算机软件X来完成对张三思维的模拟。这样，这个软件就会在一切与它具有计算等价性的程序甚至系统上实现张三这个人的思维过程！比如我们完全有可能让一大堆分子的碰撞来实现X这个软件，那么就会在这大堆分子碰撞的过程中完成对张三思维的模拟，也就是说张三这个人的意志蹦到了这一大堆分子系统中去了！更进一步，我们还可以找来足够多的人比如这个星球上所有的人来模拟那大堆分子的碰撞，从而完成软件X的计算。这意味着什么？意味着张三这个人的思维或者说意识在那群人的整体上突现了！很有可能，这些构成软件X的人都并没有意识到在他们上层的张三的意识的出现。更有趣的是，张三自己很有可能就在那一群人之中呢！ 相信你已经能够参悟到了什么是计算等价性的威力了，那么我也相信你能够理解为什么说任何一台我们使用的计算机都不过是图灵机的翻版了。

39 模拟——意义 考虑下面三句话： “请把窗户关上！”， “Please close the window！”， “01001110111”。
这三句话分别说给不同房间中的三个人。第一句话告诉给一个中国人，于是他关上了窗户；第二句话告诉了一个英国人，他也关上了窗户；第三句话告诉的是一个机器人，他也关上了窗户。这三句话从表面看显然是完全不一样的，然而当它们让不同的人来听的时候，却达到了相同的最终结果：窗户被关上了。 那么，我们自然会想，这三句话有何相同呢？显然，答案是他们的意义相同。然而什么又是意义呢？

40 模拟——意义 真正回答意义的本质是一个很困难的问题，现在人们正在努力理解语义是什么。虽然我们仍没有完全回答这个问题，但是，不妨从图灵机、计算以及计算等价性的观点来考虑该问题。如果把中国人、英国人、机器人都看作是图灵机，而那三句话看作是对他们的输入信息，那么最终的结果就是图灵机计算的输出。这个时候我们看到三种结果是相同的。也就是说这些图灵机之间是可以相互模拟的。 考虑这三句话，显然它们都具有相同的意义。而根据前面的叙述，能够相互模拟的图灵机是具有相同的计算等价性的。因而描述听到关窗指令后并按照指令行事的图灵机具有相同的计算等价性。而这种计算等价性就好像是前面说到的加法规则一样是独立于计算系统、执行机构的。因而，我们能得到下面的图：

41 模拟——意义

42 模拟——意义 通过这个对比图，我们不难得出结论：所谓语言的意义，就是执行这个语言系统的计算等价性 ！
我们如何知道不同的语言表达了相同的意义呢？显然，我们只要有了翻译就可以明白“请把窗户关上”与“Please close the window”具有相同意义，而翻译所作的工作无非就是输入中文信息输出英文信息这样的信息转换工作，因而，也就是一个计算过程 ！ 然而当不存在从一个语言到另外一个语言的翻译的时候，我们也并不能断定某一个符号序列对于固定的图灵机是否有意义。这就是说，我们虽然不能明白鸟叫是什么含义，但并不能否认它们的叫声可能有意义，因为只有鸟自己才能明白叫声的含义。

43 图灵机与计算问题 万能（通用）图灵机 编码 自食其尾

44 万能图灵机——编码 “通用图灵机”，英文是Universal Turing Machine。而之所以称之为“万能图灵机”完全是因为这个名字似乎听起来更加直观。 前面已经讲述了模拟的概念，那么自然会产生这样一个问题： 存在不存在一台图灵机能够模拟所有其他的图灵机呢？ 答案是存在的。这种能够模拟其他所有图灵机的图灵机就叫做通用图灵机，也就是我们所说的“万能图灵机”。这种机器在图灵计算这个范畴内，是万能的 ！

45 万能图灵机——编码 “万能图灵机”会怎样工作呢？
假如我把信息x输入到了图灵机M中，M就能计算出一个结果o。那么如果我把x和M的信息都输入给万能图灵机，那么万能图灵机也会输出o，也就是万能图灵机可以模拟任何一台特殊的图灵机。这样的话我们就可仅仅通过改变输入x和M的值就能“改变”万能图灵机的程序规则了。因而也可以认为万能图灵机就是可以任意编程的。这里的改变两个字加上了引号，是因为事实上任何图灵机在诞生之后规则就不能改变了，因而我们能够改变“万能图灵机”的规则，仅仅是因为看上去是这样的，其实根本没有改变。

46 万能图灵机——编码 要说明为什么“万能图灵机”是存在的，以及它是怎样模拟其他任何图灵机的动作的，我们必须先要理解究竟怎样把任何一台图灵机输入到“万能图灵机中”，这就需要理解编码的概念。什么是编码呢？你可以理解为对某一堆事物进行编号就是编码。

47 万能图灵机——编码 其实我们每人每天都在跟编码打交道。每个人都有一个身份证，而这个身份证都有一个ID号码吧？那么这个号码就是你的编号。学号也是编码。 26个字母能够被编码，比如a对应1，b对应2，……，这是显而易见的。然而任意一个英文单词都是可以被编码的则不那么容易一眼看出来。事实上，我们可以按照字典顺序把所有的单词都列出来。也就是说字母顺序越靠前，字符长度越短的单词排在前面，其次长单词，字母顺序靠后的单词就排在后面。比如一种可能的字典顺序： a, about, an…, bad, be, behave….. 只要这样一排好序，我们就能给每个单词赋予一个数字，最简单的方法是，给第一个字母分配1，第二个分配2，……，因而我们就给所有的单词都编码了。

48 万能图灵机——编码 下面讨论任意一个图灵机能不能被编码。
我们假设讨论的所有图灵机的输入集合都是仅有0,1两种，而它的输出也仅仅有0,1,2,3四个动作分别表示前移，后移，涂写0，涂写1。而内部状态数最多为10000个（总之足够多就可以了）。下面考虑程序。 假设图灵机的程序表为：

49 万能图灵机——编码 那么我们可以把它写到一行中，这就是2,1,0,3; 1,0,4,2; 3,0,1,1，注意用“，”分开了内部状态，输入数值，输出动作和下一时刻的状态，而用“；”分开了一行一行具体的程序。这样无论这个表有多大，我们都可以把它写成这样的一个字符串。这个字符串就相当于一个英文单词，这就是对该图灵机程序的一个描述。同理，其他的图灵机也能够得到这样的一个单词描述，那么我们再用字典序的方法对这些描述进行编码，也就得到了对所有图灵机的编码。

50 万能图灵机——编码 如果一台图灵机的编码是M，它读入的信息是x，这样只要把M和x用“.”号隔开的方法分开作为数据输入到“万能图灵机”中，运用特殊的算法，这个万能的机器就能得出对M计算x的模拟结果了。事实上可以由定理证明万能图灵机对于任意的编码都是存在的，在这里我们就不叙述证明过程了。

51 万能图灵机——自食其尾 既然“万能图灵机”能够模拟任何一台图灵机的动作，那么它能不能模拟它自己的动作呢？ 答案是肯定的。
我们首先看到“万能图灵机”也是图灵机，也有固定的输入、输出、状态的集合、固定的程序，因而它也能被编码。于是我们就可以把它自己的编码信息输入给它自己了。这就好像一条蛇咬到了自己的尾巴。会发生什么呢？自食其尾就会产生怪圈，虽然我们现在还没有看到任何不好的征兆，然而在后面，我们将看到这种怪圈会诞生什么样的结论。而且我们也会看到，其实这个怪圈是和康托尔对角线法则、哥德尔定理有关的。

52 万能图灵机——自食其尾 图灵机一旦能够把程序作为数据来读写，就会诞生很多有趣的情况。
首先，存在某种图灵机可以完成自我复制 ！事实上，计算机病毒就是这样干的 ！我们简单说明一下，这个特殊的图灵机是如何构造的。 我们假定，如果一台图灵机是X，那么它的编码就记为<X>，这样能够自我复制的图灵机T的功能是，把T的编码<T>写到纸带上输入到“万能图灵机”，那么“万能图灵机”就能根据读入的<T>，在纸带上再次输出<T>的一份拷贝<T>’，并且<T>=<T>’。

53 万能图灵机——自食其尾 下面就来大概解释如何构造这样的T。首先T由两部分构成AB。第一部分A的功能是指导“万能图灵机”把B的编码<B>原封不动的打印到纸带上，这个时候纸带上就有了<B>，如果这个时候你想用同样的方法打印<A>到纸带上是不行的，因为会出现循环定义。然而B可以这样做，读入纸带上的信息X，生成能够打印X的图灵机：p(X)的编码<p(X)>打印到纸带上，并把X和<p(X)>的内容前后调换，有定理保证这样的图灵机是存在的。这样当B读到纸带上的信息<B>之后就会打印出能够打印<B>的图灵机的编码也就是<A>了，然后把<A>和<B>位置对换就构成了<AB>也就是<P>，所以P把自己进行了一次拷贝。初看起来，这种自我复制的程序是不可能的，因为这包含了无穷无尽的怪圈。P要能产生它自己<P>就意味着P中至少包含了一个<P>，而这个<P>中又包含了至少一个<P>……，最后P必然是一个无限大的程序，然而我们却能够证明P是可能的。（第六章高级专题）

54 万能图灵机——自食其尾 有了“万能图灵机”还能得到很多有趣的结论，比如假设有一大群图灵机，让它们彼此之间随机的相互碰撞，当碰到一块的时候，一个图灵机可以读入另一个图灵机的编码，并且修改这台图灵机的编码。那么这样一个图灵机“汤”中会产生什么呢？圣塔菲研究所的芳塔娜已经研究了这个实验，并得出了惊人的结论：在这样的系统中会诞生自我繁殖的、自我维护的类似生命的复杂组织，而且这些组织能进一步联合起来构成更大的组织 ！

55 图灵机与计算问题 停机问题 死循环 如何理解 对角线删除方法 意味着神马 超越图灵计算

56 停机问题——死循环 图灵停机问题就是一个类似该游戏的原理 ！ 在进行正式讨论之前，我们先来看看一个非常简单的猜硬币游戏。
假如我的两个拳头中一个攥着一枚硬币，另一个没有，然后让你猜是哪一个？于是你告诉我左手中有。这时候我不会把手张开，而是背过身去做一番手脚，然后把拳头伸过来，张开手 ！哈，你错了吧，硬币在右手中 ！大概傻子都能看出来我的伎俩之所在 ！不用说，采用这种方法我保证百战百胜。因为我总是等你说出来哪个手有硬币之后再动态的改变我的策略。所以，这改变之后的状态就已经不是你猜的了。 图灵停机问题就是一个类似该游戏的原理 ！

57 停机问题——死循环 下面我们来看看图灵停机问题是怎么回事儿。
让我们考虑这样一个问题：存在不存在一个程序比如说P，能够判断出任意一个程序X是否会在输入Y的情况下陷入死循环？ 我们不妨设P(X,Y)表示P判断程序是X，数据是Y的结果。如果存在死循环，那么P(X,Y)就输出一个yes。如果不存在死循环，那么P(X,Y)就输出一个no。我们的问题就是这样的P(X,Y)存在么？这就是停机问题。所谓的某个程序X在输入Y上停机就是说X不存在着死循环，反过来如果不停机就是存在着死循环，因而这里停机和死循环是一回事儿。那么，这种判断停机问题的程序P存在么？ 答案是不存在的。下面我可以证明我的这个结论。

58 停机问题——死循环 我们不妨假设程序P存在。那么我们可以根据P设计一个新的程序Q如下： X是任何一段程序的编码： Program Q(X){
m=P(X,X) do while (m=no) … end do if m=yes then return }

59 停机问题——死循环 这段程序通俗来讲就是：输入任何一段程序X，调用函数P(X,X)并得到返回值m，如果m=no，也就是说根据P的定义，P判断出程序X作用到它自己身上X不存在死循环。那么Q就不停的做do while和end do之间的语句。如果m=yes，我们知道这表示P判断出程序X在X上存在死循环。就返回，结束该函数。 我们可以看到，这样定义的函数Q(X)是没有问题的。下面就进入关键时刻了：我们问Q这个程序作用到Q自身的编码上也就是Q(Q)会不会死循环呢？当然我们可以运用强有力的函数P(Q,Q)来计算这个问题。

60 停机问题——死循环 假设Q(Q)会发生死循环，那么P(Q,Q)就会返回yes。然而根据Q函数的定义，把X=Q代入其中会发现由于P(Q,Q)返回的是yes，也就是m=yes，因此Q函数会马上结束，也就是程序Q(Q)没有发生死循环。然而如果假设Q(Q)不发生死循环，那么P(Q,Q)应该返回no，这样根据Q函数的定义，把X=Q代入Q(Q)之中会得到m=no，这样程序就会进入do while循环，而这个循环显然是一个死循环。因而Q(Q)发生了死循环！这又导致了矛盾。 无论Q(Q)会不会发生死循环，都会产生矛盾，然而哪里错了呢？答案只能是最开始的前提就错了，也就是说我们最开始的假设P(X,Y)能够判断任意程序X在输入Y的时候是否死循环是错误的 ！也就是说这样的程序P(X,Y)不存在 ！

61 停机问题——如何理解 也许你会感觉整个论证过程有些怪异，为什么不存在这种P(X,Y)程序呢？而上面的论证过程中仅仅说P(X,Y)当作用到P(Q,Q)上时会产生矛盾。似乎并不能说明P作用到其他程序上不能判断是否死循环。比如你可以考虑编写这样一段程序，当一发现某个程序do while(T)，这里T总是为真，这样的语句出现的时候就判断这个程序有死循环。这显然是可能的。但问题的关键是，你假设了P(X,Y)能够判断任意的一个程序是否死循环！最关键的就是这“任意程序”上了。因为假如你已经按照刚才提到的判断是否有do while(T)语句的方法写出了一个程序P来判断某程序是否死循环，那么我就会根据你这个程序P再构造出一个程序Q，就是利用上面提到的论证方法，我们不妨写成QP(这里下标P的含义表示根据你的程序P而构造的Q)。这样你的P在遇到了P(Q,Q)这样的怪东西的时候无能为力了 ！

62 停机问题——如何理解 可能你还不服输，于是你又改进了你的程序变成了P’，这个时候P’能够判断包含了QP这个程序时候的所有程序情况了。那么我又会根据你的新程序P’来构造出一个更新的QP’，你的程序P’仍然不能判断，当然你还可以构造P’’,P’’’,……，我也会跟着构造QP’’,QP’’’，……，总而言之这个过程是无穷的 ！因为我总在你之后构造程序，所以你是水我是船，水涨船高，我总能比你高一级别 ！ 这很像刚开始叙述的那个猜硬币的游戏。你想猜对我的硬币，就必须告诉我一个答案是左手还是右手，然而关键问题是我总能根据你做出的答案动态调整，使得你永远也猜不对 ！停机问题也是如此，我总能根据你的程序P来构造你的P判定不出来的问题Q，我总会赢 ！很简单，因为你总要在我之前构造好P呀，就相当于你总要先说出硬币在哪个手 ！

63 停机问题——对角线删除方法 我知道图灵停机问题、哥德尔定理等等都来源于康托尔的对角线删除法则。那么，下面我们就来看看，如果运用对角线删除法则如何证明图灵停机问题呢？采用这种全新的证明思路，也许你会更加清楚地认识到停机问题的本质。 问题没有变，是否存在一个程序P(X,Y)判断出来任意一个程序X当输入Y的时候是否有死循环，或者说是否停机。

64 停机问题——对角线删除方法 我们仍然用反证法，假设这样的P(X,Y)是存在的。而我们知道程序X本身是可以被编码的。也就是可以为所有的程序进行编号：1，2，3，……，而数据Y本身也是这样的编号1，2，3，……，因而我们就可以把每一对X和Y的组合排列在一张表上。比如列表示的是数据Y，而行表示的是程序X，这样P(X,Y)的值也就是yes或no就可以写在第X行第Y列的对应位置上，表示P(X,Y)判断出的X作用在输入Y上是否会死循环的结果。比如下面的表就是一个示例：

65 停机问题——对角线删除方法 到这里没有发生什么毛病。我们知道上表中的每一个行都表示一个确定的程序作用到不同的数据上所得到的结果。比如程序X作用在1,2,3,4,……,Y，……上给出的结果就是一个序列： no,yes,no,yes,yes,no,……,yes，……

66 停机问题——对角线删除方法 下面我们把上表对角线上的元素挑出来。也就是专门找那些第1行第1列，第2行第2列，……这样的元素就可以得到一个序列： yes,no,no,yes, …… 而根据这个序列我们完全可以构造这样一个反序列： no,yes,yes,no, …… 也就是说这个序列在每一个位上都与前一个对角线序列不同 ！这个序列就称为对角线删除序列。那么我问，这个对角线删除序列是否在我们表中的某一行上呢？答案是否定的 ！这个序列必然不在表中。因为它的第一个元素与1,1不同，第二个元素与2,2不同，……。换一种方式解释就是：假设对角线删除序列的确在表上列出来了，那么这个序列必然在某个固定的行，比如说就在第1001行。那么我们就要考虑这第1001行，第1001列的元素，我们知道根据序列的构造方法(1001,1001)对应表中的元素是与序列上的这个元素不同的 ！因而产生了矛盾，也就是说这个构造出来的对角线删除序列不在表中 ！

67 停机问题——对角线删除方法 我们完全可以设计出一段程序Q使得Q作用在1,2,……,X,……上产生的序列就是对角线删除序列，而对角线删除序列不在表中就意味着程序P并不能判断出程序Q作用在任意输入上是否停机。其实这里的程序Q就是前一节论证停机问题的程序Q。 用对角线删除的证明方法来看究竟哪里出错了呢？错误就出在我们假设程序P能够得到这样一张完整的表，这张表对所有的程序计算得到是否停机的答案。

68 停机问题——意味着什么 我们已经看到了，的确存在着一类问题我们人类能构造出来，而图灵机是不能解的。我们知道图灵机不能解的问题也就是一切计算机不能解的问题，因而这类问题也叫做不可计算的。因此，必然存在着计算机的极限。实际上，运用我们前面叙述的计算等价性原理，有很多问题都可以被归结为图灵停机问题，也就是说图灵停机问题揭示了宇宙中某种共性的东西，所有那些计算机不能解决的问题从本质上讲都和图灵停机问题是计算等价的。比如在我们就提到的希尔伯特第10问题就是一个典型的不可计算问题 ！还有很多问题是不可计算的，尤其是那些涉及到计算所有程序的程序。比如是否存在一个程序能够检查所有的计算机程序会不会出错？这是一个非常实际的问题。我们都知道计算机程序特别容易犯错误，为了检查出某段计算机程序的错误，我们人类就必须对这个程序进行人工的检查。那么能不能发明一种聪明的计算机软件，输进去任何一段计算机程序，这个软件就会自动帮你检查输入的程序是否有错误？答案仍然是不存在的，其实这个问题可以被证明和图灵停机问题实质上是一样的 ！于是我们的梦想又破灭了 ！

69 停机问题——意味着什么 图灵停机问题也和复杂系统的不可预测性有关。我们总希望能够预测出复杂系统的运行结果。那么能不能发明一种聪明的程序，输入进去某个复杂系统的规则，输出的是这些规则运行的结果呢？从原则上讲，这种事情是不可能的。它也是和图灵停机问题等价的。因而，我们得出来的结论就是：要想弄清楚某个复杂系统运行的结果，唯一的办法就是让这样的系统实际运作，没有任何一种计算机算法能够事先给出这个系统的运行结果。你很有可能不同意我的观点，因为毕竟我们能够发明很多预测复杂系统的方法，而不需要一定要让复杂系统去真实的运作。但是，你还是没有理解我这里的问题。我们强调的是不存在一个通用的程序能够预测所有复杂系统的运行结果，但并没有说不存在一个特定的程序能够预测某个或者某类复杂系统的结果。那么这种特定的程序怎么得到呢？显然需要我们人为地编程得到 ！也就是说存在着某些机器做不了的事情，而人能做。这似乎为人工智能的崇拜者给以了沉重的打击 ！

70 停机问题——意味着什么 人工智能真的是不可能的么？彭罗斯曾经写过一本科学名著：《皇帝新脑》来论证人工智能的不可能性。它所运用的方法就是我们上面的逻辑。因为对于任何一个人工智能程序来说，总存在着它解决不了的问题 ！但是似乎我们人类却不受这种限制，我们总是能够发现一个程序是否有死循环，总是能够找到对某类复杂系统预测的方法，并且我们还能构造出来图灵停机问题这样的问题。然而事实并没有那么简单，反对者马上就会论证到，其实针对某一个具体的人，比如说就是彭罗斯，我们也能够运用前面的方法构造出一个彭罗斯自己不能解的问题 ！然而事实情况下要构造彭罗斯不可解的问题太麻烦了，而我们只是说原则上讲这种问题是存在的 ！因而计算机超越不了的问题，人自己也超越不了，所以说人工智能是可能的 ！

71 停机问题——意味着什么 看看上面提到的两方面论证似乎都很有道理，究竟哪个正确呢？真的会存在某个人不可解的类似图灵停机的问题么？其实要想彻底回答这个问题就相当于问超越图灵计算的限制是否可能？如何超越图灵机停机问题呢？下面我们将详细讨论一下这个问题。

72 停机问题——超越图灵计算 我们仍然用那个猜硬币的游戏为例来说明。
在进行了几轮猜硬币的游戏之后，你已经很恼火了，认为这样的游戏不公平。于是你想了一个妙招来对付我：每当我让你说硬币在哪个手中时，你先胡乱的说一个答案，比如左手。这个时候我会根据你的答案动态调整把硬币放到了右手中。这个时候你赶紧抢着说，不对，我猜你的硬币在右手 ！我没办法只能再次调整策略把硬币放到了左手。你又赶快说：是在左手 ！……。就是这样，你也学会了我的方法，根据我的策略不断调整你的策略从而让我不可能赢你。能不能把这种方法用到超越图灵停机问题呢？

73 停机问题——超越图灵计算 前面我们已经看到了类似这样的过程。假如你写出了一个程序P能够判断所有程序是否停机，那么我就能够构造一个程序Q是你的程序判断不了的。这个时候还没有结束，你又根据我的Q构造了新的程序P’，然而我又能构造一个程序Q’仍然让你的程序P’解决不了。但是你没有结束，又构造了新的程序P’’，我于是又构造Q’’……。 乍一看，似乎这个过程并不能说明任何问题。原因很简单，我要求的是构造一个固定的程序P判断出所有程序是否停机。而你给我的并不是一个具体的实实在在的程序，而是一个不断变化的捉摸不定而虚无飘渺的程序序列 ！并且你的这些总在变化的程序序列总是要根据我构造的程序才会确定改变！

74 停机问题——超越图灵计算 首先一点值得肯定的是，运用这种方法，我们的确能够超越图灵计算了，只要反复不停的变换我们的程序就不可能找出它不能解的问题。然而，另一方面又会让我们很失望：这样的变换过程并不能给出一个实实在在的程序来 ！我们拥有的仅仅是不断改变的程序序列，而不是一个实际存在的程序！ 这正是问题的关键所在：要想彻底超越图灵计算的限制，我们必须要放弃程序的实在性。也就是说程序在每时每刻都要变化成不是它自己了。那么这样的一个不断变化得不是它自己的怪东西存在么？

75 停机问题——超越图灵计算 几千年的人类科学一直在研究实实在在的东西。无论是原子、分子还是计算机程序，它们必须是一个实实在在存在的个体，在这种前提下科学才能够对它进行研究 ！如果当我们研究它的时候，它已经变得不是它自己了，那么科学就对它无能为力了。然而，我不禁要提出这样的问题：真的一切都是固定不变的存在着么，有没有某种东西在每一时刻都在变得不是它自己了呢？ 这个问题似乎是一个古老的哲学问题了，记得赫拉克里特就曾经提到过：一个人不能两次踏入同一条河流。我想他说的正是这样的问题：因为河流在每时每刻都不再是它自己了。河流是一大群流动的水滴构成的整体，在每时每刻这些水滴都在不停的运动、流逝，因而当你两次踏入这条河的时候，所有的水滴可能都不一样了，那么我们怎么能说这些水滴构成的整体还是同一条河呢？

76 停机问题——超越图灵计算 再考虑我们人自己。你很可能拿着一个你3岁时候的照片兴奋的对你的朋友说：“看，我3岁的时候多可爱呀 ！”。然而你这句话意味着什么呢？意味着照片反映的3岁时的你和现在的你是同一个个体 ！然而，3岁的你和现在的你是多么不同呀 ！我们知道，你无疑就是一大堆细胞构成的一个整体。而基本生理学知识告诉我们，实际上人体的所有细胞每隔大约4年就会因为新陈代谢的作用全部更新一遍。也就是说，你的细胞全被掉了包了，更何况3岁时候的你和现在的你差了多少个4年呀？那凭什么说那个3岁时候的你就是现在的你呢？

77 停机问题——超越图灵计算 这个问题看似玄学，不过我认为现在我们的确应该认真对待该问题了。尽管从分析的角度来说3岁的你和现在的你的确不是一个个体，然而常识告诉我们，这两个你的确都是同一个人 ！那就意味着，你这个个体并不是一成不变的一些固定的细胞，而是一个每时每刻都在变化，都在更新的一个一大堆细胞组成的构形。这个构形在每时每刻都要利用更新的一大堆细胞去维持自己的存在 ！我们得到了什么？和我们前面叙述的超越图灵机的讨论结合起来，就发现，原来人还有赫拉克里特的河流这种东西刚好就满足那种超越图灵计算的要求。也就是说人还有赫拉克里特的河流在每时每刻都在不停的更新它自己从而变得不是它自己了。那么很有可能，某一种做类似变化的个体的变化规律就是不停超越它自己的图灵停机程序，这样的虚幻的个体就真的能够超越图灵计算了 ！

78 停机问题——超越图灵计算 总结前面的讨论，我们不难给出结论，一个固死的能够被写出就不再变化的程序不可能超越图灵计算的限制，然而如果一个程序每时每刻都已经变化得不是它自己了，这个程序就能够超越图灵计算。联系到人这个个体，我们能得到：因为每时每刻的人都已经由于细胞的变化而变得不再是它自己了，所以人是超越图灵计算的 ！还记得在前面提到的一个问题么：“人脑的信息处理过程能不能被表示成固定的程序呢？”。我这里的答案就是否定的 ！也就是说人脑信息处理的过程并不是一个固定的程序！如何制造真正的人工智能呢？很显然，我们不能用一个简单的程序来构造，而必须是利用其它的方法，这个方法是什么呢？现在还没有结论 ！

79 图灵机与计算问题 悬而未决

80 悬而未决 到此，我已经把全部的有关图灵机、可计算理论、停机问题的一些重要概念介绍完了。然而在计算理论这个领域里还有很多重要的问题没有介绍。还存在一些没有解决的问题，这些悬而未决的问题包括下面几个： 是否一切的信息处理过程都具有固定的程序呢？人脑有固定的程序么？ 如何用计算机程序进行归纳？能对所有事物进行一劳永逸的归纳算法是否存在？ 什么是意义，更确切的，什么是语义？ 图灵停机问题是不可超越的么？ 人工智能是否可能？

81 悬而未决 还有很多问题也是相当重要的。例如， 我们如何用图灵机模型表示一般的学习过程？
若干小的图灵机是如何自动的构造出更大的图灵机的（这就是万事万物自组织的过程）？ 生命的目的性如何用图灵机模型表示？ 另外最近的计算主义已经把宇宙中一切的过程都归结为计算过程了，也就是说到处都是图灵机正在做运算。那么我们能不能从图灵机的角度探讨时间和空间的本质呢？我们知道，计算理论另外一大类问题就是探讨计算的时间和空间复杂度，那么这种计算的时间和空间与我们这个宇宙的时间和空间有什么关系呢？