《计算的本质》章节试读

《计算的本质》的笔记-第127页 - 存储

“纸带头”，译者指出原文是 tape head。
这里指的是 读写头，不是纸带的最初部分。
记下来我自己备忘，也提醒后来者，避免误读。

《计算的本质》的笔记-第193页 - 通用性无处不在

八卦一下
书中提到了几种与图灵机等价的模型， lambda算子、部分递归函数、SKI组合子、Iota、标签系统、循环标签系统、Conway生命游戏、rule 110、Wolfram的2,3图灵机。
部分递归函数，可能就是维基百科在递归函数词条中提到的“在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。”
Wolfram，就是著名的Mathematica的发明者之一。他的另一个成果是 Wolfram Alpha 计算型知识引擎。
数理逻辑学家、哲学家、人工智能先驱王浩（1921～1995），我记得也发表过一个图灵机等价模型，似乎是翻纸牌的，可能叫做Tile系统。可惜似乎由于有位法官同名，在维基百科上的王浩词条不能浏览，而百度百科语焉不详。
王浩研究自动定理证明，用早期的IBM计算机，几分钟就证明了罗素花十年心血才在其名著《数学原理》中证明的220条命题。王浩是历史学家何兆武先生的同学和好朋友，他俩都研究过 哥德尔-艾舍尔-巴赫 这本书。记得何兆武先生有张照片，背景正是书架，书名都被遮挡起来，除了这本很厚的 哥德尔-艾舍尔-巴赫。这本书讨论的内容就包括图灵机，也就是人的计算能力的限制。他们同样也都对罗素感兴趣，刚刚提到王浩证明了数学原理中的命题，何兆武先生则翻译了罗素的《西方史学史》上卷，对罗素的史学观也有专门论述。
王浩的工作，维基百科英文上查到了，从图灵机英文词条找过去，在[http://en.wikipedia.org/wiki/Wang_B-machine]提到：
Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23-25, 1954.

《计算的本质》的笔记-第138页

磁带，应作 纸带。

《计算的本质》的笔记-第163页

让ECREMENT工作的关键...由ZERO组成的有序对调用slide n次，然后使用SELECT从结果的有序对中拉出左边的数来。
slide操作像这样:
>> slide ([3,4])
=> [4,5]
>> slide ([8, 9])
=> [9, 10]
我不记得SICP如何实现减法了。
这一实现非常巧妙。

《计算的本质》的笔记-第138页 - 非确定型图灵机

一台机器不是只用一个状态表示“向右扫描查找一个空白方格”，而是可以为"向右扫描一个空白方格（记住我之前读取到了一个a）"设置一个状态，再为"向右扫描一个空白方格（记住我之前读取到了一个b）"设置另一个状态，所有可能的字符都以此类推－－字符数目 也是有限的，所以这样的复制总是有限的。
规则数量有限，非常重要。
如果无限，就只能递归或迭代，不能复制。
无限的情况，参见 Algorithmic Adventures [http://book.douban.com/subject/4473922/].

《计算的本质》的笔记-第141页 - 多纸带

一条图灵机的纸带通过交叉存取
交叉存取应为: 读写（存取）字符X
如果我们在每一个交叉字符的边上放上一个空白方格
应为: 每一个字符
－－－－
原文中的实例，希望实现 adgbehcfi，用一条纸带实现三条纸带（abc, def, ghi）的效果。
用字符X标识三个纸带中每个读写头的位置:
a_dXg_b_e_hXcXf_i_
三个X分别标识出ab(c) ，(d)ef，g(h)i三条纸带及读写头的位置（用括号表示）。

《计算的本质》的笔记-第134页 - 确定型图灵机 模拟

规则的语法
(当前状态，读入字符，下一状态，写入字符，读写头移动方向)
'_' 表示空白。

《计算的本质》的笔记-第122页 - 实践性

lookahead 翻译为 递推，似乎是误译。
一般译为 前瞻 或 超前，“LL(1)或者LR (0)这样的命令的时候，括号里的数字就是要超前的tokens的数量。”

《计算的本质》的笔记-第167页

匿名lambda函数实现递归。
Y组合子是一种 不动点组合子。
不动点组合子 见 [http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90]。
不动点，这个概念似乎最初来自牛顿法。

《计算的本质》的笔记-第144页

注5:二元基于2，一元基于1.
猜测“基于”是误译。
应作: 二元的基数是2，一元的基数是1.
原文中，把用三个不同的数字 1, 11, 111 编码a,b,c。
用特定字符1的个数不同来表示不同的被编码字符。
因为只使用1个字符，称为1元。类似于“一进制”。

《计算的本质》的笔记-第40页 - 大步语义

似乎 大步语义等价于SICP中的正则序，递归，先展开，后求值；
小步语义等价于 应用序，迭代，先求值，后展开。

《计算的本质》的笔记-第89页

这两个例子的唯一真正区别是, DFA的模拟是从一个当前状态移动到另一个, 而NFA的模拟是从当前可能状态的集合移动到另一个可能状态的集合.所以任何NFA都可以转化成等价的DFA, 只不过因为转化后的DFA的每个节点表示的是转化前NFA的节点的集合, 所以转化后DFA理论的最大节点数是2^n(n=转化前NFA的节点数)

《计算的本质》的笔记-第1页

《计算的本质》以Ruby程序为工具讲解了计算机、程序、程序语言等基本的计算机科学问题，是一本非常好的计算机科学实践书籍。使用Ruby语言模拟了各种机器的计算能力、计算机语言的语义，深入浅出的讨论了计算的本质。
书中详细探讨了各种类型机器的计算能力，机器按照计算能力分为有限自动机（FA），下推自动机（PDA），图灵机（TM），通用计算机；除图灵机与通用计算机等价外，计算能力逐渐增强。有限状态机增加外部存储的栈，扩大计算能力就是下推自动机；有限状态机增加无限长的纸带访问就是图灵机，图灵机的实质就是能够访问无限长纸带的有限状态机。
DFA可以识别正则式，NPDA可以识别回文字符串，确定性图灵机(DTM)可以进行二进制递增运算。每种机器都有相当明显的能力限制，FA无法解决涉及无限制的计数问题，例如判定一个括号组成的字符串是否平衡的问题；PDA无法处理任何信息需要在多处重用的问题，例如判定一个字符串是否含有同样数目的字符a,b和c；最先进的机器就是图灵机，拥有无限制的存储，这个存储可以以任何顺序，在任意循环中，在任意条件语句中以及子例程中访问。
计算规则又可以区分为确定性，非确定性，例如确定性有限自动机，非确定性图灵机等，确定性就是状态转换规则集中没有冲突的规则，没有遗漏的规则；非确定性就是放松确定性的限制，允许一个状态和输入包含多条规则或无规则。
对用通用的计算性，图灵机等价于lambda演算，等价于部分递归函数计算，等价于SKI演算，这些演算、计算及图灵机都具有通用计算机的能力，几者是完全等价的。尽管图灵机等的计算能力非常强大，但是其能力也是有极限的，比如停机问题，判定程序是否输出特定字符串等问题，都是不可判定问题。判定“程序是否做了我想让他做的事情”这是不可判定的，例如程序是否一定崩溃，是否调用了私有的API，是否执行了从网上下载的任意代码。这些判定程序自身性质的问题都是不可判定的。

《计算的本质》的笔记-第132页

注1.
原译文 纸带是纯功能性的。
猜测原意是 纸带是纯函数式的。参见函数式语言，无付作用的。

《计算的本质》的笔记-第245页 - 可以永远循环的通用系统

不停机程序是通用性的一个不可避免的结果只要在使用一种强大到能对自身求值的程序，我们就知道一定可能使用#evaluate的等价物构建永不停机的程序如果移除了一个特性让一个程序无法永远循环，一定也不可能实现#evaluate了
哥德尔不完备定理的通俗解释。