全球视点!图灵机:在没有计算机的时候,我们如何谈论计算?

2022-07-15 09:58:05   来源:商业新知网

人类的灵魂,也许只是图灵机的一个极为复杂的算法。

作者 | Lawrence C. Paulson


(相关资料图)

编译 | 王玥

编辑 | 陈彩娴

1950年10月,一篇题为“机器能思考吗”的论文横空出世。这篇论文中提出了一个令人细思极恐的测试,即在测试者与被测试者(一个真人和一台机器)隔开的情况下,通过通讯装置向被测试者随意提问,并让测试者猜测与自己对话的对方到底是真人还是机器。

在多次测试后,如果机器能平均让每个参与者做出超过30%的误判,那么这台机器就通过了测试,并被认为具有人类智能。

人们第一次意识到机器人可能具备人类智能,便是从此开始。这个测试便是令千万科幻爱好者津津乐道的图灵测试。这篇文章也为作者Alan Turing(艾伦·图灵)赢得了「人工智能之父」的桂冠。

而人工智能之路,或者说计算机发展史的源头,是一篇图灵在24岁时发表的论文。在这篇论文中,他给「可计算性」下了一个严格的数学定义,并提出著名的「图灵机(Turing Machine)」的设想。图灵机不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算装置,用来计算所有能想象得到的可计算函数。

因为图灵发明了图灵机,于是时不时便有人跳出来宣称图灵其实「发明了计算机」。然而,图灵机与实际计算机器的设计并不相同。图灵机甚至不是机器的抽象模型。事实证明(有图灵言论为证),图灵机是一个人在桌上的纸张上书写的模型。那么,图灵为什么要发明图灵机,而图灵机又将引领我们去向何方?

1

图灵的论文 “论可计算数”

解答这些疑问的最好办法是把课本放到一边,打开论文。如今,借阅一本1936年的期刊不需要填写借阅卡,也不需要等上一个小时让图书管理员从藏书室取来,我们只需要手捧一杯麦芽威士忌,在家里轻松访问谷歌即可。我们要寻找的那篇图灵论文如下:

论文地址:https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

论文中有一些错误,但瑕不掩瑜。正如Joel David Hamkins所说,图灵将可计算实数(computable real numbers)定义为具有可计算的十进制展开数,这实际上是行不通的,不过修正并不困难。

图灵在标题中就说明了这篇论文的写作意图:“论可计算数及其在「判定问题」中的应用 ”。其中“Entscheidungsproblem(判定问题)”询问是否存在一种有效技术来决定给定的一阶逻辑公式有效,即在所有解释中为真。

图灵将他的想法展开如下:

我们可以把一个正在计算实数的人比作一台只能满足有限数量条件q1,q2,... qR...的机器。这台机器中有一条长长的“纸带”穿过,纸带被分成很多个部分,这种一块一块的部分我们将其称为方块(square),每个方块都能承载一个“符号”...一些写下的符号会形成被计算的实数的十进制的数字序列,而其他的符号则只是“帮助记忆”的粗略笔记。这些粗略的笔记是可以擦掉的。我的论点是,这种在纸带上滑来滑去,滑到某个符号并对这个符号进行相应处理的运算方式,其中包括了所有用于数字计算的运算。

……

“可计算数”简单说来就是,其十进制的表达用有限的手段可计算的实数。按照我的定义,如果一个数的十进制的表达能被机器写下来,那么这个数就是可计算的。

图灵后续进行了定义和证明,这是一篇典型的数学论文,而不是典型的工程论文,在这种文章里读者想看到讨论如何实现文中所描述的某种机制。从图灵的标题和文章中我们可以看出,图灵主要关心的是一个实数到无限位小数的计算。

这篇论文还有许多其他重要贡献:

通用图灵机,以及以数字形式为机器编码的想法

如此编码的机器的停机问题,以及对角化的不可判定性

写罢这篇论文,图灵打开了理论计算科学领域的大门。

2

通用图灵机

我们不能确定是什么让图灵产生了通用图灵机(UTM)的想法,但一旦他想到了,他可能会认为通用图灵机的存在是显而易见的。因为图灵机的目的就是模拟一个在办公桌上工作的职员,而图灵机的操作和文员行为一样——根据机器状态和磁带符号,根据给定的转换规则列表执行这个或那个操作——显然需要一个图灵机来执行这样的例行任务。图灵的论文对于构造的细节有些粗略,但似乎没有人介意。

而如今,我们有了已经被设计得淋漓尽致的通用图灵机。几十年前,在剑桥大学,Ken Moody 博士编写了一个通用明斯基注册机:

链接:http://www.igblan.free-online.co.uk/igblan/ca/minsky.html

这样的机器有有限的寄存器,每个寄存器可以存储任意大的非负整数。它有一个有限程序,由三种不同类型的标记指令组成:

