注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

科学松鼠会

让我们剥开科学的坚果

 
 
 

日志

 
 
关于我

什么是科学松鼠会? 我们认为,对于部分人来说,科学就像一枚枚难以开启的坚果,虽味美却不易入口。 我们希望自己能够像松鼠一样,打开科学的坚硬外壳,将有营养的果仁剥出来,让人们能够领略到科学的美妙。 我们试图让科学传播并且流行起来。

网易考拉推荐

计算的极限(四):机械计算的圭臬   

2013-10-21 13:11:17|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

本文作者:方弦

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限》系列

殊途同归

大洋彼岸寄来的论文,对于图灵来说,并不是什么好消息。在看到丘奇的论文后,图灵有过何等反应,至今恐怕已不可考。面对着一位在数理逻辑方面已然小有名气的职业数学家,与自己一起独立发现了相同的突破性结果。往好处想,这说明图灵自己的水平已经达到了当时数理逻辑研究的前沿;往坏处想,重复了别人的结果,哪怕是独立发现的,似乎都有些不对味儿。

然而,在下定论之前,图灵还有一件事情要搞清楚。他和丘奇对“可计算性”的定义,分别建筑在图灵机与λ演算之上。那么,在不同的基础上定义的两种“可计算性”,是貌合神离还是本为一体?

图灵机与λ演算,两者似乎都在平平无奇中暗藏玄机。作为计算模型,它们有很多相似之处,比如自我指涉的能力。但它们看起来又是如此不同,图灵机是一台在工程上能建造的机器,而λ演算则是一个彻头彻尾的数学模型。看起来,要回答这个问题,并非易事。

图灵机模型

lambda演算

图灵知道,丘奇也知道,他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中,一语带过的那个“机械化的运算”,即将被赋予精确的数学含义。但正因如此,踏出的第一步必须慎之又慎,尤其对于“可计算性”这个最基础的定义,必须做到毫不含糊。为此,为了消除模棱两可之处,图灵机与λ演算是否能力相当,这是个必须回答的问题。

知己知彼,百战不殆。为了解答这个问题,图灵开始钻研λ演算,试图弄清到底λ演算能计算什么。终于,他证明了,所有λ演算能计算的函数,他的图灵机也能计算,反之亦然。也就是说,λ演算与图灵机的计算能力是等价的,两种模型定义的“可计算性”实际上殊途同归。他将这个结果作为附录补充到了他的论文。

对于图灵来说,这既是个坏消息,也是个好消息。坏消息是,他的结果与丘奇的重复了,对于发表文章来说,这不是什么好事情。好消息是,他的结果与丘奇的重复了,但他对可计算性的定义与丘奇的截然不同,而且两种看似毫无关系的定义,在实质上是相同的,这说明,他们对可计算性的定义,这最初的一步踏出的方向是正确的。一个人提出的定义很可能忽视某个方面,但现在两个截然不同的定义引向相同的结果,在交叉印证下,几无出错之虞。

可以说,图灵的工作面世之日,正是可计算性理论呱呱坠地之时。

也难怪纽曼教授一开始不相信图灵的工作。仅仅二十出头,刚刚踏入科学界的年轻人,就解决了如此重要的问题,而且为一个全新的领域立下了奠基石,这种人,即使在剑桥这个英国顶尖学府,也可谓难得一见。倒不如说,一开始不相信,这才是正常的反应。

但即便不相信,数学证明就是证明。即使纽曼教授并不专精于数理逻辑,还是能看出图灵论文的过人之处。他决定为图灵争取发表的机会。

这并非易事。因为从结论上说,图灵重复了丘奇的结果,所以最初联系的几个期刊的编辑都婉拒了纽曼的要求:他们只看到了论文的结论,没看到论文的精髓。最后,纽曼找到了当时伦敦皇家学会学报的编辑,经过三催四劝,终于说服编辑发表图灵的文章。

《论可计算数,及其在可判定性问题上的应用》,图灵的这篇文章,后来被认为是伦敦皇家学会学报发表过的最重要的文章之一。

伦敦皇家学会学报

万变之宗

乘着远洋货轮,图灵的论文很快传到了大洋彼岸,在普林斯顿掀起了一阵旋风。

