计算机怎样编程与计算思维 (10).pdf

信息技术基础：

计算机、怎样编程与计算思维（Python版）

“计算机科学之父”艾伦·图灵:

图灵机和图灵测试

艾伦·图灵

艾伦·麦席森·图灵(AlanMathisonTuring)是

英国的数学家、计算机科学家和逻辑学家，在

他年仅42岁的一生中，由于对理论计算机科学

的开拓性贡献，被后世称为“(理论)计算机科学

之父”和“人工智能之父”。他的理论使得计算

机真正成为了一门科学。

为了纪念他在计算机领域的卓越贡献，美国计算

机协会(AssociationforComputingMachinery,

ACM)于1966年设立了图灵奖(TuringAward)，用

于奖励“对计算机领域具有持久和重大的技术重

要性”的个人，此奖项是计算机科学领域最崇高AlanMathisonTuring

(1912-1954)

的奖项，有“计算机界的诺贝尔奖”之称

2

艾伦·图灵的生平

图灵于1912年生于伦敦，1931年进入剑桥大学学

习数学，1934年毕业。

1928年，伟大的德国数学家大卫·希尔伯特

(DavidHilbert)在一个国际会议上提出了三个深

刻的问题：数学是完备的吗？数学是一致的吗？

数学是可判定的吗？

第3个问题又称为判定问题(DecisionProblem,德

语：Entscheidungsproblem)：希尔伯特希望求解

出一个算法，该算法可以从已有的一组公理利用

逻辑规则来判定一个命题可证明或证否。DavidHilbert

(1962-1943)

3

艾伦·图灵的生平

一个计算问题的算法(Algorithm)是：存在一组明确的指令，机器通过

机械化地执行这组指令，对于给定的输入，在有限步内可以产生该计

算问题的输出结果。

判定问题的算法的输入是一个数学陈述，输出是真或假。

1936年，24岁的图灵发表论文“论可计算数及其在判定问题上的应用

”(OnComputableNumbers,withanApplicationtothe

Entscheidungsproblem)。在这篇文章里，他引入了一个有着正规形式

的假想的计算设备——图灵机(TuringMachine)。

在1936年的这篇论文里，图灵证明了停机问题(HaltingProblem)是不可计算的(uncomputable)。停机问题

问：是否能构造出一个算法在有限步(finitesteps)告诉我们任何一个给定的程序运行后最终会停止运行(停

机)还是会陷入无穷循环以至于永不停机。图灵证明了停机问题的算法是不存在的，作为一个特例说明了

希尔伯特的判定问题是不可解的。

4

艾伦·图灵的生平

在第二次世界大战(1939-1945)期间，图灵

在位于布莱切利公园(BletchleyPark)的英

国政府密码学校里工作，对纳粹德国通信布莱切利公园

使用的恩尼格玛密码机(Enigmacipher

machine)做密文分析，参与建造了机械电

子式的密码破解机“炸弹机”(Bombe)。之