布莱切利庄园,位于英国白金汉郡,二战密码破译大本营
布莱切利庄园在战时雇佣了1万人来参与和辅助密码破译工作
顺便说一下,英格玛并不是德国在二战期间所用的唯一一种密码机。从1941年开始,德国人使用了一种比英格玛更尖端精巧的密码机——洛伦兹密码机(Lorenz)。要破解它,需要用到当时最先进的全电子计算机——“巨人计算机”(Colossus),每台计算机中都装有几千个真空管。但是,这些都是图灵的同事汤米-弗劳尔斯(Tommy Flowers)的智慧之果,图灵并没有在这些进展中扮演关键性的角色。
人与机器
如今,尽管普通人对图灵最熟悉之处莫过于他对破译英格玛的贡献以及那个以他命名的实验——图灵测试,但是,图灵在数学上最重要的贡献却是他发表于1936年的论文《论可计算数及其在判定问题上的应用》(On Computable Numbers, with an Application to the Entscheidungsproblem),在这篇文章中他介绍了著名的图灵机。
受到逻辑学家库尔特-哥德尔(Kurt Gödel)传奇的“不可判定性”启发(即,任何数学系统中总是会存在不能被证明的命题),图灵论述的问题是,一个由有限数量规则构成的算法对任意函数的计算是否能达到任意高的精度。为了简便,图灵使用了数字而不是函数。举个例子说,π就是可计算的;即使是古希腊人也知道将π精确到小数点后任意位数的简单算法。
但实际上,这个问题已经被阿隆佐-邱奇(Alonzo Church)解答过了,后来他成为了图灵在普林斯顿大学的研究生导师。然而图灵的版本却为更多的人所记住,因为邱奇的解答蛰伏在纯粹而艰涩的数学术语中。为解决这个问题,图灵提出了一个概念——“机器”(如今被称为算法)。他的想法成为了现代计算机架构的基础,后来在一些机器上付诸实施,比如普林斯顿高等研究院1952年建成的一台机器。
阿隆佐-邱奇
这项工作碰巧让大众媒体认为是图灵发明了计算机。在这点上,那些撰稿人应该脸红,或者鼻子变长。最早的一批二进制机器建造者为今天的计算机引入了许多特征,这些人包括约翰-阿塔纳索夫(John Atanasoff)、乔治-斯蒂比兹(George Stibitz)和康拉德-楚泽(Conrad Zuse)等等。他们的工作几乎与图灵同时展开,当然不可能提前知道图灵的成果。
还有一个常被忽略的事实是,邱奇和图灵在可计算性问题上和哥德尔定理一样给出了否定的答案——算法不能将所有的数字或函数计算到任意精度。事实上,人们能够证明,在算法上不可计算的函数要比可计算的函数要多。
换句话说,出乎现代人意料之外——计算机并不能解决所有的问题。
本文来源:不详 作者:佚名