5.1　西方

对高效能算法的探索可追溯到大约3000年前，人类第一次使用基本算术来做大数的加法。而我们的故事从20世纪30年代开始，当时人们开始建立算法过程的理论。

1.阿兰·图灵

我们为探索太空而发明了望远镜，借助它我们能看到宇宙遥远的地方，了解它早期的历史。我们建造了能看到原子的显微镜，也建造了巨大的机器用以击碎微小的粒子从而找到更小的粒子。我们甚至破译了人类的DNA。但是有一样事物，它出现在我们的桌上、车内，甚至口袋里，但我们仍然觉得它很神秘，这就是计算机。计算机到底是什么？

computer（计算机）这个词早在17世纪就出现了，那时还没有人想象过机器可以做数学运算。那时的computer是计算员，即做计算工作的人。刚刚兴起的银行业需要计算员来记录和追踪每一笔存款和借贷的账目。

根据《牛津英语字典》，第一次将computer用于指代能计算的设备是在1897年，而电子计算机投入使用是在20世纪40年代。computer的意义，从一种人变为几台庞大的机器，又变成了人们的日用品。

不要把计算机看成是机器，想想它的功能：接收信息，根据指令处理信息，然后产生输出。从功能角度讲，邮政服务是一台计算机：接收信件，解码地址，然后把信件分发投递到合适的位置。生物学过程也是一台计算机：接收DNA序列，产出维持生命所需各种功能的蛋白质。

而我们称之为计算的过程又是什么呢？有没有不能被计算的事物？这个谜题在电子计算机问世之前的1936年，就被伟大的数学家阿兰·图灵解开了。图灵研究了数学家的思考方式，并模拟这种思维过程发明了一个形式化的数学模型，我们现在称之为图灵机，已成为计算学的标准模型。

阿兰·图灵1912年生于伦敦。20世纪30年代初，他考入剑桥大学国王学院，展露出过人的数学才华。那段时间里，他从一个数学家的角度，思考了计算的本质。数学家在思考时有一定的方法步骤，尽管人的记忆容量非常有限，但是记录信息的纸和笔则可以敞开供应。数学家会在一页纸上匆匆写下一些笔记，写完一张纸后要么再用一张纸，要么回到之前写过的某张纸，对笔记进行一些修改。图灵受这个过程的启发，创造了一个形式化的计算模型，即我们所熟悉的图灵机。

图5-1　图灵机

尽管结构非常简单，但图灵宣称，他的机器模型可计算一切能被计算的事物。几乎在同一时间，阿隆佐·丘奇也宣称它的Lambda Calculus（λ演算，一种原始的编程语言）能做同样的事情。丘奇–图灵论题虽然在现代计算机发明之前就已产生，但它通过了时间的考验。图灵机能计算现有或将来一切能被计算的事物。任何其他计算机器模型的能力都不会超出图灵机。

你不一定非要理解图灵机的工作原理才能理解计算。只需要想想任意一种编程语言，假设可利用的存储空间是无限的。所有编程语言在功能上是等效的，并且其计算能力都等于简单的图灵机的计算能力。

图灵在1936年就指出，图灵机并不是什么都能计算。最著名的例子是停机问题，即没有计算机能通过查看一段代码就知道自己是会永远执行下去还是会最终停止。

在第二次世界大战期间，图灵在英国的密码破译工作中承担了重要的任务。战后，他开始考虑图灵机是否是以人脑为原型的。他引入了今天我们称之为“图灵测试”的判定方法，判定机器是否可以表现出类人的智能。假设你通过即时通信软件和别人聊天，你能判断和你聊天的是真人还是计算机程序吗？如果一个计算机能让大部分人误以为它是真人，它就通过了图灵测试。

不幸的是图灵的学术生涯半路夭折。他于1952年因同性恋行为被当时的英国司法机关判定有罪，这最终导致了他在1954年自杀。直到2009年，英国首相戈登·布朗才为当年政府对图灵的判决发表了一份官方道歉声明。

美国计算机协会以图灵的名字命名了计算机界的最高荣誉：图灵奖（等同于其他领域的诺贝尔奖），以表彰图灵为计算机科学和人工智能所做的开创性工作。本章提到的许多科学家都是图灵奖得主。