简陋的图灵机是如何完成计算的？

大家好，欢迎来到IT知识分享网。

1

了冯·诺依曼，他是现代计算机之父。我介绍冯·诺依曼，是想告诉你，电脑的内外差别，为什么不是按照机箱的内外来分辨，而是要把处理器和内存定义成“内”，处理器和内存之外都是“外”。

这是因为计算机之父冯·诺依曼，他已经定好了，他在观察第一台计算机ENIAC的优缺点之后，总结出来的经验，提出了一个新的结构。按照新结构来设计计算机是最容易实现通用计算机的。

这个新结构，说白了就两个东西最重要，一个是CPU，一个是内存，其他的所有设备都是围着它们转，给它们打辅助。其他的设备，本质上无非就是提供提供数据，接收接收数据。

冯·诺依曼提出的这种方法简单有效，所以所有计算机就都按照这种方式来做了，到了现在电脑还都是用的冯·诺依曼架构。

但是你别被这个表现蒙蔽了，并不代表电脑必须按照冯·诺依曼说的方式来制造。现在电脑被冯·诺依曼架构称霸了，那是因为既然已经有一个好用的架构了，那就学习学习拿来用吧，省的再重新发明了。这就相当于是，已经有人把答案做出来了，你就不用闷头算题了，拿过来抄一遍岂不是省事。

当然了，这是科技发展，这方面还是鼓励大家模仿学习的，如果是写作业，还是不要抄的好，要不然考试是会考0分的。

要是有个外星人坐在飞船来到的地球，那你拆开他飞船上的电脑，这个电脑很有可能就不是冯·诺依曼架构的。毕竟他是外星人，没办法抄冯·诺依曼的作业。

至于电脑不是冯·诺依曼说的这个样子，还能是什么样子，我也不知道，反正到现在也没有发明出来。但是我就是可以肯定，冯·诺依曼架构不是唯一的。

为什么这么说呢？因为理论上讲，如果能用机器把人脑的功能完全复刻一遍，也肯定是可以造出计算机的。只不过人脑太复杂了，现在还搞不明白，当然也就没办法做出人脑一样的计算机了。

当然，我们现在还没有发明其他架构的电脑，还是因为冯·诺依曼还挺好用的，没有必要花心思、花力气去做新架构。

一个架构，六七十年没有变过，从这一点冯·诺依曼怎么就那么厉害呢？这其实不全是冯·诺依曼的功劳，因为这个架构并不是他凭空拍脑门想出来的。他也抄了作业，他抄了另一个计算机之父图灵的作业。当然，也不是全部原封不动照搬过来，还是有很多自己创新地方的。

1937年，图灵就在自己的脑袋里面构建了一个虚拟的机器，这个机器就是一个可以自动运行、自动解决问题的计算机，我们现在把这个虚拟的机器叫做图灵机。冯·诺依曼就参考了图灵机，提出了冯·诺依曼架构。

2

图灵机，那可是想的简单的，甚至都可以说简陋了。我们可以先来看一下图灵机的样子。

图灵机有两个重要的部分，一个无限长的纸带，一个是可以进行读写的读写头，也就是既可以把纸带上的内容读出来，又可以在纸带上写字。

纸带上是一个一个的格子，每个格子里面可以写0或1两个字符。读写头可以左右移动，读写的时候，一次可以读写一个格子里的内容。如果格子里面已经有了别的内容，那么就会把原来的内容擦除掉，然后再重新写上新内容。

你也别奇怪啊，这个机器这么简陋，能干啥。别说干啥了，可能都没有办法运行起来吧，拿它能解决什么问题？

当然如果只是这样的话，这个机器还啥也干不了，要想化腐朽为神奇，还需要两个东西。

第一个，是一个表格。这个表格其实就是一堆指令，告诉读写头怎么应该干什么。比如，如果读到了1那么向左移动纸带，如果读到了0就把这个格子里的0改写成1并同时向右移动。这个表格其实就代表这个机器可以做的所有动作。

只有这一个表格还远远不够，如果只有这个表格的话，那么无非是两种情况，要么读到了0，要么读到了1，也就是说这个机器有点低能，只能完成两个不同的动作，不可能有第三种情况了。

这肯定不行啊，怎么办呢？这就需要第二个东西了，这个东西才是真正的画龙点睛。是什么呢？那就是读写头有一个状态记录器，用来表示这个读写头此时此刻的状态。只需要多增加这么一个功能，图灵机就可以从原来的低能，一下子变成可以解决所有计算问题了。

只要可以记录状态就可以这么神奇吗？我举一个形象点的例子帮你理解一下。

