您现在的位置是:首页 > 人工智能人工智能
图灵机:在没有计算机的时候,我们如何谈论计算?
cc博主2022-07-13【人工智能】505人已围观
作者 | Lawrence C. Paulson
编译 | 王玥编辑 | 陈彩娴1950年10月,一篇题为“机器能思考吗”的论文横空出世。这篇论文中提出了一个令人细思极恐的测试,即在测试者与被测试者(一个真人和一台机器)隔开的情况下,通过通讯装置向被测试者随意提问,并让测试者猜测与自己对话的对方到底是真人还是机器。
在多次测试后,如果机器能平均让每个参与者做出超过30%的误判,那么这台机器就通过了测试,并被认为具有人类智能。
人们第一次意识到机器人可能具备人类智能,便是从此开始。这个测试便是令千万科幻爱好者津津乐道的图灵测试。这篇文章也为作者Alan Turing(艾伦·图灵)赢得了「人工智能之父」的桂冠。
而人工智能之路,或者说计算机发展史的源头,是一篇图灵在24岁时发表的论文。在这篇论文中,他给「可计算性」下了一个严格的数学定义,并提出著名的「图灵机(Turing Machine)」的设想。图灵机不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算装置,用来计算所有能想象得到的可计算函数。
因为图灵发明了图灵机,于是时不时便有人跳出来宣称图灵其实「发明了计算机」。然而,图灵机与实际计算机器的设计并不相同。图灵机甚至不是机器的抽象模型。事实证明(有图灵言论为证),图灵机是一个人在桌上的纸张上书写的模型。那么,图灵为什么要发明图灵机,而图灵机又将引领我们去向何方?
图灵的论文 “论可计算数”
解答这些疑问的最好办法是把课本放到一边,打开论文。如今,借阅一本1936年的期刊不需要填写借阅卡,也不需要等上一个小时让图书管理员从藏书室取来,我们只需要手捧一杯麦芽威士忌,在家里轻松访问谷歌即可。我们要寻找的那篇图灵论文如下:
论文地址:https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf论文中有一些错误,但瑕不掩瑜。正如Joel David Hamkins所说,图灵将可计算实数(computable real numbers)定义为具有可计算的十进制展开数,这实际上是行不通的,不过修正并不困难。
图灵在标题中就说明了这篇论文的写作意图:“论可计算数及其在「判定问题」中的应用 ”。其中“Entscheidungsproblem(判定问题)”询问是否存在一种有效技术来决定给定的一阶逻辑公式有效,即在所有解释中为真。
图灵将他的想法展开如下:
我们可以把一个正在计算实数的人比作一台只能满足有限数量条件q1,q2,... qR...的机器。这台机器中有一条长长的“纸带”穿过,纸带被分成很多个部分,这种一块一块的部分我们将其称为方块(square),每个方块都能承载一个“符号”...一些写下的符号会形成被计算的实数的十进制的数字序列,而其他的符号则只是“帮助记忆”的粗略笔记。这些粗略的笔记是可以擦掉的。我的论点是,这种在纸带上滑来滑去,滑到某个符号并对这个符号进行相应处理的运算方式,其中包括了所有用于数字计算的运算。……
“可计算数”简单说来就是,其十进制的表达用有限的手段可计算的实数。按照我的定义,如果一个数的十进制的表达能被机器写下来,那么这个数就是可计算的。
图灵后续进行了定义和证明,这是一篇典型的数学论文,而不是典型的工程论文,在这种文章里读者想看到讨论如何实现文中所描述的某种机制。从图灵的标题和文章中我们可以看出,图灵主要关心的是一个实数到无限位小数的计算。
这篇论文还有许多其他重要贡献:
通用图灵机,以及以数字形式为机器编码的想法
如此编码的机器的停机问题,以及对角化的不可判定性
写罢这篇论文,图灵打开了理论计算科学领域的大门。
通用图灵机
我们不能确定是什么让图灵产生了通用图灵机(UTM)的想法,但一旦他想到了,他可能会认为通用图灵机的存在是显而易见的。因为图灵机的目的就是模拟一个在办公桌上工作的职员,而图灵机的操作和文员行为一样——根据机器状态和磁带符号,根据给定的转换规则列表执行这个或那个操作——显然需要一个图灵机来执行这样的例行任务。图灵的论文对于构造的细节有些粗略,但似乎没有人介意。
而如今,我们有了已经被设计得淋漓尽致的通用图灵机。几十年前,在剑桥大学,Ken Moody 博士编写了一个通用明斯基注册机:
链接:http://www.igblan.free-online.co.uk/igblan/ca/minsky.html
这样的机器有有限的寄存器,每个寄存器可以存储任意大的非负整数。它有一个有限程序,由三种不同类型的标记指令组成:
递增寄存器R并跳到标签L,或R+→L
测试/递减寄存器R并跳转到标签L0/L1,或L0↞R−→L1
中断。
这样的机器比图灵机更容易编程,尽管它们仍然不像真正的计算机。
Moody在N和N×N之间使用了标准的双射,将整数列表打包成单个整数。他编写了一个小型寄存器机器的小库,用于执行堆栈上推和从堆栈弹出等操作,并创建了一个让人想起真实处理器的获取-执行周期的设计。整个过程可见以下几张幻灯片。下图是机器本身:
下图则是机器的整体结构。(这两张图的作者都是剑桥大学理论计算科学教授Andrew Pitts。)
出人意料的是,这个机器的结构真简单!
停机问题
停顿问题显然是不可决定的。否则,许多数学上的猜想都会难以解决,比如费马大定理:只要写一个程序,搜索x, y, z, n>2,使,并问它是否终止。然而,停机的不可判定性必须被严格地表达和证明。
与大众看法相反,图灵的论文并没有讨论停机问题,而是讨论了一个与停机问题相关的特性,他称之为“循环性”(circularity)。如果图灵机「只写下有限数量的第一种符号」(即0和1),它就是循环性的。我想,循环性之所以重要,是因为图灵特别喜欢把实数近似为无限的二进制字符串。物理学家Christopher Strachey在1965年给《计算机杂志(Computer Journal)》的一封信中声称,图灵告诉他一个关于停机问题不可判定性的证明。
图灵和Maurice Wilkes
2009年9月,David P. Anderson采访了Maurice Wilkes,他对图灵的看法却与大众恰恰相反:
David P. Anderson:你认为图灵1936年发表的判定问题论文的重要性何在?Maurice Wilkes:我觉得一个工程师会把存储程序(stored program)的想法当成类似三位一体的重要理论,并会说:"这绝对是一流的,就应该按这办法做"。
那篇论文中的思想与我所说的没有任何具有实际意义的区别。他能发表那篇论文已经很幸运了, 我的意思是阿隆佐·邱奇(Alonzo Church)用其他方法得到了同样的结果。
文章地址:https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
需要注意的是,在接受采访时,Maurice Wilkes已经96岁高龄了,他本人是著名的计算机先驱,EDSAC(Electronic Delay Storage Automatic Calculator,即电子延迟存储自动计算器)之父。在他这段奇怪的回答中,可以看出他对图灵崇高地位的嫉妒。这两个人显然合不来!我们也看到了Maurice Wilkes对理论的不屑:尽管把机器编码为数字是对存储程序计算机的预期,但图灵的工作是纯粹的数学,没有任何工程意义。图灵对实际的计算机工程很感兴趣,但他多次试图参与到真正的工程里,却屡屡受挫。
而那些关于邱奇的言论又是如何评价的呢?
图灵和邱奇在普林斯顿
在图灵做研究的时候,许多研究人员关注的是“有效可计算性”的想法。此处我推荐读者看看邱奇的《初等数论的一个不可解问题》(见下图)。
论文链接:https://www.jstor.org/stable/2371045?origin=crossref
老实说,这篇论文读起来很吃力,但它能带我们身临其境。本文给出了一个λ-演算的定义,一个递归函数的定义(在Kleene(克莱尼)/Gödel(哥德尔)意义上),以及λ-演算中范式的存在性和等价性的一些不可判定结果。邱奇和克莱尼已经证明了λ可定义函数和递归函数的等价性;而当图灵在普林斯顿的时候,λ可定义函数和图灵可计算函数之间的等价性也得到了证明,于是我们便得到了邱奇-图灵论题,这个论题的指的是有效可计算的函数恰恰是那些数学上等价类中的函数。
邱奇-图灵论题正确吗?
正如人们常说的那样,我们无法证明这个论题正确与否,因为「有效可计算」不是一个精确的概念。我们可以把图灵可计算函数看作是一个颇为包容的类,因为其包括了许多在宇宙生命周期内无法计算的函数。借助Ackermann函数,我们可以很容易地得到范例。
Ackermann函数的现代形式如下:
文章链接:https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html
如果你定义f(n)=A(n,n),就不能指望计算出偶数f(4)。g(n)=A(4,n)尽管是原始递归,但几乎无法计算。
尽管在20世纪30年代之前都还没有数字计算机,但有效可计算性的概念已为数学家所熟知。有效性的概念在希腊几何的直线结构和圆规结构中就早已出现,有效性也是判定问题和希尔伯特第十问题的组成部分。与哥德尔的递归函数和邱奇的λ微积分相比,图灵的概念的天才之处在于其显然是正确的。哥德尔自己也不确定他的递归函数是否抓住了计算的思想,我们也不清楚邱奇的想法是否正确。唯有图灵的想法简单而自然。图灵的想法与其他模型在可证明性上是等价的,并为所有这些模型提供了合理解释。他在1937年发表的论文《可计算性和λ-可定义性》中指出了这一事实。
本文旨在证明作者提出的可计算函数与邱奇的λ-可定义函数以及由埃尔布朗和哥德尔所提出的并由克莱尼发展的一般递归函数是相同的。这几个相同的函数都证明了每个X-定义函数都是可计算的,并且每个可计算函数都是一般递归的。注意,图灵写的是「可计算的」,而我们要写「图灵可计算的」。
原文链接:
https://lawrencecpaulson.github.io//2022/07/06/Turing_Machines.html更多内容,点击下方关注:扫码添加 AI 科技评论 微信号,投稿&进群:雷峰网(公众号:雷峰网)
雷峰网版权文章,未经授权禁止转载。详情见转载须知。
相关文章
- 微软新成立 AI4Science 团队,机器学习大牛 Christopher Bishop 担任主任,刘铁岩任北京负责人
- 揭秘嘉立创致胜市场的关键,为什么它能做到?
- 齐向东:合规是各类数字化业务安全开展的前提
- 华为汽车又一关键人物流失,车BU首席架构师离职,内部多位关键人物已相继出走
- 2022年《财富》中国500强排行榜揭晓;腾讯CISG调整组织架构:成立智慧行业九部,负责运营商行业大客户拓展;Facebook 母公司 Meta 悄然实行末位淘汰制 | 雷峰早报
- 英伟达正将其在AI领域的成功经验复制到量子计算
- 美团多位管理层变动,快手前高管仇广宇已加盟,暂任王兴的助理
- 乐视,悄悄起死回生了?
- 腾讯CSIG成立政企业务线,李强担任政企业务总裁
- UIUC 李博:从技术角度实现 AI 可信,从博弈论、对抗攻击,到逻辑推理
猜你喜欢
最新免费小火箭节点分享-永久v2ray机场链接-每日更新(2022/10/4)
技术好文今天星期二,cc博主继续为大家提供最新免费小火箭节点分享-永久v2ray机场链接,更新于2022年10月04日17点更新,最新v2ray节点分享。需要付费节点下方推荐点击v2rayn出门右拐即可,周末更新资源部分可用,免费资源不易,请大家珍惜。CC博客将分享持...
阅读更多独家|微软亚太研发集团 CTO 王永东升任集团主席,洪小文国内不再担任职务
人工智能作者 | 李梅编辑 | 陈彩娴AI 科技评论独家获悉,近期,现任微软全球资深副总裁、微软(亚洲)互联网工程院院长王永东,已从微软亚太研发集团 CTO 升任为集团主席。这意味着,原微软亚太研发集团主席洪小文已卸任,且在国内不再担任任何职务。2021 年 7 月...
阅读更多扬言「吊打」英伟达的AI芯片公司,快被现实打趴了
芯片作者 | 包永刚编辑 | 王亚峰与三四年前国内云端AI芯片公司们在发布会的PPT上超越英伟达的豪言壮志形成鲜明对比,如今这些公司在现实里到处碰壁,许多连北都找不着。“刚过完年,我们把芯片送到客户那里测试时,才发现我们的软件根本没办法满足客户应用场景的...
阅读更多理想汽车8月销量断崖下滑,位于同行倒数;三星内涵iPhone14创新不足;字节表示无上市计划,飞书是未来大机会|雷峰早报
业界理想汽车:8月交付量4571辆,销量断崖下滑9月1日,多家新势力车企公布了2022年8月造车成绩单。其中,理想汽车8月仅交付4571台,同比下降51.54%,环比下降56.14%,再次陷入低谷,仅高于疫情最严重时4月的4167辆,销量出现断崖式下滑。8月交付...
阅读更多腾讯Q2财报:企业服务毛利水平持续改善,健康可持续战略初见成效
业界8月17日,腾讯发布2022年第二季度业绩报告,“金融科技及企业服务”业务单季收入422亿元,占总营收的31.5%,连续五个季度超过30%。本季度企业服务收入健康度显著提升,“健康可持续战略”初见成效。财报显示,由于优化收入结构、减少亏损项目和降低成本,企业...
阅读更多
热门文章
- 「11月24日」2024年V2ray/Clash/SSR/Shadowrocke澳大利裔日本免费节点
- 香港VPS低至6折93元/年,全场8折,香港CN2,洛杉矶CN2 GIA,洛杉矶9929,洛杉矶CMIN2,日本大阪/东京IIJ,日本BGP,韩国BGP,英国伦敦AS9929住宅IP
- 低至4折,2核4GB内存VPS/GPU独服 $2.99/月起,GPU VPS/GPU专用服务器 $13/月起,物理专用服务器$29/月起,可免费试用
- 知乎直答亮相“学术酒吧”开放麦,李开复、刘知远相聚“AI上头俱乐部”
- MIT 热门研究:AI 工具“带飞”科研,但也严重加速内卷
- 美国/香港VPS年付99元起,双核/2GB/15GB SSD/500GB流量@100Mbps带宽
- 国行 iPhone 16 相机控制也接入视觉智能了!可一键调用阶跃星辰智能助手「跃问」
- RISC-V要成为「显性」技术,到了关键时期
- 英伟达CFO称Blackwell需求量惊人,已向合作伙伴发出1.3万个样片
热评文章
「11月18日」2024年V2ray/Clash/SSR/Shadowrocke泰国-新加坡免费节点
「11月24日」2024年V2ray/Clash/SSR/Shadowrocke澳大利裔日本免费节点
MIT 热门研究:AI 工具“带飞”科研,但也严重加速内卷
国行 iPhone 16 相机控制也接入视觉智能了!可一键调用阶跃星辰智能助手「跃问」
知乎直答亮相“学术酒吧”开放麦,李开复、刘知远相聚“AI上头俱乐部”
黄仁勋亲述创业故事:两次都差点倒闭
低至4折,2核4GB内存VPS/GPU独服 $2.99/月起,GPU VPS/GPU专用服务器 $13/月起,物理专用服务器$29/月起,可免费试用
RISC-V要成为「显性」技术,到了关键时期
香港VPS低至6折93元/年,全场8折,香港CN2,洛杉矶CN2 GIA,洛杉矶9929,洛杉矶CMIN2,日本大阪/东京IIJ,日本BGP,韩国BGP,英国伦敦AS9929住宅IP
英伟达SC24六大技术亮点,不止加速超算500强