数学

都听过图灵机,它的灵感来自哪儿?

秦曾昌 田达玮 共同发表于  2018-06-11 14:29

人类,从来都不缺计算工具。

从中国的算筹、算盘,到西方帕斯卡、莱布尼兹等制造的计算器,这些古老的计算工具虽然能够进行加减乘除、乘方以及开方运算,在当时大大地加快了人们的运算速度,但与我们今天所理解的计算机相去甚远——这些古老的计算器,往往只能完成某一项特定任务;而今天,在计算机上只要点开不同的程序,就能完成各种不同的任务。

这种能解决各式各样问题的计算机,都属于图灵机。

什么是图灵机?

图灵机是图灵在他24岁发表的论文(《论可计算数及其在判定问题中的应用》)中提出的一种抽象模型。这种当时只存在于想象中的机器由一个控制器、一个读写头和一根无限长的工作带组成的。纸带起着存储的作用;读写头能够读取纸带上的信息,以及将运算结果写进纸带;控制器则负责对搜集到的信息进行处理。

一个图灵机的示意装置。图片来源:GabrielF|wikipedia

图灵机的结构看起来非常简单,但事实上,它与算盘之类的古老计算器有本质的区别:如果在控制器中输入不同的程序,它就能够处理不同的任务。这意味着,图灵机实际上是一种通用计算机

虽然图灵机因图灵而得名,但给予图灵灵感的却很可能是著名的“失败”发明家查尔斯·巴贝奇。

“失败”的发明家巴贝奇

查尔斯巴贝奇(1791-1871)对数学和机械都有着极高天赋,他在18岁时以优异的成绩考入剑桥大学。在大学期间,巴贝奇注意到了一个现象:当时欧洲的数学用表存在大量的错误。一项普查发现,在40本数表中,有3700个错误,而且大部分是由于手工计算和印刷造成的。这让巴贝奇难以接受,他认为如果能用一台机器代替人工计算同时自动打印出数表,那么这些问题就可以得到解决。而这台机器,就是著名的“差分机”。

图片来源:wikimedia

当然,要制造这样一台机器需要巨大的资金来源,巴贝奇开始向政府寻求帮助。在政府看来,当时数学用表的错误确实给航运以及建筑业带来了极大的不便,如果巴贝奇的“差分机”能够成功,将会减少船只触礁以及房屋桥梁倒塌事故的发生,因此有意愿资助他。

于是,在政府的支持下,巴贝奇完成了能够进行4级拆分的差分机。这台差分机的运算速度之快和错误率之低已经远远领先于当时手工计算水平。

“差分机”的成功研制,让巴贝奇备受鼓舞。他打算继续研制精度更高、运算速度更快的“差分机2号”。也是在研制“差分机2号”的时候,巴贝奇开始构想另一种结构更简单,功能更全面的机器——分析机。“分析机”有一种被称为“孔卡”的结构,给“孔卡”编写不同的程序,就可以让分析机解决不同种类的问题。这一构想其实与图灵机的“控制器”异曲同工。

巴贝奇的分析机(部分测试版)。1833年,一位不满18岁的女孩被“分析机”的构想深深吸引(这个女孩便是历史上第一位程序员爱达,Ada Augusta Byron)。1842年,爱达热心地将一位意大利数学家发表的阐释巴贝奇分析机原理和性能的文章翻译成英文,并且在备注中,写下了一段程序,这段程序,被认为是第一段计算机程序。图片来源:Bruno Barral|Wikipedia

可惜的是,巴贝奇输给了时代。巴贝奇的概念太过超前,以至于当时的人们无法验证他的猜想,也无法建造出他理想中的机器(直到二十世纪末,人们才按照巴贝奇的设计造出了“差分机2号”)。

巴贝奇至死都没有见到“差分机2号”和“分析机”问世。而当时英国政府向巴贝奇资助的1.7万英镑,最终也打了水漂。这让不少人认为巴贝奇是个失败者,他的“分析机”构想也没有再引起人们的关注。

图灵机的诞生

直到近一个世纪后,大名鼎鼎的图灵提出了一种能模拟人类进行数学计算过程的机器,图灵称之为A-machine,也就是我们所熟知的图灵机。A-machine很大程度上模仿了人类处理问题的过程:它拥有一个类似于人眼和手的读写头能够读取信息以及输出信息;一条无限长的纸带,源源不断地提供信息以及供输出结果; 一个类似于我们大脑的控制器,能够根据问题不同,进行不同的处理。

理论上来说,任何能够用数学解决的问题都能交由图灵机来处理,这一构想与巴贝奇所追求的“完全由机器来分析和处理问题”十分一致。图灵的学生以及合作者罗宾·甘迪,也发现了巴贝奇分析机的理论中有不少与图灵机理论异曲同工之处,因此推测分析机是图灵机的灵感来源。

阿兰·图灵。图片来源:turingarchive.org

相较于巴贝奇,图灵是幸运的。他的理论在接下来的十几年时间里便得到了验证,并逐渐发展成为我们今天的计算机。

自图灵机模型提出以来,至今已经历了八十年时间。人们对图灵机模型进行拓展,诞生了一批改进版的图灵机,如双向无限带图灵机、多头图灵机、非确定型图灵机、多维图灵机等。但这些模型,仅是对运算速度等进行了提升,并没有提出超越图灵机的新模型。超越图灵机的伟大构想,说不定已经在酝酿中。

可以肯定的是,超越图灵机的全新计算机,必将给人工智能技术带来一次巨大的飞跃。(编辑:婉珺)

显示所有评论

全部评论(7)
  • 1楼
    2018-06-11 14:57 天降龙虾

    丘奇-图灵机。。。当年俺第一次接触算法理论科普的时候,只知道伟大的图灵,却一直很奇怪敢排在他前面的那个“丘奇”是谁。。。。。

    [0] 评论
  • 2楼
    2018-06-11 15:26 在雨夜

    一直都不懂计算机的原理。

    [0] 评论
  • 3楼
    2018-06-11 15:32 operabug

    理论上来说,任何能够用数学解决的问题都能交由图灵机来处理


    是不是意味着,超越图灵机,需要超越数学

    [2] 评论
  • 4楼
    2018-06-15 15:20 70米深的阳光
    引用@天降龙虾 的话:丘奇-图灵机。。。当年俺第一次接触算法理论科普的时候,只知道伟大的图灵,却一直很奇怪敢排在他前面的那

    丘奇就是发明lambda演算的那个哥们。图灵机和lambda演算在可计算性方面是等价的

    [0] 评论
  • 5楼
    2018-06-15 19:52 freefreemen

    或许地球不是殖民星球了,而是一个技术研发 星球了呀^@^

    [0] 评论
  • 6楼
    2018-06-16 11:49 mark_w

    本以为灵感来自一个什么瞬间的启示或者想象,结果却是来自一台更加复杂的机器。。。

    [0] 评论
  • 7楼
    昨天23:34 q68257962
    引用@operabug 的话:理论上来说,任何能够用数学解决的问题都能交由图灵机来处理 是不是意味着,超越图灵机,需要超越数学

    不是,那个p-np什么什么的还是没能证明。


    [0] 评论

显示所有评论

你的评论

登录 发表评论

秦曾昌
秦曾昌 北京航空航天大学副教授,果壳网科学顾问
田达玮
田达玮 中科院海洋研究所硕士,未来实验室科普策划

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:13691127034    网上有害信息举报专区    儿童色情信息举报专区