艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日），英国数学家、逻辑学家，被称为计算机科学理论之父、人工智能之父，今天正好是其110周年诞辰。《科学美国人》曾这样评价图灵的一生：“个人生活隐秘又喜欢大众读物和公共广播，自信满怀又异常谦卑。一个核心的悖论是，他认为电脑能够跟人脑并驾齐驱，但是他本人的个性却是率性而为、我行我素、无法预见，一点也不像机器输出来的东西。”

一、奠计算机理论之基

20世纪前，人们普遍认为所有的问题类都是有算法的，计算研究就是找出算法来。但20世纪初，人们开始怀疑是否某些问题根本就不存在算法，即它们是不可计算的。1928年，数学家大卫•希尔伯特（David Hilbert）提出了一个问题：是否存在一系列有限的步骤，它能判定任意一个给定的数学命题的真假？这就是Entscheidungsproblem，德语“判定性问题”的意思。

为了回答可判定性问题，首先需要对“一系列有限的步骤”（也就是算法）进行定义，此时人们才发现对于算法、可计算性都没有准确的定义。

1936年5月，24岁的图灵完成了《论数字计算在决断难题中的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）。该论文定义了可计算函数，将计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述直观上具有机械性的基本计算程序，使任何机械(能行)的程序都可归约为这些动作。这种简单的方法以一个抽象自动机（后被称为图灵机）概念为基础，其结果是：算法可计算函数就是这种自动机能计算的函数。这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，图灵机不是具体的计算机，而是一种计算概念，奠定了现代可计算性理论的基础。

逻辑结构上图灵机由四个部分组成：

1. 一个无限长的存储带，带子由连续的存储格子组成，每个格子可存储一个数字或符号。
2. 一个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号。
3. 内部状态存储器，该存储器可以记录图灵机当前状态，并且有一种特殊状态为停机状态。
4. 控制程序指令，指令可根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作（左移还是右移），并改变状态存储器的值，令机器进入一个新的状态或保持状态不变。

图灵提出了通用图灵机（UTM，Universal Turing machine）的概念，相当于通用计算机的解释程序，奠定了计算机的理论基础，促进了通用计算机的设计和研制工作。

如今所有通用计算机都是图灵机的一种实现，两者的能力是等价的。当一个计算系统可以模拟任意图灵机（或者说通用图灵机）时，称其是图灵完备的（Turing complete）；当一个图灵完备的系统可以被图灵机模拟时，称其是图灵等效的（Turing equivalent）。图灵完备和图灵等效成为衡量计算机和编程语言能力的基础指标，几乎所有编程语言都是图灵完备的，即一款语言能写出的程序也可以用另一款语言实现。

图灵还指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度就要靠增加程序的长度和存贮量来解决，这种思想开启了计算机科学中计算复杂性理论的先河。

二、破不可破解之“迷”

2014年上映的模仿游戏记录了图灵在布莱切利的传奇时光。

二战时期，德国设计并使用称为“迷”（Enigma）的加密机器，被认为是不可破译的密码。该机器的心脏是一个有电线相连的转子，波兰人马里安·雷杰夫斯基(Marian Rejewski)通过密码分析实现了3个转子的Enigma的破译，但德国在1938年将机器上的转子增加到了5个，解密复杂度呈爆炸式增长。

1938年，图灵在白金汉郡的布莱切利公馆（Bletchley Park）参与到英国政府的密码破译项目中，他通过研制出了更先进的译码计算机——图灵炸弹机（Turing Bomba），并利用德国人的加密失误，成功破解Enigma。
后来，为了破解德国更先进的保密电传打字机Lorenz SZ，图灵于1943年主导研制成功CO-LOSSUS(巨人)，“巨人”共向英国和盟军指挥部发出了48000份超级机密电报，平均每小时破译的德国情报超过了11份，直接影响了二战的战局。

前英国首相温斯顿·丘吉尔曾表示，图灵在布莱切利的工作成果使战争至少提前2年结束，挽救了至少1400万人的生命。

战后，图灵进入国家物理研究所，并设计了属于最早一批电子计算机——自动计算机ACE（Automatic Computing Engine），实现了他心目中的通用图灵机。

三、开人工智能之先河

1950年图灵发表论文《计算机器与智能》（ Computing Machinery and Intelligence），提出著名的“图灵测试”，为后来的人工智能科学提供了开创性的构思。

图灵测试由计算机A、人类B和观测者C组成。计算机和人类分别在两个不同的房间里。观测者通过电传打字机与机器和人联系并进行提问，由计算机和人类分别做出回答。人类在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维。如果观测者听取他们各自的答案后，无法分辨哪个是人回答的，哪个是机器回答的，则认为该计算机具有了智能。

图灵还有一个不被人注意的工作，那就是他对数理生物学的研究。 1952 年 8 月 14 日他在《皇家学会哲学学报》发表了唯一的一篇生物论文 The chemical basis of morphogenesis（“形态生成的化学基础”）。

图灵在生物学上的焦点是生命的物理结构，其兴趣是有机体为什么和如何发展成特殊的形态，并用数学方法证明，最初是均匀的一定类型的动态系统，经过渐进的变化过程，基于涨落与扩散会导致空间不均匀性的出现，现在已经成为图案形成范畴的核心。 图灵还提出叶序的几何理论，他主要的兴趣是斐波那契叶序列，即用斐波那契数（Fibonacci number）解释植物叶子的形态，如树叶排列以及向日葵小花的排列。

图灵机、破译密码、人工智能……图灵献给世界太多伟大的作品，却没能在生前得到应有的名誉乃至起码的认可。1952年，他因同性恋的罪名被起诉，在坐牢和化学阉割之间，他无奈选择了后者，旁人的偏见和药物的副作用使他承受着精神和肉体的双重痛苦。1954年6月7日晚上，他躺在家里因氰化物中毒离开了人世，床头放着一个咬过的苹果。

1966年，美国计算机协会ACM（Association for Computing Machinery）设立计算机领域的最高奖项，图灵奖，素有“计算机界的诺贝尔奖”之称。2013年，英国女王伊丽莎白二世正式颁发皇家赦免，图灵终于得到了迟来的公道。2019年，英国的中央银行——英格兰银行宣布，图灵的肖像将出现在新版的50英镑纸币上，以此纪念这位改变了国家乃至整个世界命运的伟人。