图灵是如何设计出图灵机的,背后的故事和对我们的启发是什么,估计99%的人不知道

发布者:梁刚健发布时间:2023-02-27浏览次数:698

原文链接:https://mp.weixin.qq.com/s/GiS_sdL2_Kx6FszgrFFWOA

原创 图灵君 图灵人工智能


                         


  1. 1.  图灵其人



世界上可以分为两类人:计算机专业的人和非计算机专业的人。

图灵在计算机专人的心目中可以说是如雷贯耳,他被称为计算机之父,也被称为人工智能之父,英国数学家、逻辑学家,1931年图灵进入剑桥大学国王学院,毕业后到美国普林斯顿大学攻读博士学位,第二次世界大战爆发后回到剑桥,后曾协助军方破解德国的著名密码系统Enigma,帮助盟军取得了第二次世界大战的胜利。由美国计算机协会(ACM)于1966年设立的计算机奖项,名称就称取自图灵,旨在奖励对计算机事业作出重要贡献的个人。图灵奖对获奖条件要求极高,评奖程序极严,一般每年仅授予一名计算机科学家。图灵奖是计算机领域的国际最高奖项,被誉为“计算机界的诺贝尔奖”。每年该奖的获得者都是大家讨论的焦点。

对非计算机专业人来说,对图灵的了解莫过于电影《模仿游戏》,《模仿游戏》是由莫腾·泰杜姆执导,本尼迪克特·康伯巴奇、凯拉·奈特莉等主演的传记电影。该片改编自安德鲁·霍奇斯编著的传记《艾伦·图灵传》,讲述了“计算机科学之父”艾伦·图灵的传奇人生,故事主要聚焦于图灵协助盟军破译德国密码系统“英格玛”,从而扭转二战战局的经历。该片获得第87届奥斯卡金像奖最佳改编剧本奖,以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的7项提名。从而使图灵走进了大众心中。


《模仿游戏》剧照

2019715日,英格兰银行行长马克·卡尼在展示新版50英镑纸币,艾伦·图灵登上英国50英镑新钞。英国广播电台(BBC)称,面值50英镑的新钞将于2021年底进入流通。这更进一步让图灵这个名字让世界所了解。


50英镑新钞

大家可能不知道,在设计新版50英镑时,英格兰银行向公众征求意见,不到6周就收到了近23万份提名,涉及 989名科学家。最后,由科学领域专家组成的委员会拟定了一个候选名单。入围名单的个个都是大神,比如霍金、拉马努金、保罗狄拉克、罗莎琳富兰克林、玛丽安宁等等,还有图灵。


最后,图灵胜出,足见图灵的贡献被大众的认可度不是一般的高。


  1. 2.  图灵的成就




在人工智能领域,图灵被称为“人工智能之父”,「机器能思考吗?」这道测试题至今仍然是人工智能领域最著名也最具争议的议题之一。图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制,但此项工作严格保密。直到70年代,内情才有所披露。从一些文件来看,很可能世界上第一台电子计算机不是ENIAC,而是与图灵有关的另一台机器,即图灵在战时服务的机构于1943年研制成功的CO-LOSSUS(巨人)机,这台机器的设计采用了图灵提出的某些概念。它用了1500个电子管,采用了光电管阅读器;利用穿孔纸带输入;并采用了电子管双稳态线路,执行计数、二进制算术及布尔代数逻辑运算,1946年,图灵发表论文阐述存储程序计算机的设计。他的成就与研究离散变量自动电子计算机(Electronic Discrete Variable Automatic Computer)的约翰··诺伊曼(John von Neumann)同期。图灵的自动计算机与诺伊曼的离散变量自动电子计算机都采用了二进制,都以“内存储存程序以运行计算机”打破了那个时代的旧有概念。数学领域,他解决了困扰数学界30年之久的希尔伯特「可计算性与特判定问题」,是数学史上一个重要的里程碑。图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础。一般地,把一个判定问题归结为停机问题:“如果问题A可判定,则停机问题可判定.”从而由“停机问题是不可判定的”推出“问题A是不可判定的”。生物学领域,图灵第一个触及到了复杂系统的自组织问题,他首次提出了这样的课题:一锅无序混乱的「化学汤」中如何创生出了生命?现在,这门学科仍然是自然科学中的前沿显学。哲学领域,他基于人工智能和复杂系统提出的很多命题,至今还是哲学家思考和辩论的重要议题。计算机、人工智能、复杂系统……图灵的力量并不在于他解决了哪些问题,而在于他为人类开创了一系列全新的科学方向。在他死去60多年之后,这些方向仍然是人类最先锋、最前沿的研究领域。以上还仅仅是他学术方面的成就,他还有一个称呼「WWII codebreaker」,直到今日,外媒在提到他时仍如此冠名。



