读书记录之《计算的本质》

之前读龙书,读到自动机的时候就完全渐渐就不知所云了。后来试着看看其他类似的书,比如虎书、鲸书,最后统统都放弃了。

最近看了《计算的本质》,感觉看着还不错,简单的解释了龙书里的部分概念,还有一部分SICP的内容。

这本书主体分两部分,第一部分主要是基础的语法语义分析和自动机、下推自动机和图灵机;第二部分是一些图灵等价的机器,比如labmda、SKI、IOTA之类演算,同时还有些机器极限和抽象的讨论。

从小步语义、大步语义开始,一直到语法分析,计算的本质到底是什么?

DFA(确定下有限自动机)通过确定的状态和规则来分析输入的字符,达到终态。确似乎无法解决类似非确定的路径和多种状态可能的分析,比如倒数第几个字符是A时达到终态。虽然我们最后实现了NFA(非确定性有限自动机),以为解决了DFA无法解决的问题,最后发现NFA和DFA是等价的。我们常见的正则表达式,就可以转换成状态机。

但是DFA或者NFA怎么检查成对出现的括号呢,通过在DFA上引入一个栈,我们得到一个下推自动机(DPDA),通过对得到的字符入栈和出栈来变更转台,解决成对的字符对称问题。但是一个栈或许并不能解决我们所有问题,比如偶数个字符的回文,因为在多次弹出栈的时候可能会丢失信息,非确定下推自动机(NPDA)可以解决这类问题,NPDA的实现是通过给每个路径一个栈实现的,灵活性更高。但是因为存在好多个栈,NPDA和DPDA并不等价。

但是我们有更高级、更通用的机器吗?一个图灵机(TM)就是我们期望的机器。图灵机把栈换成了穿孔纸带,可以一定规则读取或者写入纸带,可以实现我们期望中的机器实现。确定型图灵机(DTM)和非确定型图灵机(NTM)是等价的,为什么呢?因为图灵机是我们目前所知道的最强大的机器,DTM和NTM的极限是相同的。

上面说TM是目前知道的最强大的机器,因为她能解决我们所知的所有算法。我们所知道的很多实现:lambda演算(只有变量、函数、调用三个基本元素,可以实现图灵等价的机器)、部分递归(通过ZERO、INC和RECURSE、MINIMIZE来实现图灵机)、SKI(有三个算子S、K、I,其中I是可以用S和K实现的,通过SKI规则可以实现lambda演算)、IOTA(只有一个规约规则,可以实现SKI)、标签系统(通过反复删字符和写字符的规则,配合编码实现图灵机)、循环标签系统(标签系统的字符换为0和1)、细胞自动机、生命游戏等等都是图灵等价的。Church-Truing thesis认为任何算法都能被一台机器(特别是一台确定型图灵机)解决。

当然,图灵机无法解决停机问题和停机问题类似的普遍问题(如果上升到哲学范畴多少让人有所遐想,更或许会让人沮丧),但是我们可以通过一些抽象来给出一些近似的答案。

ps. 这本书的实现语言是ruby,尽量使用了最少的语法特性,比如proc。有一部分实现,比如lambda演算,因为使用了单个参数的函数,涉及到curring,但是也可以无视。

发表评论

电子邮件地址不会被公开。 必填项已用*标注