在普林斯顿高等研究院的哥德尔,与丘奇有过不少碰面的机会。他读过丘奇的论文,大概也听过丘奇本人介绍他的λ演算。但哥德尔对λ演算一直颇有微词。实际上,作为一种计算模型,λ演算从未得到他的认可。它与人们日常接触到的“计算”毫无相似之处,更像是符号的堆砌和推演。虽然其中的计算的确可以机械性地完成,但要证明这一点绝非易事。事实上,这是一个远非显然的定理,证明也相当复杂。总而言之,λ演算并不像机械的计算,更像智慧的推理。

实际上,哥德尔自己也有一套“机械计算”的模型,那正是他在证明哥德尔不完备性定理时发展出来的递归函数体系。这套体系将“机械计算”定义为递归函数能计算的内容,而递归函数,顾名思义,就是可以用某些递归方式定义的整数函数。但哥德尔对他自己的模型同样不满意,原因同样是他的模型似乎需要太多的聪明才智,不像一台机器。

但图灵的论文瞬间就令哥德尔为之折服。

任何人,只要看一眼图灵机的定义,都会认同图灵机的计算完全是机械演算,完全可以造出一台可以运作的实际的图灵机。而更重要的是,图灵机抓住了“机械计算”的神韵。

机械计算是什么?是机器可以做出的计算。但机器可以千奇百怪,要用三言两语抓住本质,似乎不太可能。那么,何不反其道而行之?与其想像这些机器共有的特性,不如寻找它们共有的限制。

这正是图灵在论文中的做法。他总结了以下几个机器计算的限制:

第一:一台机器只有有限个可以分辨的状态;一台机器能分辨的表示数据的符号只有有限种。

开关或开或合,电路或通或断,中间的变化是跳跃式的。即使是连续的电信号,由于不可避免的热噪声影响,通过测量能分辨出的状态同样只有有限个。虽然现代的计算机看似有无限可能,但这只是幻觉。CPU和内存中的电路,数量虽然庞大无比,但总归是有限的,它们的通断形成的不同状态亦是如此。同理,虽然符号、信号在细节上可以有无数种变化,但由于精度等问题,即使是人,也无法事无巨细将所有细节一一分辨出来,更何况机器。

这么多,记不住,头好晕……

第二:机器的每一步操作需要的时间有一个下限,而每次操作最多只能读入与改写外部有限个符号。在某次操作读写某处的符号后,下一步机器读写的符号与之前符号的距离应该是有界的。

由于物理的限制,不存在速度无限的物体。无论任何机器,都不能在有限的时间内作出无限次操作,当然也不可能有无限次读入与改写。同样,读写头移动的速度是有限的,所以两次操作读写符号的距离当然也有限制。

第三:在某步操作中,机器的行动完全取决于它当时的内部状态以及读取到的符号。

机器就是机器,它应该做的,就是按照预先规划的图纸一步一步执行。没有异想天开,没有灵光一现,只有照章办事,只有步步为营。

嗯,这样好多了,干活也有劲了

这几个限制看起来相当合理,甚至显得理所当然。但就从如此平平无奇的限制出发,图灵用缜密的逻辑说明了,一台服从这些限制的机器能计算的问题,必定可以用一台特定的图灵机解决。也就是说,任何一台服从这些限制的机器,无论设计如何精巧,构成如何复杂,它的计算能力都不可能超越图灵机,无一例外。

我们甚至可以说,图灵机的设计本身,正是这些限制的一种体现。图灵很可能一开始就意识到了这些限制,再由此出发,去定义他的图灵机。哥德尔之所以对图灵机击节叹赏,大概也正因蕴含在它定义中的,图灵对“机械计算”的深刻洞察。相比之下,虽然与之等价的λ演算也尚算精致,但对于“机械计算”只得其形未得其神,显然逊色不少。

现在,希尔伯特在他的问题中那模糊的“机械计算”,终于有了一个精确的定义:机械计算,就是图灵机能做的计算。这又被称为图灵-丘奇论题,正是可计算性理论的奠基石。

除了λ演算与递归函数以外,还有许多计算系统与图灵机等价。波斯特对应问题,计数器机,马尔可夫算法,甚至元胞自动机,这些计算模型都与图灵机等价。但以我们的后见之明来看,图灵机仍然是机械计算最自然最有用的模型之一。

最简单的通用图灵机

也正因这篇论文,图灵得到了到普林斯顿读博深造的机会,在丘奇的指导下,得以继续探索可计算性的无限可能。在大洋彼岸等待图灵的,又是可计算性理论的一篇新章。

计算的极限(四):机械计算的圭臬 - 科学松鼠会 - 科学松鼠会
  评论这张
 
阅读(1371)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017