递增寄存器 R 并跳到标签 L ,或 R +→ L

测试/递减寄存器 R 并跳转到标签 L 0/ L 1,或 L 0↞R−→ L 1

中断。

这样的机器比图灵机更容易编程,尽管它们仍然不像真正的计算机。

Moody在 N 和 N×N 之间使用了标准的双射,将整数列表打包成单个整数。他编写了一个小型寄存器机器的小库,用于执行堆栈上推和从堆栈弹出等操作,并创建了一个让人想起真实处理器的获取-执行周期的设计。整个过程可见以下几张幻灯片。下图是机器本身:

下图则是机器的整体结构。(这两张图的作者都是剑桥大学理论计算科学教授Andrew Pitts。)

出人意料的是,这个机器的结构真简单!

3

停机问题

停顿问题显然是不可决定的。否则,许多数学上的猜想都会难以解决,比如费马大定理:只要写一个程序,搜索x, y, z, n>2,使 ,并问它是否终止。然而,停机的不可判定性必须被严格地表达和证明。

与大众看法相反,图灵的论文并没有讨论停机问题,而是讨论了一个与停机问题相关的特性,他称之为“循环性”(circularity)。如果图灵机「只写下有限数量的第一种符号」(即0和1),它就是循环性的。我想,循环性之所以重要,是因为图灵特别喜欢把实数近似为无限的二进制字符串。物理学家Christopher Strachey在1965年给《计算机杂志( Computer Journal )》的一封信中声称,图灵告诉他一个关于停机问题不可判定性的证明。

4

图灵和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对理论的不屑:尽管把机器编码为数字是对存储程序计算机的预期,但图灵的工作是纯粹的数学,没有任何工程意义。图灵对实际的计算机工程很感兴趣,但他多次试图参与到真正的工程里,却屡屡受挫。

而那些关于邱奇的言论又是如何评价的呢?

5

图灵和邱奇在普林斯顿

在图灵做研究的时候,许多研究人员关注的是“有效可计算性”的想法。此处我推荐读者看看邱奇的《初等数论的一个不可解问题》(见下图)。

论文链接:https://www.jstor.org/stable/2371045?origin=crossref

老实说,这篇论文读起来很吃力,但它能带我们身临其境。本文给出了一个λ-演算的定义,一个递归函数的定义(在Kleene(克莱尼)/Gödel(哥德尔)意义上),以及λ-演算中范式的存在性和等价性的一些不可判定结果。邱奇和克莱尼已经证明了λ可定义函数和递归函数的等价性;而当图灵在普林斯顿的时候,λ可定义函数和图灵可计算函数之间的等价性也得到了证明,于是我们便得到了邱奇-图灵论题,这个论题的指的是有效可计算的函数恰恰是那些数学上等价类中的函数。

6

邱奇-图灵论题正确吗?

正如人们常说的那样,我们无法证明这个论题正确与否,因为「有效可计算」不是一个精确的概念。我们可以把图灵可计算函数看作是一个颇为包容的类,因为其包括了许多在宇宙生命周期内无法计算的函数。借助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科技评论 , RAD极客会推荐阅读,不代表RAD极客会立场,转载请注明,如涉及作品版权问题,请联系我们删除或做相关处理!

关键词: 停机问题 可计算函数

上一篇:
下一篇:
精彩阅读

全球视点!图灵机:在没有计算机的时候,我们如何谈论计算?

热点

人类的灵魂,也许只是图灵机的一个极为复杂的算法。

世界动态:【《量子商业》】:​【区块】如何降维打击“企业”(一)

热点

高维度的行为,对低维度的行为可以产生精确且必然的影响,且低维度的行为无论如何改变,也无法抵御。

讯息:用友YonSuite三年引领SaaS产业跨越式发展

热点

YonSuite的创新和实践也将为更多的SaaS企业提供借鉴,开启中国SaaS产业的黄金十年。

世界快播:赵建良|基于区块链信任的新型产业关系和企业数字化前景

热点

区块链被称为信任机器,正在深入影响互联网时代的信任体系。

每日消息!趣链联合红洞发布《联盟链运营治理框架》白皮书

热点

趣链科技创始人兼首席执行官李伟博士受邀出席演讲并在会上发布《联盟链运营治理框架》、《联盟链运营治理最佳实践》白皮书。

天天短讯!BOE(京东方)《财富》中国500强排名跃升至第57位

热点

7月12日晚间,2022年《财富》中国500强榜单重磅发布。

当前短讯!WPS:最晚明年年底前彻底关闭广告

热点

7月11日,有博主爆料WPS探测出敏感词后,会删除存在云端上的文件,就连用户本地文件也会删除。

世界聚焦:2022年上半年广电+四大运营商政企市场战绩出炉!

热点

日前,行业发布了2022年上半年四大运营商战绩。

