什么是计算?广义上讲,一个函数变换,把输入信息 x 变成输出信息 f(x)就是一个计算!如果我们把一个小球扔到地上,小球又弹起来了,你完全可以把小球的运动都抽象成一些诸如位置、速度、形状等等信息,而地面把小球弹起来就无非是对小球的这些信息进行了某种变换,因而地面就完成了一次计算!
自然中的一切过程都是在进行计算，碰撞的小球、流动的溪水、燃烧的火焰，大自然用自己的方式处理着大量的信息。如同在《黑客帝国》中一样，我们所生活的世界是计算出来的。著名的Mathematica 软件发明人沃尔弗莱姆（Wolfram）甚至宣称，整个宇宙就是一台大的图灵计算机。而美国ACM颁发的计算机领域最高荣誉是“图灵奖”。
究竟什么是图灵机？图灵又是何方神圣？本文先景仰一下天才图灵，再了解一下图灵机的基本思想，然后看看图灵机是如何工作的。
天才图灵
艾伦·图灵（Alan Turing），1912 年 6 月 23 日生于英国伦敦西部帕丁顿住宅区一个中上层的家庭里。父亲在民间服务机构工作，经常来往于英国与印度之间。幼小的艾伦·图灵被托付给他父亲的一位朋友。很小的时候，图灵就显露出不同常人的天分。他仅用了三个星期，自己学会了阅读。他还表示出对数学难题的热衷。
六岁那年进小学，女校长马上发现了他的聪明才智，为了怕他“吃”不饱，经常将后面的课程提前教给他。1926 年，他进入中学。开学那天，正赶上英国举行大罢工，公共交通瘫痪。年仅 14 岁的图灵提前一天只身骑自行车，飞速穿行 60 英里（近 100 公里）赶往学校，夜间留宿中途的小饭店，最后没有误了第一天的课。这件事在当地报纸上报道后引起轰动。
图灵的爱好是数学和科学，而这所开办于十六世纪的著名学校，其传统是文学和艺术。校长给他父亲写信，认为图灵独自追求科学，有违学校育人的初衷，实在是浪费时间。但是，图灵不管这些，继续在自己喜爱的学科领域中不断展示才华。1927 年，他根本没有学习过微积分的基础知识，但是硬是将十分复杂的难题解决了。1928 年，图灵年仅 16 岁，开始接触爱因斯坦的高深理论。他不但掌握了这些理论，而且用爱因斯坦理论审视教科书中没有阐述清楚的牛顿运动法则。
1931 年，图灵进入剑桥大学国王学院学习。1934 年取得学士学位。1935 年，凭借他在国王学院中的关于高斯误差函数的学术报告而被选为助理研究员。
1936 年，艾伦·图灵发表了他的著名论文《论可计算数及其在判定问题中的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem），论文设计了抽象的现代计算机模型，即图灵机。图灵高度概括了这台机器的结构和工作原理，从而为人们设计具体的实用的计算机指明了方向。
1950 年，图灵又发表了划时代的文章：《机器能思考吗？》，成为了人工智能的开山之作。
图灵的天才还体现在二战期间用数学方法破译德军使用的一种优良的恩尼格玛发报机发出的任何密码，为此德军在英伦三岛与大西洋吃足苦头。
图灵的身体素质也让人们所羡慕，它在 1947 年居然用 2 小时 46 分 3 秒跑完马拉松。
可惜的是，就在他的事业刚刚达到顶峰的时候图灵自杀了。1954 年 6 月 8 日，图灵死于氰化物中毒，享年仅有42 岁。一代科学巨星陨落了，为了纪念这位在计算机领域中建立开创性功绩的著名科学家，美国设立了“图灵奖”，奖励世界上信息科技的杰出科学家。
图灵机
现代计算机的历史应从 1936 年算起，因为在那年，图灵设计出抽象计算机模型——图灵机，而任何实用的现代计算机性能只是图灵机性能的等价集，或者子集。著名的丘奇(A.Church)命题指出,任何算法都可以用一个图灵机来描述。
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
- 在纸上写上或擦除某个符号；
- 把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于
- 此人当前所关注的纸上某个位置的符号；
- 此人当前思维的状态。
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
- 一个被划分成方格的无限长的纸带；
- 一个读写头，可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号；
- 一套控制规则——程序——它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态；
- 一个状态寄存器，保存当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。
小虫的比喻
我们不妨考虑这样一个问题：假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型呢？
首先，我们需要对小虫所在的环境进行建模。我们不妨假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小方格，而每个方格都只有黑白两 种颜色。黑色表示该方格有食物，白色就表示没有。假设小虫仅具有一个感觉器官：眼睛，而且它的视力差得可怜，也就是说它仅仅能够感受到它所处的方格的颜 色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。
其次，小虫有输出动作，它可以在方格上前移、后移，还可以涂写方格成黑色或者白色。最后，小虫还会有两种内部状态，即{饥饿，吃饱}。这样小虫的行动按照下面的程序进行：
| 输入 | 当前内部状态 | 输出 | 下时刻的内部状态 |
|---|---|---|---|
| 黑 | 饥饿 | 涂白 | 吃饱 |
| 黑 | 吃饱 | 后移 | 饥饿 |
| 白 | 饥饿 | 涂黑 | 饥饿 |
| 白 | 吃饱 | 前移 | 吃饱 |
即如果当前处于饥饿状态，则有食物就吃掉，没有食物就“自行解决问题”（即自己会吐出食物）；如果当前处于吃饱的状态，则如果没有食物就前移，如果有就后退，并且转入饥饿状态。那么当小虫子读入黑白白黑白……这样的纸带的时候，会怎样行动呢？让我们来看下面的图：
在图中，小虫用圆圈表示，它从最左边开始移动，灰色表示饥饿状态，白色表示吃饱状态。箭头表示移动的方向。从上到下，小虫一步一步地根据纸带的颜色 和它自己的内部状态查找规则表中的对应项而采取行动。例如第5 步读入方格是黑色，内部状态为吃饱，根据这两项输入信息查找规则表找到对应项是第二项，根据它，小虫应该后移，且内部状态变为饥饿。不难看到，到了第8 步，情况跟第4 步完全相同，输入都是白色纸带和饥饿状态，根据程序，小虫将重复4~8之间的动作，并一直持续下去……
尽管从长期来看，小虫会落入机械的循环。然而当你输入给小虫白色信息的时候，它的反应可能完全不同（如第4 步和第6 步的行为），所以只要小虫子的内部状态和程序非常复杂，那么小虫的行为也会越来越超出你的想象！相信你已经明白了这个小虫模型，那么你就掌握了图灵机的工 作原理，因为从本质上讲，这个小虫模型就是一台图灵机！
这个模型是否太简单了？下面，我就要试图说服你，图灵机这个模型是伟大的！
首先，人都可以被抽象地看成一个图灵机。显然，输入状态集合就是你所处的环境中能够看到、听到、闻到、感觉到的所有一切，可能的输出集合就是你的每 一言每一行，以及你能够表达出来的所有表情动作。内部状态集合则要复杂得多。因为我们可以把任意一个神经细胞的状态组合看作是一个内部状态，那么所有可能 的神经细胞的状态组合将是天文数字！
似乎你会说，还有很多思维本质的东西没有概括进去，人有记忆，图灵机有么？其实，只要图灵机具有了内部状态，它就相应的具有了记忆。因为记忆的本质 就是在头脑的内部存储了某种信息，这无疑可以表达成一个内部状态。比如上面讲到的具有饥饿和吃饱两种状态的小虫就会记住它的经历：如果吃到食物就用吃饱状 态来“记住”食物的存在。
似乎图灵机模型中不包括学习，因为学习就意味着对程序的改变，而图灵机是不能在运行过程中改变它的程序的。然 而，我们不难假设，你实际上并不能打开 一个人的脑袋来看，所以它的实际程序规则你是不知道的。很有可能一个图灵机的规则非常多，在大多数情况只在少数几个规则里面转，但一旦不同的外部信息激活 了它的某些内部状态，它就可能激活另外一些之前没有使用过的规则，这样它的行为就发生了本质上的变化。对于外界观察者来说，它似乎会学习了！而实际上，这 个图灵机的程序一点都没变。
现代商业上使用的计算机，使用硬布线来执行简单操作，它们的做法远比图灵机执行加、减、乘、分支……等操作更机巧。但是，值得注意的事实就是这些计算机都无法超过图灵机。尽管图灵机朴实简单，但市场上计算机能计算的任何问题它都有能力计算。确实，图灵机只是一台抽象的、或者概念的计算机，但它能做的事远比任何一台具体的计算机多。这是因为具体的计算机只具有有限的存储器，它们的操作速度受到现实世界各种限制。当然图灵机假设纸带有足够长，这说明有些任务，不给予它们无限的工作存储空间和无限的时间，图灵机还是不能执行的。
最后看看真正的图灵机工作的时候是什么样子：
参考文献