3.  是什么灵感让图灵设计出了图灵机


 


图灵是如何发明图灵机的?有资料证实,图灵是在研究数学理论上一个深奥的哲学问题时发明了图灵机,具有讽刺意味的是,这个机器诞生于完全抽象的研究,从来没有人想到它会有任何实际的用途,更别提它会影响人们的生活了。 

时间追溯到剑桥大学1935年的冬季学期,在剑桥大学的圣约翰学院,纽曼教授正在他的课程“数学基本原理”上课,这门课因为难度大所以教室的学生并不多,但是图灵确实这门课的学生之一,他正在讲台下专心致志地听讲。 

纽曼教授的课不但很有特色,而且每次都有“压轴戏”,这次压轴戏的内容是阐述哥德尔取得的一些惊人成果。哥德尔生性沉默寡言,但是非常聪明。在1931年,哥德尔就证明了算术系统的

完备性,这一成果也被称为“哥德尔不完备行定理”,至今仍是数学领域最令人震惊的发现之一。哥德尔不完备行定理表明:无论算术系统的形式规则是如何制定的,总会有一些算术公理无法通过规则来证明,就如简单的皮亚诺算术系统中的关系式2+2=4。这一惊人而又神奇的结论是纽曼最后几节课的主题。消除

完备性的唯一方法似乎是重置规则,使其前后自相矛盾,但这似乎不是一个完美的解决方案。 

哥德尔指出,数学中有些真实性无法被证明。这个结论令人震惊,甚至激怒了一些人,特别是哪些数学家。因为,数学家不仅倾向于认为所有真实的事物都可以被证明,而且认为所有重要的事物都应该能够被证明,因为只有通过清晰的、规则明确的严格证明才能带来确定性。 

纽曼在当天的演讲中谈论的不是哥德尔,而是大数学家希尔伯特,希尔伯特被誉为欧洲数学界的教皇。希尔伯特有句名言是“我们必须知道,我们必将知道”。1900年,在巴黎国际数学大会上的演讲中,希尔伯特向国际数学界提出了23个有待解决的数学难题,这为20世界的数学发展制订了计划。 

当天,纽曼正向学生介绍数学中“系统化”程序的概念,这是希尔伯特整个方法论体系中的核心概念。例如,我们在学校里学过的长乘法则就是一个典型例子,它很好地说明了数学家所谓的系统化程序的含义。也就是说,系统化程序就像简单的纸笔法,任何人都可以机械地按照步骤执行,而无需任何创意或者真知灼见。类似天分或者直觉的东西就不需要了。有经验的操作员甚至不需要知道程序的用途,就可以准确地执行它,而不必了解程序的目的、运作方式和原理。 

纽曼和学生说,这些系统化的数学程序的基本特征是可以通过机器来执行。这在当时是一种新颖的表达方式,纽曼的演讲激发了图灵的想象力。许多年后,纽曼回忆起图灵发明的通用图灵机说:“我相信这一切都是源于他参加了我关于数学和逻辑基础的课程。”纽曼认为,关于机器可以执行系统化程序的提议,启发了图灵去“尝试并说明一个完美的通用计算机器意味着什么”。事实证明,纽曼的演讲让图灵非常着迷,他疯狂地思考着,以至于对演讲内容的研究占据了图灵的多年的工作生涯。 