假如我们把这个读写头想象成是一只狗，纸带就是一条无限长的路，纸带上的1表示这个地方有食物，纸带上的0表示这个没有食物。这只狗做的事情也很简单，在它的脑子里就装了2件事，第一件事就是遇到了1，也就是有食物，那就把食物吃掉，并且向前走一格。这就相当于在图灵机上把1涂掉，写上0然后再向右移动一格。第二件事就是如果遇到0了，那就什么也不做继续往前走。

如果没有第二个画龙点睛的东西，这只狗只能是一只笨狗，他不知道饱也不知道饿，就知道吃。它肯定是一直走一直吃，最后把肚子撑爆了。

但是这只狗只需要聪明一点点，知道自己的状态，那就不一样了。假如这只狗有3种状态，饥饿、差一点饱和完全饱了。那么这只狗最开始走的时候，状态是“饥饿”，走着走着第一次遇到了一个1，也就是遇到了食物。

这个时候，该干嘛呢？它需要先看一下自己现在的状态，一看是饥饿，那好办了，就把食物吃掉，继续向前走一格。不能光吃啊，吃了一个食物肯定饱了一点了，所以这个时候狗的状态就变成了“差一点饱”。

然后继续走，走着走着遇到了第二个1，这个时候怎么办呢？同样，还是先看一下自己的状态，一看是“差一点饱”，那就继续把食物吃掉，向前走一格，同样同时要把状态修改成“完全饱”了。

走着走着，又遇到了1，这个时候再看自己的状态，一看是完全饱了。那就可以不吃食物，直接到下一格。这样小狗就不会撑爆肚子了。这样的狗就不是一直笨狗了。

当然，这个狗还是笨了一点，只知道是不是吃还是不吃。但是这个状态如果增加呢，比如热不热啊，疼不疼啊，危险不危险啊，状态越多就越聪明。

也就是说啊，一旦有了记录自己状态的能力之后，小狗的聪明程度都是一个质的飞越。图灵机也不例外，也是只要能记录状态，它的能做很多事情了。

有了这4样，纸带，读写头，写在表格里的指令和记录状态的装置，图灵机就已经可以完成所有计算了。

到底如何做才能完成所有计算，这一次肯定是来不及讲了，反正是多复杂的计算都可以做。我就举一个简单的例子，让图灵机自动完成一次加法运算吧。

纸条上不是只能记录0和1吗，那我们就可以做一个规定有几个连续的1就代表这是数字几，比如111代表3，11代表2。0就是把不同的数隔开的工具，比如在纸带上写的是，这就代表了这个纸带上有一个3和一个2，111和11中间有个0把它们隔开了。

我们要做加法运算，怎么做加法？就是要像一个表格，告诉读写头怎么做，可以让原来的中间的0消失，让111和11接起来，也就是有5个1是连续的，5个1当然就是5了。加法完成。

具体怎么做，我就直接公布答案了，思路并不是把中间的0删除掉，而是把后面的11向左移动一格，这样就可以把段的1给拼接起来了。

要想实现加法，读写头需要有3种状态，分别是a、b和c。这里的abc，不像小狗肚子状态一样有具体意义，这里没有实际的现实意义啊，只要能区分开彼此就行。

然后还需要6条命令，就可以让图灵机自动完成加法运算。

这六条我挨个讲一下啊，我也不一步一步带着你做了，如果你感兴趣了，还愿意动脑筋，可以在自己画一画，看看按照这6个命令进行移动，最后是不是会得到11111。

1. 如果状态是a，读写头读到的是1，那么向右移动，不改变读写头状态；
2. 如果状态是a，读写头读到的是0，那么把当前这一格改写成1，向右移动，状态改变成b；
3. 如果状态是b，读写头读到的是1，那么向右移动，不改写读写头状态；
4. 如果状态是b，读写头读到的是0，那么向左移动，状态改变成c；
5. 如果状态是c，读写头读到的是1，那么把当前这一格改写成0，不移动，状态不变；
6. 如果状态是c，读写头读到的是0，那么不移动，状态不变；

就是这6条，不只是能计算3+2，任何自然数的加法都可以计算。只需要，两个数之间隔一个0。对了，还有图灵机开始计算的时候，读写头要放在纸条上第一个1的位置，状态设置成a。接下来，就不用管了，它就可以自动完成加法运算。

这是加法，那么乘法呢，除法呢？其他四则运算，或是更复杂的计算呢？只要给定不同的指令表格和读写头状态，那么这个机器就可以完成不同的计算任务。这是被图灵证明了的。图灵能伟大，可不是他拍脑袋想出了一个简陋的图灵机，而是他证明了，只要一个问题可以被计算、被求解，那把它交给图灵机一定都可以搞定。

具体怎么证明的，那就特别复杂了，我们这里不讲了。要想讲明白，我还得去看看图灵当年写的论文才行。我自己现在也不知道具体是怎么证明的。

3

