3592 字

图灵机与可计算问题

最近读完了《艾伦·图灵传》,我其实比较抵触看个人传记,一来是我觉得传记虽然都是洋洋洒洒的大部头,但多半还会是断章取义;另一个原因则是传记的主题是人,所有材料都是围绕个体展开,很容易漏掉其他重要信息。这本书应该说还是挺不错的,但翻译者太多半吊子意会,说起来我打算看这本书也是因为多年前参加了这本书的翻译者苏椰的一个活动,他当时故弄玄虚说是把二战时谜机的破解方法与图灵机原理都写到传记里了。现在读完了我觉得他自己都未必搞明白谜机的破解,而图灵机的解释也乱七八糟,我没读过原文也不知道这锅是翻译者背还是作者背。

对图灵的评价

要评价图灵,或者说要评价任何一个天才级的人,同样需要另一个近似天才级的人。显然这本书作者还是够资格的,他应该是完全熟悉图灵的工作,这很不容易。图灵属于应用数学家,也就是说他本质上是个数学家,而数学在我看来特别不好掌握,理工科对数学的要求其实都是应用层面的。而图灵很厉害的地方在于他不但研究极为抽象的数学与逻辑学,还研究了如何使用数学来了解世界,从这个意义上,他更像是个工程师。我是没能力评价图灵的,但图灵的研究涉及物理、化学、生物等诸多学科,其扎实的数学基础让他可以灵活运用知识来解决问题,这里的问题指的是可计算问题。现在的分科教育让很多人觉得有些问题的解决是显而易见的,但其实每个解决工具都是个“地三鲜”产物,没有这些工具甚至都无法想象一些问题,我觉得在这点上图灵的贡献非常大。

可计算问题

数学经历过三次危机,第一次是无理数危机,解决方法是把提出无理数的那个人扔海里淹死了;第二次是无穷小危机,这锅在于微积分的发明与使用,求导数时无穷小量可以做分母,但又可以近似为零,这种“即…又…”的东西很难在逻辑上存在,解决方法是从定义上解决的,我看不懂也就不多说了;第三次危机就比较壮观了,是罗素针对集合论或者说希尔伯特的可判定性问题提出来的,最简单的版本就是理发师悖论,这个危机最后是哥德尔定理解决的,其实也不能算是解决,因为哥德尔给出的结论是完备形式系统的三个要素:完备性、一致性与有效公理化的存在性是不能同时存在的,用人话说就是一个含义为真的命题真值是不可证明的,这样理发师悖论就成了不可判定问题了,也算是基于证明后告诉大家都别瞎折腾完备数学体系了,搞出来你也证明不了。

这个第三次数学危机非常有趣,实际上这跟差不多同时期提出来的量子力学里测不准原理很接近,都是一种框架内不可能实现的“即…又…”的理论。有意思的是,金融学也存在蒙代尔不可能三角,现在的贸易战其实就在挑战国内政策制定者对这个原则的应对,保汇率资本就会外流,控制资本进出就会导致汇率跳水。而其实在分析化学特别是高通量分析时也存在一个固定时间内灵敏度与准确性不可兼得的现象。统计学习里也有误差-方差平衡的问题,你永远无法构建一个统计模型同时把误差跟方差降成零。这些出现在多个学科中的鱼和熊掌不可兼得的现象都暗示了一个人类认知的极限或最低成本,无论如何都无法突破极限或继续降低成本。

图灵机其实也是面对第三次数学危机的,当我们知道问题存在可证明与不可证明两种之后,下一个问题就是如何找出这两种问题的边界。这里我们把那些可证明或可解决的问题统称为可计算问题,这样我们现在就需要构建数学模型来判定问题是否可计算,图灵给出的答案就是图灵机。图灵机是一个很直观的模型,一条无限延伸的纸带、一个读写头与配套有状态的控制器。这个机器的功能也很简单:

  • 读取纸带上的信息到控制器
  • 控制器将纸带信息结合自身状态去查询内置程序
  • 根据程序指示修改状态、在纸带左右移动或修改纸带信息

乍看之下似乎很啰嗦,特别是要有状态,其实图灵机的状态是为了判定是否可以停机而设计的,而图灵机停机问题实际上就是理发师悖论。设想存在一个图灵机A与程序a,然后用图灵机B来判断A在程序a下是否可以停机,然后构建一个图灵机C,当B返回为可以停机时就死循环,返回不能停机时才停机。这样图灵机C其实就永远无法停机了,也就是说图灵用一种机械装置证明了停机问题不可计算,也就是间接说明了希尔伯特的可判定性问题无解。这里我们看到图灵把一个图灵机运行在了另一个图灵机内部,这大概就是函数递归思想的某种雏形。不过图灵机不能停机只是很特殊情况下的现象,如果我们仅仅考虑一般问题,那就是说绝大多数可计算问题都应该可以在图灵机上跑出答案来,也就是说图灵机其实是通用计算机的雏形。

通用计算机

