
艾伦·图灵(Alan Turing) 在1954年英年早逝后,作为计算机科学和人工智能领域的核心人物,他的声誉越来越高。在我们所知道的计算机还不存在的时代,图灵就把他的天才运用在了这样的问题上。他关于这个问题和其他问题的理论工作仍然是计算、人工智能和现代密码标准的基础,包括NIST推荐的标准。
从设计出最强大的计算机到加密标准,图灵短暂的一生也经历了一些曲折。

艾伦·图灵
在图灵的时代,数学家们在争论是否有可能制造一台单一的、万能的机器来解决所有可计算的问题。例如,我们可以计算出一辆汽车到达目的地的最节能路线,以及(原则上)一串氨基酸折叠成三维蛋白质的最可能方式。
另一个对现代加密很重要的可计算问题的例子是,较大的数字是否可以表示为两个较小的数字的乘积。例如,6可以表示为2和3的乘积,但7不能被分解成更小的整数,因此它是一个素数。
一些杰出的数学家提出了通用计算机的详细设计,这些计算机将遵循非常复杂的数学规则运行,制造这样的机器似乎非常困难,图灵的天才展示了一个非常简单的机器实际上可以计算所有可计算的东西。
他假想的装置现在被称为“图灵机”。这台机器的核心部件是一条胶带,它被分成不同的盒子。每个方框包含一个符号(如a,C,T, G代表遗传密码的字母)或一个空格,这条磁带类似于今天存储数据的硬盘驱动器。最初,磁带上的符号串对应于输入,包含要解决的问题的数据。字符串还充当计算机的内存。图灵机在磁带上写入数据,以便在以后的计算中访问。

该设备读取纸带上的单个符号,并在移动到另一个符号之前遵循是否更改该符号或保持其不变的指示。这些指令取决于机器的当前“状态”。例如,如果机器需要确定磁带是否包含文本字符串“TC”,它可以在前进方向扫描磁带,同时在状态“前一个字母是T”和“前一个字母不是C”之间切换。如果在状态“前一个字母是T”时,它读到“C”,它进入状态“发现它”并停止。如果它在输入的末尾遇到空白符号,它会进入“未找到它”的状态并停止。现在我们可以把这组指令看作是机器的程序。
这花了一些时间,但最终每个人都明白图灵是正确的:图灵机确实可以计算所有看起来可以计算的东西,对这台机器进行再多的添加或扩展也无法扩展其计算能力。
为了理解什么是可以计算的,确定什么是不能计算的是有帮助的。在以前学生们经常会遇到这样的问题:“我的程序已经运行了很长时间;卡住了吗?”这就是所谓的“停止问题”,学生们经常想知道为什么我们不能在不陷入无限循环的情况下检测到无限循环。事实证明,一个程序做到这一点是不可能的。图灵表明,不存在一台机器可以检测另一台机器是否停止。从这个开创性的结果引出了许多其他不可能的结果。例如,逻辑学家和哲学家不得不放弃自动检测断言(例如是否有无限多个质数)是真还是假的梦想,因为这是无法计算的。如果你能做到这一点,那么你就可以简单地通过询问“这台机器停止”这句话是真还是假来解决停止问题。
图灵继续为人工智能、理论生物学和密码学做出了基础性贡献

第二次世界大战期间,他对这最后一个课题的研究为他带来了荣誉和名声,当时他在改编和扩展波兰数学家发明的密码分析技术方面发挥了非常重要的作用。这项工作打破了德国Enigma机器的加密,为战争做出了重大贡献。
图灵是同性恋。二战结束后,1952年,英国政府判定他与一名男子发生性关系。他只是通过接受现在所谓的“化学阉割”才免于入狱。1954年,他死于氰化物中毒,享年41岁,最初被判定为自杀,但根据随后的分析,这可能是一场意外。50多年后,英国政府才向他道歉并“赦免”了他(在世界各地的科学家进行了多年的宣传活动之后)。今天,计算机科学的最高荣誉被称为图灵奖。
图灵的可计算性工作为现代复杂性理论奠定了基础。该理论试图回答这样一个问题:“在计算机可以解决的问题中,哪些问题可以有效地解决?”这里,“高效”指的不是几十亿年,而是毫秒、秒、小时或天,这取决于计算问题。
例如,目前保护我们的数据和通信的许多密码学依赖于这样一种信念,即在太阳变成红巨星并吞噬地球(目前预测为40亿至50亿年)之前,某些问题(如将整数分解为质因数)无法解决。NIST负责全世界使用的密码标准。没有复杂性理论,我们无法完成这项工作。

技术有时会给我们带来一个曲线,比如人们发现,如果制造出一个足够大且可靠的量子计算机,它将能够分解整数,从而打破我们的一些密码。在这种情况下,NIST的科学家必须依靠世界上的专家(其中许多是内部专家)来更新我们的标准。我们有充分的理由相信,量子计算机将无法破解NIST即将推出的密码学,其中一个原因是图灵的机器可以模拟量子计算机。这意味着复杂性理论给了我们一个强大的量子计算机所能做的限制。
但这是另一个话题了。现在,我们可以庆祝图灵为今天的计算技术提供了关键,甚至为我们如何解决迫在眉睫的技术问题提供了线索。