介绍完图灵机了，你看它是不是似曾相识啊。那个无限长的纸条，用来保存数据让读写头操作的，这就是内存啊。那个读写头，就是CPU啊，那个表格就是程序啊。

只需要表格里的信息也转换成二进制，也可以能保存在纸条上。这就相当于冯·诺依曼提出的，把程序和数据都存着内存里一样。

讲到这里应该明白了吧，为什么要把CPU和内存看做是计算机内部了，因为计算机就是来自于图灵机啊。图灵机，从硬件上来看，只有纸条和读写头，也就是只有内存和CPU。

前面没有讲，现在的CPU内部也是会记录状态信息的，而且状态信息还特别丰富，比图灵机的状态信息丰富多了。

CPU里面用来记录当前状态信息的部分叫做寄存器，现代的CPU里面的寄存器，有地址寄存器、数据寄存器、指令寄存器、累加寄存器、状态字寄存器等等。具体这些寄存器是什么意思啊，等我后面帮你拆解处理器是什么工作的时候在给你介绍吧。

我现在可以给你介绍一个小知识，那就是寄存器的大小其实决定了处理器的位数。这个位数就是二进制数有多少位，比如010、011、111这3个数都是二进制数，而且都有3个0或1，这种就叫做3位，如果是1111、或是1010，有4个0或1，那就是4位。

现在寄存器的大小，普遍都是64位，也就是一个寄存器可以一下保存64位2进制。要是早个十几年，比如Intel的奔腾处理器就是32位的。我小时候玩的任天堂的红白机，这个游戏机里面的处理器只有8位寄存器。

不论是8位、16位、32位还是64位，往往不只代表了处理器内部寄存器的位数，还代表着处理器一次可以处理的数字的大小。就比如，64位的处理器，就可以一下读取64个二进制数到处理器里面。而8位的处理器，一次只能读取8位，需要读8次才能达到64位处理器一次的效果。

你看图灵机，只看它读写能力的话，一次只能读写一个1或0，所以它就是个1位机。

介绍完这个小知识，我们再回到冯·诺依曼架构和图灵机上。图灵在构想图灵机的时候，他其实并没有想着如何制造出一个真实的机器。而且图灵机又是一个非常非常简陋的原型，虽然要处理器有处理器，要内存有内存，但是既没有考虑硬件到底怎么实现，又没有考虑性能，计算起来到底是快是慢。

从图灵机到真的把计算机做出，还是很多的事情要做的。这就像是，我们看到鸟飞上天了，我们知道一定有什么方法可以飞起来，但是真的把飞机造出来那就是另外一回事了。所以我们才会歌颂莱特兄弟，他们能把飞机真的造出来，是永远值得被赞扬的。

冯·诺依曼也一样，虽然他读过图灵的论文，知道图灵机的思路，但是他对计算机的贡献也是不可磨灭的。就比如内存，其实还是和图灵机的字条不一样，内存所以也可以看做是一个长长的存储带，但是CPU读取内存里的数据，可以直接读取。原来读的是1号位置的数据，想要读取100号位置的数据，可以直接读取，要是图灵机的纸条，那就不行 ，必须从1号位置移动99次才能移动到100号位置。显然内存访问起来更方便。

这其实也是冯·诺依曼架构超越了图灵机的地方，所以我才会说冯·诺依曼和图灵都是计算机之父。

至于图灵能想出图灵机，并不是想着要创建计算机，而是为了证明一个数学上的终极问题，这个问题可以讲好几集的，我们继续挖坑，这一集就先不讲了。你只要知道，这个数学问题是能让数学崩溃的一个问题，非常非常重要。

最后，关于图灵这个人，我其实还想多介绍一些，他的人生虽然很短暂，但是他已经2次改变过人类的命运，而且现在很可能正在第三次改变人类命运。

第一次改变，就是1937年提出了图灵机。前面我讲了这么多，你也能可以感觉到了，我们现在的信息社会的基础就是建立在图灵机上的。

第二次改变，是第二次世界大战的时候，他加速了战争的结束。冯·诺依曼是靠参与曼哈顿计划，制造原子弹来加速战争结束的。图灵也有自己的贡献，他是在英国参与激活成功教程德国密码，来帮助盟军取得胜利的。关于这段历史，我推荐你看一部电影《模仿游戏》，就是讲的图灵如何帮助英国激活成功教程密码的故事。很多人都说，图灵的贡献让第二次世界大战提前结束了好几年。

第三次改变人类命运，是现在正在发生的事情。是在二战之后，图灵继续做的研究，就是人工智能。计算机只是可以快速地进行计算，那么它能不能具有像人一样，甚至超过人的智能呢？人的智能又是什么呢？他提出了非常有名的“图灵测试”，就在尝试回答这个问题。图灵不只是计算机之父，也是人工智能之父。