图灵机的发明

图灵机的发明

第二次世界大战期间，战斗正在英伦三岛和英吉利海峡激烈地进行着。当德国法西斯的飞机轰炸英国机场时，机场上却空空如也，等待着他们的只有密集的高射炮火，德国法西斯最高统帅部碰到这种事已不止一次了。他们意识到了自己的密码联系已被英军破译，英军已掌握了他们的秘密军事通讯。纳粹头子急于在自己内部寻找叛徒以除后患。然而他们做梦也没有想到，英国军事当局并没有拿到密码本，而是一位年轻的英国数学家图灵用数学方法破译了德军使用优良的恩尼格玛发报机发出的任何密码。一位数学家曾经这样说过：“如果没有图灵发明的设备，真不知第二次世界大战的历史是不是会另个一样子！或许第二次世界大战的历史会重写。”这也许有点言过其实，但图灵的功绩确实很伟大。

1912年6月23日，图灵出生在伦敦的一个中上层家庭里。他自幼聪明伶俐，刻苦好学。1931年他进入剑桥大学后，他的多方面才能迅速爆发出来。1935年就以《关于高斯误差函数》的论文获博士学位，同时荣获史密思奖。在整个第二次世界大战中，他受聘于英国外交部的通讯处，用他特有的数学知识设计了破译密码的机器，获得了帝国勋章。

图灵的工作主要是把人们在进行计算时的动作分解成比较简单的动作。我们想象一个人在一张方格纸上做计算，他需要（1）一种贮存计算结果的贮存器，即纸张；（2）一种语言，表示加减乘除等操作和数字的符号；（3）扫描区，在计算过程中，看到的上下左右几个方格中的数字；（4）计算意向，即在计算的每一阶段打算下一步做什么。例如看到6＋9就要准备进位等；（5）执行下一步计算。图灵成功地把人的计算活动机械化，从理论上说，如果解方程，搞近似计算，无非是按照某种算法，告诉机器在遇到注视格中出现什么情况时按什么计算意向去执行下一步动作。因此，凡是人或其他机器执行的算法，图灵机都可以做到。这架机器就是我们所说的图灵机，通过上述大略描写，我们也许能大概揣测出图灵机为什么能破译密码了：因为拍电报无非是按一定的规则在一条纸带上穿孔，其规律正和计算机执行某种程序相同。因此我们就能够把密码和程序联系起来，通过设法检验程序，也就破译了密码。