计算的本质：深入剖析程序和计算机 Understanding Computation From Simple Machines to Impossible Programs (Tom Stuart 张伟) (z-library.sk, 1lib.sk, z-lib.sk)

图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使 用，未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产 权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 ������

图 灵 程 序 设 计 丛 书 人 民 邮 电 出 版 社 北　　京 Understanding Computation From Simple Machines to Impossible Programs [英］Tom Stuart 著 张伟 译 Beijing • Cambridge • Farnham • Köln • Sebastopol • Tokyo O’Reilly Media, Inc.授权人民邮电出版社出版 计算的本质 深入剖析程序和计算机

内 容 提 要 本书借助简单的 Ruby 代码示例，全面、深入地介绍计算理论和编程语言设计。作者注重 实用性，在读者熟知的背景知识下，以明晰的可工作代码阐释了形式语义、自动机理论，以及 通过 lambda 演算进行函数式编程等计算问题，并为读者自行探索打下了良好基础。 本书面向熟悉某种现代编程语言却非科班出身的程序员，是一本帮你真正理解计算机科学 和计算原理的优秀参考书。 定价：69.00元 读者服务热线：(010)51095186转600　印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广字第 8052 号 著　　　　[英] Tom Stuart 译　　　　张　伟 责任编辑　李松峰　毛倩倩 执行编辑　程　芃 责任印制　焦志炜 人民邮电出版社出版发行　　北京市丰台区成寿寺路11号 邮编　100164　　电子邮件　315@ptpress.com.cn 网址　http://www.ptpress.com.cn 北京　　　　　　印刷 开本：800×1000　1/16 印张：18.75 字数：433千字 2014年 11 月第 1 版 印数：3 701 — 4 000册 2016年 6 月北京第 3 次印刷 著作权合同登记号 图字：01-2013-5148号 ◆ ◆ ◆ （2016.6重印）

III 版权声明 ©2013 by O’Reilly Media, Inc. Simplified Chinese Edition, jointly published by O’Reilly Media, Inc. and Posts & Telecom Press, 2014. Authorized translation of the English edition, 2014 O’Reilly Media, Inc., the owner of all rights to publish and sell the same. All rights reserved including the rights of reproduction in whole or in part in any form. 英 原版 O’Reilly Media, Inc. 出版，2013。 简 版 人民邮电出版社出版，2014。英 原版的 译 O’Reilly Media, Inc. 的 权。 简 版的出版和 出版权和 权的 者——O’Reilly Media, Inc. 的 可。 版权 ， 书面 可，本书的任 和全 以任 形式重制。

O’Reilly Media 通过图书、 志、在 、 和 等 式 知识。 自 1978 年开 ，O’Reilly 一 是 发 的 者和 动者。 正在开 ， 注真正重 的 ——通过 的 号 社 科 的 用。作为 社区 的参 者，O’Reilly 的发 了 的 、 和发 。 O’Reilly 为 件开发人员 性的 动 书 第一 网 GNN 了 深 的开 代码峰 ，以 开 件 动以 了 Make 志， 成为 DIY 的 一 地通过 种形式 人的 。 O’Reilly 的 和峰 了 和 的 ， 同 出开 的 性 。作为 人 的 ，O’Reilly 现在 的 知识 通的计算机用 。 论是通过书 出版，在 者面 程， 一 O’Reilly 的 了 可动 的理 —— 是 发 的 。 业界评论 “O’Reilly Radar 博客有口皆碑。” ——Wired “O’Reilly 凭借一系列（真希望当初我也想到了）非凡想法建立了数百万美元的业务。” ——Business 2.0 “O’Reilly Conference 是聚集关键思想领袖的绝对典范。” ——CRN “一本 O’Reilly 的书就代表一个有用、有前途、需要学习的主题。” ——Irish Times “Tim 是位特立独行的商人，他不光放眼于最长远、最广阔的视野并且切实地按照 Yogi Berra 的建议去做了：‘如果你在路上遇到岔路口，走小路（岔路）。’回顾过去 Tim 似乎每一次都选择了小路，而且有几次都是一闪即逝的机会，尽管大路也不错。” ——Linux Journal O’Reilly Media, Inc.介绍

V 目录 封面介绍 .................................................................................................................................................X 前言 .........................................................................................................................................................XI 第 1 章　刚好够用的 Ruby 基础 ......................................................................................................1 1.1　 式 Ruby Shell ......................................................................................................................1 1.2　 .................................................................................................................................................2 1.2.1　基本数据 ........................................................................................................................2 1.2.2　数据结构 ........................................................................................................................3 1.2.3　proc .................................................................................................................................4 1.3　 制 .........................................................................................................................................4 1.4　 和 .................................................................................................................................5 1.5　 和 .....................................................................................................................................6 1.6　 性 .....................................................................................................................................7 1.6.1　局部变量和赋值 ............................................................................................................7 1.6.2　字符串插值 ....................................................................................................................8 1.6.3　检查对象 ........................................................................................................................8 1.6.4　打印字符串 ....................................................................................................................8 1.6.5　可变参数方法（variadic method） .................................................................................9 1.6.6　代码块 ............................................................................................................................9 1.6.7　枚举类型 ......................................................................................................................10 1.6.8　结构体 ..........................................................................................................................11 1.6.9　给内置对象扩展方法（Monkey Patching） ................................................................12

VI ｜ 目录 1.6.10　定义常量 ....................................................................................................................13 1.6.11　删除常量 .....................................................................................................................13 第一部分　程序和机器 第 2 章　程序的含义 .........................................................................................................................17 2.1　 义 的 义 .........................................................................................................................18 2.2　语 ...........................................................................................................................................19 2.3　 作语义 ...................................................................................................................................19 2.3.1　小步语义 ......................................................................................................................20 2.3.2　大步语义 ......................................................................................................................40 2.4　 语义 ...................................................................................................................................46 2.4.1　表达式 ..........................................................................................................................46 2.4.2　语句 ..............................................................................................................................49 2.4.3　应用 ..............................................................................................................................51 2.5　形式 语义实 .......................................................................................................................52 2.5.1　形式化 ..........................................................................................................................52 2.5.2　找到含义 ......................................................................................................................53 2.5.3　备选方案 ......................................................................................................................53 2.6　实现语 解 .......................................................................................................................54 第 3 章　最简单的计算机 ................................................................................................................59 3.1　 定性 自动机 ...................................................................................................................59 3.1.1　状态、规则和输入 ......................................................................................................60 3.1.2　输出 ..............................................................................................................................60 3.1.3　确定性 ..........................................................................................................................61 3.1.4　模拟 ..............................................................................................................................62 3.2　非 定性 自动机 ...............................................................................................................65 3.2.1　非确定性 ......................................................................................................................65 3.2.2　自由移动（free move） ................................................................................................71 3.3　正 式 ...............................................................................................................................74 3.3.1　语法 ..............................................................................................................................75 3.3.2　语义 ..............................................................................................................................78 3.3.3　解析 ..............................................................................................................................86 3.4　等价性 .......................................................................................................................................88

目录 ｜ VII 第 4 章　增加计算能力 .....................................................................................................................97 4.1　 定性下 自动机 .................................................................................................................100 4.1.1　存储 ............................................................................................................................100 4.1.2　规则 ............................................................................................................................101 4.1.3　确定性 ........................................................................................................................103 4.1.4　模拟 ............................................................................................................................103 4.2　非 定性下 自动机 .............................................................................................................110 4.2.1　模拟 ............................................................................................................................113 4.2.2　不等价 ........................................................................................................................115 4.3　 用下 自动机进行 .....................................................................................................116 4.3.1　词法分析 ....................................................................................................................116 4.3.2　语法分析 ....................................................................................................................118 4.3.3　实践性 ........................................................................................................................122 4.4　 .............................................................................................................................123 第 5 章　终极机器 ............................................................................................................................125 5.1　 定 图 机 .........................................................................................................................125 5.1.1　存储 ............................................................................................................................126 5.1.2　规则 ............................................................................................................................127 5.1.3　确定性 ........................................................................................................................131 5.1.4　模拟 ............................................................................................................................131 5.2　非 定 图 机 .....................................................................................................................136 5.3　 .................................................................................................................................137 5.3.1　内部存储 ....................................................................................................................137 5.3.2　子例程 ........................................................................................................................140 5.3.3　多纸带 ........................................................................................................................141 5.3.4　多维纸带 ....................................................................................................................142 5.4　通用机 .................................................................................................................................142 5.4.1　编码 ............................................................................................................................144 5.4.2　模拟 ............................................................................................................................145 第二部分　计算与可计算性 第 6 章　从零开始编程 ...................................................................................................................149 6.1　 lambda 演算 ...................................................................................................................150

VIII ｜ 目录 6.1.1　使用 proc 工作 ...........................................................................................................150 6.1.2　问题 ............................................................................................................................152 6.1.3　数字 ............................................................................................................................153 6.1.4　布尔值 ........................................................................................................................156 6.1.5　谓词 ............................................................................................................................160 6.1.6　有序对 ........................................................................................................................161 6.1.7　数值运算 ....................................................................................................................161 6.1.8　列表 ............................................................................................................................168 6.1.9　字符串 ........................................................................................................................172 6.1.10　解决方案 ..................................................................................................................174 6.1.11　高级编程技术 ...........................................................................................................178 6.2　实现 lambda 演算 ...................................................................................................................184 6.2.1　语法 ............................................................................................................................184 6.2.2　语义 ............................................................................................................................186 6.2.3　语法分析 ....................................................................................................................191 第 7 章　通用性无处不在 ..............................................................................................................193 7.1　lambda 演算 ............................................................................................................................193 7.2　 函数 .........................................................................................................................196 7.3　SKI 合子演算 .....................................................................................................................201 7.4　 Iota .............................................................................................................................210 7.5　 .................................................................................................................................213 7.6　 .........................................................................................................................220 7.7　Conway 的 ...............................................................................................................229 7.8　rule 110 ....................................................................................................................................231 7.9　Wolfram 的 2,3 图 机 ..........................................................................................................234 第 8 章　不可能的程序 ...................................................................................................................235 8.1　基本 实 .................................................................................................................................236 8.1.1　能执行算法的通用系统 ............................................................................................236 8.1.2　能够替代图灵机的程序 ............................................................................................239 8.1.3　代码即数据 ................................................................................................................239 8.1.4　可以永远循环的通用系统 ........................................................................................241 8.1.5　能引用自身的程序 ....................................................................................................245 8.2　可 定性 .................................................................................................................................250 8.3　 机问题 .................................................................................................................................251 8.3.1　构建停机检查器 ........................................................................................................251

目录 ｜ IX 8.3.2　永远不会有结果 ........................................................................................................254 8.4　 可 定的问题 .............................................................................................................258 8.5　 人 的 示 .....................................................................................................................260 8.6　发 的原 .............................................................................................................261 8.7　 理 可计算性 .....................................................................................................................262 第 9 章　在“玩偶国”中编程......................................................................................................265 9.1　 解释 .................................................................................................................................266 9.1.1　路线规划 ....................................................................................................................266 9.1.2　抽象：乘法的符号 ....................................................................................................267 9.1.3　安全和近似：增加符号 ............................................................................................270 9.2　 语义 .................................................................................................................................274 9.2.1　实现 ............................................................................................................................275 9.2.2　好处和限制 ................................................................................................................281 9.3　 用 .........................................................................................................................................284 后记 .......................................................................................................................................................285

X 封面介绍 本书 面 的动 是 学 为 Hippopus hippopus 。 形 ， 为 。 是 科 科的一 ， 科 是 科的 一 。 在印 区 的 。 同 的 合 。 深深的 和 同的 图 。 在 一 地 用 过 的 ，以 的 为 。

XI 前言 读者对象 本书 编程语言和计算理论 好 的程序员， 是 正 学 过数学 者 计算机科学的 。 你 及程序、语言以及机 ， 开 的计算机科学知识 ，却 用 阐明 的数学语言打 的 ， 本书 是你 的。 开 的数学 号， 用可工作的代码 理论性 ，并为 自行探索 。 本书读者 了解一种现代编程语言， Ruby、Python、JavaScript、Java 者 C#。书 示例程序 用 Ruby 语言编 成， 了解 语言的读者 。注 ，本 书 并 是 示 Ruby 面向 设计的 实 。本书代码 在简明 晰， 并 一 定 ， 为 的 是 用 Ruby 阐明计算机科学， 是用计算机科学 解 Ruby。本书 非 者 科全书， 以并 出形式论 者 的 明， 图 你 一 的 ， 发你 深入地了解 。 排版约定 本书 用以下 版 定。 • 用 记 。 • 等 字 constant width 用 程序代码，在 用 示程序的 成 ， 函数 、数 、数 、 、语 、 字。

XII ｜ 前言 • 等 constant width bold 是 用 入的 。 • 等 constant width italic 用 下 定的 。 示、 一 注解 在 。 示 在 。 使用代码 本书 在帮助读者解 实 问题。 你 在自 的程序 用 本书 的代码， 非 地 用， 权。 ，用本书 的 代码 程序 用向 可， 是 者 发 O’Reilly 图书 的代码 权 用书 的代码 问题 权， 的示例代码 合 自 的 过 可。 用 的代码 ， 你 明 的出 。出 一 书 、作者、出版 和书 号，例 ： Understanding Computation by Tom Stuart (O’Reilly). Copyright 2013 Tom Stuart, 978-1-4493-2927-3 。 用代码的 形 通，可以 ：permissions@oreilly.com。 Safari® Books Online Safari Books Online www.safaribooksonline.com 是 的数字图书 。 同 以图书和 的形式出版 和 作 的 作 。 Safari Books Online 是 、 件开发人员、Web 设计 、 人 和 人 开 、解 问题、学 和 的第一 。 、 机 和 人，Safari Books Online 种 合和 的定 价 。用 可通过一 的数 索 问 O’Reilly Media、Prentice Hall Professional、Addison-Wesley Professional、Microsoft Press、Sams、Que、Peachpit Press、Focal Press、Cisco Press、John Wiley & Sons、Syngress、Morgan Kaufmann、IBM

前言 ｜ XIII Redbooks、Packt、Adobe Press、FT Press、Apress、Manning、New Riders、McGraw-Hill、 Jones & Bartlett、Course Technology 以及 出版社的 千种图书、 和正 式出版 的书 。 了解 Safari Books Online 的 ， 网 。 联系我们 本书的 价和问题发 出版社。 ： O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 ： 北京市 区 2 号成 C 807 100035 北京 O’Reilly 的 一本书 网 ，你可以在 本书的 ， 、示 例代码以及 。本书的网 地址是： http://oreil.ly/Understanding_Computation 本书的 论和 性问题， 发 电子邮件 ： bookquestions@oreilly.com 了解 O’Reilly 图书、 程、 和 的 ， 问以下网 ： http://www.oreilly.com 在 Facebook 的地址 下：http://facebook.com/oreilly 注 的 Twitter 动 ： http://twitter.com/oreillymedia 的 YouTube 地址 下： http://www.youtube.com/oreillymedia 致谢 非 Go Free Range 的 ， 在本书 作 为 了 地 、 好的 以及 。 的 ， 定 了。 James Adam、Paul Battley、James Coglan、Peter Fletcher、Chris Lowis 和 Murray Steele 的 ，并 Gabriel Kerneis 和 Alex Stangl 的 。 了 的 ， 本书的 为 。 学的 Alan Mycroft 和 示 。

XIV ｜ 前言 O’Reilly 的 人帮助 了本书的 工 出版， Mike Loukides 和 Simon St.Laurent 一开 和 ， Nathan Jepson 成实 图书的 ，以及 Sanders Kleinfeld 的语 一 的 。 的 一 人的 、 动机， 机 在计算机 子。 Leila， 次 记工作 成 ， 地 的 一 一 地 。 了。

1 第 1 章 刚好够用的Ruby基础 本书 的代码全 用 Ruby 成。Ruby 是一种简单、 好 的编程语言。 为 Ruby 晰 ， 了 ， 本书并 Ruby 的 性， 以 示例代码 可 成你 的 任 语言， 是 Python 者 JavaScript 的动 语言， 你 理解的 。 的示例代码 Ruby 2.0 和 Ruby 1.9。你可以在 Ruby http://www.ruby- lang.org/ 了解 Ruby， 可以下 一 的实现。 一下 Ruby 的 性，并 介绍本书 用 的 。 你 学 ， O’Reilly 的 Ruby 编程语言 The Ruby Programming Language 一书 。 了解 Ruby，你 全可以 第 2 开 读本书。 1.1　交互式Ruby Shell Ruby 好的一 性 是 式 制台 IRB， 可以 在 入 Ruby 代码 执行 。本书 用 IRB 的代码进行 ，并探索 代码是 工 作的。 在开发机 的 行 入 irb， 可以 行 IRB 了。IRB 示 示 >> ， 明 可 以 入一 Ruby 式。 入一 式并 ，代码执行， 示 示 => ：

2 ｜ 第 1 章 $ irb --simple-prompt >> 1 + 2 => 3 >> 'hello world'.length => 11 本书 出现 示 >> 和 =>， 是在 IRB 。为了 代码 读，本书 示 的 示 ， 是 定 代码 入 者 进了 IRB。 以一 本 书 下面 的 Ruby 代码： x = 2 y = 3 z = x + y 可以在 IRB 的 ： >> x * y * z => 30 1.2　值 Ruby 是一种面向表达式的语言： 一 的代码执行 一 。下面 一下 Ruby 同 的 。 1.2.1　基本数据 ，Ruby Boolean 、数 number 和字 string ， 算： >> (true && false) || true => true >> (3 + 3) * (14 / 2) => 42 >> 'hello' + ' world' => "hello world" >> 'hello world'.slice(6) => "w" 一 Ruby 符号 示一 字，是一 、 可 的 。作为字 的简单 、非 less memory-intensive 的 身， 号在 Ruby 用——通 是作为 的 用 参 1.2.2 。 号字面 的开 一 号： >> :my_symbol => :my_symbol >> :my_symbol == :my_symbol => true >> :my_symbol == :another_symbol => false

刚好够用的Ruby基础 ｜ 3 nil 用 示 在任 用的 ： >> 'hello world'.slice(11) => nil 1.2.2　数据结构 Ruby 的数 字面 是一 用 号 的 号的形式： >> numbers = ['zero', 'one', 'two'] => ["zero", "one", "two"] >> numbers[1] => "one" >> numbers.push('three', 'four') => ["zero", "one", "two", "three", "four"] >> numbers => ["zero", "one", "two", "three", "four"] >> numbers.drop(2) => ["two", "three", "four"] 范围 range 示 和 的 合。 的 是在 ： >> ages = 18..30 => 18..30 >> ages.entries => [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] >> ages.include?(25) => true >> ages.include?(33) => false 一 散列 hash 示一 合， 一 一 编程语言 种数 作 map 、 字 dictionary 者 数 associative array 。 一 字面 成 号 用 号 的 => 的 ： >> fruit = { 'a' => 'apple', 'b' => 'banana', 'c' => 'coconut' } => {"a"=>"apple", "b"=>"banana", "c"=>"coconut"} >> fruit['b'] => "banana" >> fruit['d'] = 'date' => "date" >> fruit => {"a"=>"apple", "b"=>"banana", "c"=>"coconut", "d"=>"date"} 号用作 ， 以 作为 号 ，Ruby 了 一种书 的语 。 种 => 的 式 为 ， 用 JavaScript 的 JSON 式 ： >> dimensions = { width: 1000, height: 2250, depth: 250 } => {:width=>1000, :height=>2250, :depth=>250} >> dimensions[:depth] => 250