图灵经过自己的思考,19364月底,经过一番精心准备后,图灵拜访了纽曼,并给了纽曼一份《论可计算数及其在判定问题上的应用》的草稿。图灵发明了一种通用机器,这台理想化的机器由一个无限的内存(一个无限的纸带)和一个“扫描器”组成,扫描器沿着纸带来回移动,读取纸带上打印的内容,然后在纸带上进一步打印出更多的内容。在开始计算之前,机器的程序和计算所需的所有数据都已打印在纸带上。通过选取存储在纸带上各种不同程序,操作员可以让机器执行任何“人类计算机”可以执行的过程。这就是图灵称之为“通用机器”的原因。事实上,通用图灵机是对“人类计算机”高度抽象的理想化,但它同时也是一个全新的多功能的机器。此外,图灵还大胆地在基础数学的讨论中,引入了工程数学的概念。后来纽曼写道:“今天,我们很难意识到,在基础数学的讨论中引入纸带和纸带上的图样是多么大胆的创新。”1936年,图灵在《伦敦数学学会学报》上发表了一篇题为《论可计算数及其在判定问题上的应用》的生涩论文。如今,这篇论文被认为是现代计算机科学的基石。

这篇论文发表的背后还有一个插曲,在图灵准备把他的手稿邮寄给一家期刊编辑的时候,美国逻辑学家丘奇发表的论文副本也送到了剑桥。丘奇编写的由数学符号组成的论文,其中关于判定问题的研究成果与图灵的研究内容基本一致。根据学术规则,一旦有人发表了一个数学成果,除非其他人的论文有一些重要的不同或者全新的见解,否则不能再次署名发表。这次又是纽曼给图灵出谋划策。纽曼认为,图灵论文的意义远不止狭隘地应用于解决判定问题。他亲自给伦敦数学学会的编辑写信,声明即使丘奇的成果在先发表,也不应该阻止图灵的作品在协会期刊上发表。这样,这篇奠基性的论文才得以发表。论文发表后,图灵也振翅高飞,他选择前往数学和科学蓬勃发展的美国,并于丘奇合作一起进行数学研究。也正是丘奇,他率先使用图灵机一词指代图灵的发明成果。 

图灵致力于驳斥希尔伯特关于数学本质的权威观点,通用计算机的提出是驳斥其观点的关键一步,但也因此招致了希尔伯特的反驳。通过对通用计算机行为的推理,图灵能够证明有一些定义明确的数学问题是通用计算机无法解决的。这个结果同哥德尔的

完备性定理一样令人震惊。哥德尔慷慨地说,图灵向他展示了“正确的视觉”。利用图灵的发现,他成功地将

完备性定理的适用范围扩展到涵盖所有包含基本算术形式的数学系统中。数学中的

完备性几乎无处不在。可以说哥德尔和图灵给希尔伯特关于数学本质的观点带来了双重打击。 

尽管当时对图灵来说,纠正希尔伯特谬误的工作很重要,但是从今天的角度来看,这与他发明精妙的通用计算机相比,真的是不值一提。下面看看大名鼎鼎的图灵机吧! 


4.  图灵机的工作原理

 


图灵机由一个扫描仪和一个拥有无限存储空间的磁带组成,磁带被分割成一个个小方块,在扫描仪上来回移动,每个小方块可能是空白的,也可能包含一个符号,如“0”或“1”。扫描仪在任何给定时间下只能读取磁带上的一个小方块,因此一次最多只能看到一个符号。


图灵机


