Understanding Computation - 计算的本质

图书信息

• 英文书名：Understanding Computation: From Simple Machines to Impossible Programs

• 中文书名：计算的本质 —— 深入剖析程序和计算机

• 作者：[英] Tom Stuart

• 译者：张伟

• 页数：正文 286 页 / 不含附录

• 英文出版社：O'Reilly Media

• 中文出版社：人民邮电出版社 / 图灵教育

• 出版日期：英文原版 2013 / 简体中文版 2014

• 个人分类：编译器 / 计算理论

• ISBN：978-7-115-36154-7

书评

写于2023年1月28日。

比较老的一本书，早就已经停印了，二手市场上贵的离谱，好在目前图灵社区官网上还是能直接买到mobi格式的电子书的，可以直接下载。电子书排版和纸质版一样好，阅读体验很不错。我一直很想给图灵的这一行为表示好评，很多其他出版社要是有哪一本书停印了，很多时候是连扫描版PDF都找不到的，而图灵一直可以直接在官网上买电子书，还不用它定制的在线阅读器，可以下到本地读，这我真的是很佩服。图灵在这方面压根就没考虑过防盗版，只要有一个人买了电子书按理来说就可以下载下来全网到处传，但图灵这样坚持了很多年，我真的很尊敬这家出版社。

中文书名副标题中的“深入”多少有点夸大的意思，英文书名倒是很恰当。这也是国内CS类图书标题翻译的经典毛病了，副标题总是译不出灵魂。整本书从内容来看是比较浅显甚至偏科普向的计算理论。

全书主要分两部分，使用Ruby介绍书中内容，主要偏实践而非理论，所以阅读难度不大。前半部分讲经典的图灵机模型，从程序语义的科普到有限自动机（FA）及其应用（正则），再到下推自动机（PDA），最后到图灵机的模拟，基本上是展示从简单机器（FA）一步一步到通用机器（图灵机）其计算能力的变化。

后半部分从λ演算开始，首先演示如何用λ演算实现和图灵机等价的能力，其中演示了在λ演算下如何模拟数字、列表、数值运算等，然后展示了数个与λ演算等价的系统，如SK组合子、标签系统、生命游戏等。在λ演算之后，探讨了程序可判定性与可计算性相关的话题，介绍了停机问题及与其等价的问题，然后简单展示了对程序执行静态分析的一些方案，如抽象解释和简单的类型系统。

整体上是非常棒的一本书。无论是对于对编译器领域一无所知，想满足好奇心的读者，还是对于有一定编译器基础知识，希望通过一些实际例子实践理论知识的读者，都是很合适的。我个人很推荐这本书，很多地方相当具有启发性，而且读着很轻松愉快。