计算机工作原理其实就是图灵机的高级版,纸带就是输入输出设备,控制器是机械的,程序是预先编程好的。现代计算机的原型是冯·诺伊曼搞出来的,他在运算器中事先内置操作并用带有操作码与地址码的指令来对存储器内数据进行运算与读写,说白了他把图灵机真正实现了出来。当然,冯·诺伊曼使用的是电路友好的二进制而图灵自己设计了一种别人几乎看不懂的32进制。从图灵机原理上我们会发现如果状态过多,那么程序编写难度是指数式上升的,因为你要对每个状态进行编程,否则这个机器就无法顺畅运行。状态多了运行会快但编程序就困难,后来有人证明自然对数的底数e是最佳状态数,四舍五入就是3个状态,但由于电子元器件就知道通或不通,所以两种状态是最方便使用的。同时,绝大多数可计算问题都可以变成加减法问题,通过布尔逻辑运算我们可以轻松实现一个加法计算的电子电路,这样我们就可以用一个内置累加器与指令的固定机械结构来进行运算了。要知道这个结构比ENIAC的结构要先进,那个结构要进行编程是要重新布线的,而在冯·诺伊曼结构上只需要重新编程组合指令就可以了。也正是这个结构导致了存在机器码、汇编语言、底层语言与高级语言的区别,层次越低,机器就越容易通过指令组合快速完成任务,但高层次的语言更接近人类的语言。本质上计算机还是个机械装置,其理解人只能通过机器码。

但书里面却指出,其实图灵在战后的一项重要工作也是做一个通用计算机,不过他却没有二战期间那么走运,各种资源限制与性格因素导致他被孤立甚至排挤出了核心团队。其实这里面有点分工问题,图灵是作为数学家加入的团队,但其实他也懂电子电路的一些知识,甚至他也想到了用水银延迟线来作为存储设备(水银延迟线是个很神奇的东西,用声电转化来存储信息)。不过这倒不怎么碍事,因为很快图灵就把兴趣转到了研究生物学现象中的数学原理了。

人工智能

图灵另一个很出名的成就就是图灵测试,图灵认为机器是可以具有智能的,因此他构想出了一个猜性别的测试,进而衍生为猜测对话的是人还是机器的测试。这点其实很有意思,图灵应该是当时少数清楚通用计算机运行原理的学者,而他也正是通用计算机机械原型的设计者,按说他最知道机器跟人的区别,但他却认为机器可以有智能。也就是说,原理上的不同并不是智能差异的论据,图灵可能想的更深了一层:人脑其实也是个机械,虽然原理到今天也没弄明白,而智能也就是出现在这个机械的各种生化反应之中的,那么同样作为机械,为什么就不能也有智能呢?也许早就有了只不过无法与人交流而已。

很多人认为人工智能不是真正智能往往是从其设计者是人这点出发的,他们认为机器是无法做出人命令之外的事,也就是机器是没有自由意志的。其实很多研究发现人同样没有自由意志,很多你认为自主做出的选择实际上是意识为了解释本能而给出的反馈,是个幻象,本质上人的多数行为都是生物应激而不是自主控制的。其实,就连意识本身从进化上看也就是个副产品,为了更好的生存而已。那么机器会不会也会产生意识呢?如果它们产生的意识不是进化通过生化反应造成的幻象又会是什么样呢?同样的回到图灵测试,如果我们实际无法判断是人还是机器,那么还有必要从历史上找回自己的物种认同感吗?图灵给我们留下的思考还是非常多的,而且很多问题在不久的将来可能就会具现化,那个时候就不是数学危机了,而是自我认知的危机。

密码

这本书有相当的篇幅讨论了图灵在布莱克利庄园破译德国密码的工作,我读到时其实挺想单独总结一篇的,但时间过去太久很多细节都记不清了。不过,电影《模仿游戏》里有很多是违反事实的戏剧化描写,谜机其实也有好几代,图灵是关键人物但也有其他人的重要贡献。从密码学上看,谜机的加密方式已经非常强悍了,甚至今天想要破解谜机都不是特别容易,不过现代密码学的根基已经换成了数论,但谜机的故事始终都很精彩,网上也有很多很技术的讨论,可以作为头脑体操来尝试阅读。

图灵之死

图灵的死非常神秘,官方给出的结论就是自杀,作者虽然也比较认可但也给出了大量的疑点,有些放到时代背景里去看还是有道理的。不过图灵的经历实在太过不同寻常,所以任何疑点都不能给出决定性证据。图灵的同性恋身份也在文中有很多描述,当时英国社会也将同性恋认为是精神疾病,不可否认他因为这个身份接受两年化学阉割会产生严重影响。而他战时的涉密工作与当时英国社会对间谍渗透的恐惧与美国冷战思维似乎也可能是死亡原因。甚至图灵的最后一次算命都可能是最后一根稻草。不论如何,图灵死的毫无征兆,但这种事有时可能就是没有任何原因。

这本书的细节与事实整理还是很好的,不过我感觉作者有点过于神化图灵了,例如图灵机实际跟邱奇的工作是实质等同的而很多描述带有明显的个人偏好与选择性描述。无论如何,图灵是伟大的,理解图灵机也是理解计算机科学作为独立学科的钥匙,更神秘的则是无处不在的鱼与熊掌不可兼得问题,我觉得图灵可能也思考过这个问题。