焦点快报!亮见01期丨弃购推特:马斯克「开不起」440亿美元玩笑,真后悔报价太贵

热点

马斯克收购推特一波未平,一波又起,双方在收购案的态度上,都发生了180度大转弯。

天天微动态丨抖音为小红书唱颂歌

热点

字节为何必须“抄袭”小红书?

财富

今日要闻!茅台冰淇淋,再换个“姿势”拥抱年轻人

资讯

茅台冰淇淋,再换个“姿势”拥抱年轻人,一“瓶”酒,两“桶”油,跨界真会玩。

天天短讯!薇诺娜首投的国货美妆「方里」,靠专注亚洲底妆年销破2亿

资讯

薇诺娜首投的国货美妆「方里」,靠专注亚洲底妆年销破2亿,90%的全球底妆品牌都在专研欧美人群,而方里却想做更适合亚洲人的底妆专家。

天天速看:“离谱”音乐节,从涨价开始

资讯

“离谱”音乐节,从涨价开始,一流价格,几流演出?

天天快播:Web3是互联网人的机会,却不是大厂的未来

资讯

Web3是互联网人的机会,却不是大厂的未来,“Web2的企业在Web3没有想象中的拉胯。”

天天微头条丨有多少男人愿意为“地中海”花钱?

资讯

有多少男人愿意为“地中海”花钱?,植发不是一门好生意

每日头条!微信读书不再“免费”,腾讯的“试验田”废了?

资讯

微信读书不再“免费”,腾讯的“试验田”废了?,2亿用户的微信读书,对腾讯价值何在。

观点:火爆伪风口:汽车电池回收

资讯

火爆伪风口:汽车电池回收,有一系列束缚行业发展的问题

当前速讯:大厂的“小红书梦”该醒了

资讯

大厂的“小红书梦”该醒了,再造“小红书”的接力棒传到了抖音手上。

全球播报:产品经理不香了:逃离大厂,丢掉理想

资讯

产品经理不香了:逃离大厂,丢掉理想,“面试造飞机,进来拧螺丝”。

天天百事通!海外创投丨「Wefox」获4亿美元D轮融资,Mubadala Investment Company领投

资讯

海外创投丨「Wefox」获4亿美元D轮融资,MubadalaInvestmentCompany领投,「Wefox」于2015年在柏林成立,拥有一支内部和外部经纪人团队,销售各种保险产品。

世界动态:【《量子商业》】:​【区块】如何降维打击“企业”(一)

高维度的行为,对低维度的行为可以产生精确且必然的影响,且低维度的行为无论如何改变,也无法抵御。

讯息:用友YonSuite三年引领SaaS产业跨越式发展

YonSuite的创新和实践也将为更多的SaaS企业提供借鉴,开启中国SaaS产业的黄金十年。

世界快播:赵建良|基于区块链信任的新型产业关系和企业数字化前景

区块链被称为信任机器,正在深入影响互联网时代的信任体系。

每日消息!趣链联合红洞发布《联盟链运营治理框架》白皮书

趣链科技创始人兼首席执行官李伟博士受邀出席演讲并在会上发布《联盟链运营治理框架》、《联盟链运营治理最佳实践》白皮书。

天天短讯!BOE(京东方)《财富》中国500强排名跃升至第57位

7月12日晚间,2022年《财富》中国500强榜单重磅发布。

华盛顿地铁站首次亮相为视障人士扩展旅行路线

5月25日消息,一款旨在帮助视障人士或盲人行人使用公共交通工具的应用程序在华盛顿地铁站首次亮相。该应用程序名为Waymap,旨在为盲人和视

2022年情况又要变了!华硕高管:今年PC恐怕要供过于求

这两年来,由于疫情导致的居家办公及远程教育需求爆发,一直在下跌的PC市场枯木逢春,2021年更是创下了2012年以来的最快增长,然而2022年情

垃圾佬的心头好!西数新款固态盘SN740曝光

对于DIY垃圾佬来说,散片、拆机件、工包……这些名词怕是并不陌生。本周,西数推出了主要供应OEM厂商的新款固态盘SN740。SN740升级到了第五

虚假宣传、误导消费者 倍至冲牙器关联公司被处罚

后来者要想在激烈的市场竞争中立足,如果可以背靠巨头享受大树底下好乘凉的红利,那自然是皆大欢喜,没有这个福气,也大可凭借自己一步一个

吉利几何EX3功夫牛高居榜首,4月投诉量230起

近日,车质网发布了2022年4月车型投诉排行八卦(前30名),其中有不少产品的出现属实让人没想到。具体来看,吉利几何EX3功夫牛高居榜首,4月

“说好了未达到目标全额退款,结果都是骗人的!”

春天不减肥,夏天徒伤悲。一波减肥大军抱着坚定的信念踏上征途,发现身边各式各样的高端减肥训练营正打着健康减肥封闭管理保质保量包吃包住