计算的本质 － 深入剖析程序和计算机, 关于计算理论
版权声明 @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 OReilly 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,ine.出版,2013。 简体中文版由人民邮电出版社出版,2014。英文原版的翻译得到 OReilly Media,nc.的 授权。此简体中文版的岀版和销售得到出版杈和销售权的所有者— O Reilly media,Inc 的许可。 版权所有,未得书面许可,本书的任何部分和全部内容不得以任何形式重制。 O Reilly Media,nc介绍 O'Reilly media通过图书、杂志、在线服务、调查研究和会议等方式传播创新知识。 自1978年开始,Oˆ Reilly一直都是前沿发展的见证者和推动者。超级极客们正在开创 着未来,而我们关注真正重要的技术趋势——通过放大那些“细微的信号”来刺激社 会对新科技的应用。作为技术社区中活跃的参与者, O'Reilly的发展充满了对创新的 倡导、创造和发扬光大 Oˆ Reilly为软件开发人员带来革命性的“动物书”;创建第一个商业网站(GNN);组 织了影响深远的开放源代码峰会,以至于开源软件运动以此命名;创立了Make杂志, 从而成为DⅠY革命的主要先锋;公司一如既往地通过多种形式缔结信息与人的纽带。 oˆ Reilly的会议和峰会集聚了众多超级极客和高瞻远瞩的商业领袖,共同描绘岀开创 新产业的革命性思想。作为技术人士获取信息的选择, O Reilly现在还将先锋专家的 知识传递给普通的计算机用户。无论是通过书籍出版,在线服务或者面授课程,每 项oˆ Reilly的产品都反映了公司不可动摇的理念——信息是激发创新的力量 业界评论 ¨ O'Reilly radar博客有口皆碑。” — Wired O'Reilly凭借一系列(真希望当初我也想到了)非凡想法建立了数百万美元的业务。” Business 2.0 Oˆ Reilly Conference是聚集关键思想领袖的绝对典范。” CRM “一本 O'Reilly的书就代表一个有用、有前途、需要学习的主题。” — Trish times ¨Tim是位特立独行的商人,他不光放眼于最长远、最广阔的视野并且切实地按照 Yogi Berra的建议去做了:‘如果你在路上遇到岔路口,走小路(岔路)。’回顾过去 Tim似乎每一次都选择了小路,而且有几次都是一闪即逝的机会,尽管大路也不错」 Linux journa 目录 封面介绍 前言 第1章刚好够用的Ruby基础 1.1交互式 Ruby shell 1.2值 1.2.1基本数据 1.22数据结构 12234 1.2.3proc… 1.3控制流…… 1.4对象和方法 1.5类和模块… 1.6其他特性 1.6.1局部变量和赋值…… 1.6.,2字符串插值… 1.6.3检查对象 77888 64打印字符串 1.6.5可变参数方法( variadic method)… 1.6.6代码块………… 1.6.7枚举类型… 10 16.8结构体… 1.6.9给内置对象扩展方法( Monkey Patching) 12 1.6.10定义常量…… 13 1.6.11删除常量 第一部分程序和机器 第2章程序的含义 ……17 2.1“含义”的含义……… 2.2语法… 2.3操作语义 19 2.3.1小步语义……… …20 23.2大步语义 24指称语义 46 24.1表达式………… …46 242语句 49 24.3应用 ……51 25形式化语义实践 25.1形式化 52 252找到含义 2.53备选方案 53 2.6实现语法解析器… 第3章最简单的计算机 3.1确定性有限自动机… 3.1.1状态、规则和输入 3.1.2输出 3.1.3确定性………… 3.1.4模拟 62 3.2非确定性有限自动机 65 3.2.1非确定性… 3.2.2自由移动( free move)… 3.3正则表达式 ,, …74 3.3.1语法 …75 3.3.2 义 ………78 333解析 86 34等价性… …88 目录 第4章增加计算能力 4.1确定性下推自动机… …100 4.1.1存储 100 4.1.2规则 …101 4.1.3确定性 103 4.1.4模拟 4.2非确定性下推自动机 …110 4.2.1模拟 113 42.2不等价 115 4.3使用下推自动机进行分析 116 43.1词法分析 116 43.2语法分析… l18 4.3.3实践性… 122 44有多少能力 …123 第5章终极机器 125 5.1确定型图灵机· 125 5.1.1存储 126 5.1.2规则 127 5.1.3确定性…… 131 5.1.4模拟 5.2非确定型图灵机 13 5.3最大能力 ……137 53.1内部存储 137 5.3.2子例程………… 140 53.3多纸带……… 5.3.4多维纸带………… 54通用机器……… …………………142 5.4.1编码… 5.4.2模拟 145 第二部分计算与可计算性 第6章从零开始编程… 149 6.1模拟 lambda演算…… 目录|W 61.1使用proc工作 150 6.1.2问题 …152 6.1.3数字 6.1.4布尔值 …156 6.1.5谓词 160 61.6有序对 16l 6.1.7数值运算 …161 61.8列表 168 61.9字符串 172 6.1.10解决方案 …………174 6.1.11高级编程技术 178 6.,2实现 lambda演算………………………………………………………………184 6.2.1语法 6.2.2语义 186 623语法分析 第7章通用性无处不在 …………………………193 7.1 lambda演算……………… ……193 72部分递归函数 7.3SKI组合子演算……… 201 7.4约塔(Iota)…………… ………………210 7.5标签系统 213 7.6循环标签系统…… 77 Conway的生命游戏 7.8rule110……………………………………………………………231 79 Wolfram的2,3图灵机… 234 第8章不可能的程序 235 8.1基本事实……………236 8.1.1能执行算法的通用系统 236 8.1.2能够替代图灵机的程序… 8.1.3代码即数据 8.1.4可以永远循环的通用系统 ……………………241 8.1.5能引用自身的程序 ………245 8.2可判定性 250 83停机问题……………… …………251 8.3.1构建停机检查器… ……251 目录 8.32永远不会有结果 254 84其他不可判定的问题 258 8.5令人沮丧的暗示… ·260 8.6发生上述情况的原因 …261 8.7处理不可计算性 262 第9章在“玩偶国”中编程 …265 9.1抽象解释…… 9.1.1路线规划… 266 91.2抽象:乘法的符号 …267 91.3安全和近似:增加符号 …270 92静态语义 ……274 9.2.1实现 275 92.2好处和限制 281 93应用… 后记 ……285 目录X 封面介绍 本书封面上的动物是砗蚝(拉丁学名为 Hippopus hippopus)。砗蚝因其形状又叫马蹄蛤, 又因其颜色泛红称为草莓蛤。砗蚝是砗磲科巨蛤亚科的一部分,而砗磲科又是乌蛤科的 部分。砗蚝主要生活在印度洋一太平洋区域的礁石中 砗蚝有两个相同而对称的铰合部。它还有着深深的嵴和与众不同的红白图案。砗蚝待在 个地方使用虹管过滤周围的水之后,以周围的浮游生物为食。