扫描仪能够擦除、打印小方块上的符号,并将磁带向左或向右一次移动一个小方块。此外,它还可以更改刻度盘(或者其他功能等效的设备)的位置。刻度盘位于扫描仪内部,我们可以把它想象成一个老式的怀表,但是上面只有一个指针。这个指针可以指向表盘边缘上的任意一个刻度,这些刻度被命名为iiiiii(就像怀表表面标记的小时刻度一样)。为每一个刻度定义一个名称是很有必要的,因为这关乎“状态”的显示(图灵很严肃地称它们为“m-配置”)。这个刻度盘为扫描仪提供了基本的短期记忆功能。图灵在1936年的论文(论可计算数及其在判定向题上的应用中介绍了图灵机。他在该文中提出的第一个图灵机例子非常简单易懂,试想这台机器从空白磁带开始工作,扫描仪仅在磁带上交替打印01,即01010…显然,这不是世界上最有用的计算,但它很好地说明了图灵机的运行方式。为了使示例更有趣,扫描仪在每个01之间留下一个空白方块。此外,扫描仪从起点开始向右运行。


交替打印01


图灵利用他所称的“指令表”来指导图灵机的动作(见图)。该指令表就是当今计算机程序的简化版。图灵机的指令表一共有4列,每一列都是指令缩写。R是让图灵机“将扫描仪重新定位到右侧一格”的缩写(这实际上是通过将磁带向左移动一格来完成的)L是“将扫描仪重新定位到左侧一格”的缩写(通过将磁带向右移动来实现)P0是“在当前小方块上打印0”

缩写,P1同理。所以图中第一行的意思是:“如果你在状态i下,并且正在扫描的方块是空白的,那么在扫描的方块上打0,将扫描仪向右移动一个方块,然后进人状态ⅱ。”扫描仪通过将刻度盘上的指针指向刻度ⅱ,来“记住”它刚刚完成的操作。如果明白了表格第一行的意思,也就理解了状态的含义:

  • 状态ⅱ:我刚刚打印了0

  • 状态iii:我刚刚在打印0的后面留下了一个空白的小方块。

  • 状态iv:我刚刚打印了1

  • 状态i:我刚刚在打印1的后面留下了一个空白的小方块。

状体

扫描空格

操作

下一状态

i

空白

P0R

ii

ii

空白

R

iii

iii

空白

P1R

iv

iv

空白

R

i

图灵机简单程序

注:图灵机可以通过按照这个指令表进行无休止地工作,来打印出所需的数字序列,并将交替的方块留空。

刚才提到的操作——擦除、打印、改变状态、向左或向右移动,是每个图灵机的基本动作(或称原子动作)。正如图灵所展示的,他的机器可以通过串联执行这些大量的基本动作来完成高度复杂的任务。值得注意的是,尽管图灵机看上去很简单,它却可以计算当今市场上任何一台电子计算机所能计算的一切。不仅如此,因为图灵机是抽象的——名义上的机器——拥有无限的磁带或内存空间,它甚至可以完成现实中所有计算机都无法完成的计算任务。图灵机也能够执行无休止的计算,如前文所述,成为无休止地打印0101的机器。另一个无休止计算的例子是计算无限不循环实数的每一位小数,例如π,一个永远没有终点的数字。数字π定义为圆的周长与其直径之比,其数值为3.14159265…图灵将π描述为一个“可

计算数”,意味着图灵机可以进行无休止的计算,一个接一个地吐出数字π后每一位小数。图灵还表明,与π相比,确实还有不可计算的无限不循环数字。

在《论可计算数及其在判定间题上的应用》中,图灵进一步阐述了指令表本身可以存储在图灵机的磁带上。图中的指今表可以写成如下内容:iP0RiiiiP1RiviiiP1RivivRi,其中“;”表示指令间的分隔符,“一”表示“空白”。程序员可以直接将这个指令表放到磁带上(每个符号占据一个单独的小方块)。事实上,图灵展示了如何编写一段代码的过程,并使其中每条可能使用到的指令都可以通过01的组合模式来表示,这意味着最终程序员在磁带上只需要打印01的字符。

图灵接下来介绍的是他的通用机。通用图灵机有一个特殊的指令表,工程师可以将其“硬连线”到扫描仪中,并且永远不会改变。这个指令表(图灵在《论可计算数及其在判定问题上的应用》中展示了其所有复杂的细节)使通用机能够读取并执行程序员存储在磁带上的所有指令。这是一个简单但深刻的想法,也是迈向现代计算机的第一步。


  1. 5.  图灵给我们的启发



人是经过上万年的进化、上千年的传承、几十年的学习而来的,要想获得成功。好的导师、合作伙伴以及自己的天赋都很重要。

  • (1)有一个能启发你研究兴趣的、指导你的导师。

  • (2)投入到一个有很好科研氛围的环境。

  • (3)有自己感兴趣的领域和天赋,并一直坚持下来,不要为世俗的名气和成功迷惑。


转自维基百科/百度百科/网络/;部分内容摘自《图灵传》等

版权声明

 版权属于原作者,仅用于学术分享