2012年11月28日星期三 购书前奏曲和序言
今年11月11日，我的室友星星欠我30元钱，我让他送我光棍节礼物，不用还我钱了。他问我要啥，那段时间看乔布斯传看得很high，于是觉得北大学子一定知道很多好书，让他送我本书，推荐下，他说GEB不错。我当时愣了下，这应该是数理逻辑要看的一本书。我想了想让他给我买了浪潮之巅。但是还是去搜索了GEB这本书。当当网上的评价是，“这是一本空前的奇书，也是一本杰出的科学普及名著，它以精心设计的巧妙笔法深入浅出地介绍了数理逻辑、可计算理论、人工智能等学科领域中的许多艰深理论，轻松、幽默、流畅的文字隐藏着大量的潜台词，它们前后照应、互相联系，交织成一个复杂、无形的网络，读者看不见它，但可以嗅出它的气味，并觉察到这是作者有意喷洒的。”
11月22日，从“当当网”够得这本书。
11月28日，开始读这本书。[美]侯世达 著。作者是华裔？怀着这种怀疑开始阅读。从乔布斯传开始，读每本书开始从序言开始。GEB序言38页。
从序言中了解到，此书的中文版成书得益于北大的吴允曾和马希文教授。我发现侯世达，并非华裔，而是道格拉斯·理查·郝夫斯台特 Douglas R. Hofstadter。此人很厉害，不仅在数学和计算机的造诣上，我个人认为在他促成多国语言的GEB的过程中，他绝对是一个语言学家。侯世达是他给自己取的中文名字，他还给本书的中文版作了序。
对于本书的中文版，绝对不是简单的英译中，我个人认为基于作者的语言造诣，加上北大和商务印书馆的支持，本书绝对算一部中文的巨作，做到了严复所谓的三个基本标准：信，达，雅。关于科学的文章我也很赞赏他们的关于科学性论文移译的观点。
比如：“a man, a plan, a canal : Panama”难道要翻译为“一位工程师设计了巴拿马运河”？但是作为计算机的学生，我惊奇的发现，这句英文是回文！所以为何不可对应中文的“叶落天落叶”。
关于GEB：Gödel, Escher, Bach: an Eternal Golden Braid
中文对应：
哥德尔、埃舍尔、巴赫：集异璧之大成
可以看到作者的英文前缀 和 英文对应。中文名和中文拼音对应。
对了，还有一个很艺术的地方：
这两个小方块的三维投影正好是GEB和EGB（本书的后半部分）。
北大的翻译工作组更加用心：中文的集异璧和英文的GEB全部在里面了。
2012年12月06日星期四 导言 一首音乐——逻辑的奉献
最近太忙了，之前把《乔布斯传》和《浪潮之巅》看完了，想集中精力看GEB，结果一方面太忙，另一方面我发现除了计算机有点基础之外，我别的领域特别是音乐确实是个笨蛋。比起前两本书，GEB的不同之处在于你还需要动脑子去理解，这里面充满了逻辑的论证，稍不留神就出现的悖论，信手拈来的计算机中的回文、离散数学中的同构、物理学中的静止与运动。
今天终于把需要看完了。序言或者导言围绕着巴赫的音乐的奉献展开的，取得名字也很有意思叫逻辑的奉献，然后再分别谈了谈巴赫、艾舍尔和哥德尔这三位集大成者。
卡农和赋格：
作为一个音乐白痴，之前只听说过卡农，赋格连听都没听说过。不过大概尝试去理解他们的意思，你会发现巴赫确实是一个天才，从对仗美的角度，虽然我没有听过他的曲子。看他的曲子的结构也能想到，哇，那一定很美。
卡农的基本点是一个单一的主题与它自己相伴而奏。由加入的各个不同声部分别长处主题的“副本”。最简单的方式是轮唱。更复杂的卡农是由简入繁，不仅在时间上而且在因搞上相互交错，第一声部可能在C调上唱出主题，同第一声部相交错第二声部可能在比C调高五度的G调上唱出同一主题。第三部可能在比G调高五度的D调上唱出，这又有点等差数列的味道。看这个结构我就觉得很好听。卡能还有一种更复杂的阶段叫主题转位，意思是产生这样一个旋律，每当原来的主题跳上时，它就跳下，两者所越过的半音阶数相同。接下来是最玄妙的地方了——逆行。主题按照一定的时间从后往前奏出，即螃蟹卡农。无论哪一种副本都保留了原主题的信息，从任何一个副本可以恢复主题，这种保存信息的转换即同构。
正好周四的时候，老师问我什么是图同构，我说可以“印”过去！那什么是子图同构呢？
赋格有点类似于卡农，但没那么严格。
为了过渡到伟大的画家艾舍尔，我还必须提一下无穷升高的卡农。该卡农以C调开头，但是当即将结束时调子已经是D小调了，高了五度，而这个小变化让听者难以察觉。在所谓的“结尾”处，巴赫又把它巧妙地转回了开头，以此循环，无穷无尽。
“觅之，自有所获”。
如果说巴赫演奏出了这个无穷升高的怪圈，那么艾舍尔就画出了他！下图是瀑布，六个分立阶段即展示出了怪圈。
而上升与下降这幅画用了四个阶段就展示了怪圈，虽然比较松散。
2012年12月07日星期四 导言 一首音乐——逻辑的奉献
下面来讲讲最伟大的数学家哥德尔。巴赫和艾舍尔的怪圈中存在着有穷和无穷的冲突，有一种强烈的悖论感，这里面是不是数学出了问题？
有一个悖论叫艾皮曼尼蒂斯悖论：艾皮曼尼蒂斯是一个克里特岛人，他说“所有克里特岛人都说谎”。
这句话可以理解为：“本句话是假的”。
你假设它为真，它却自己得出了自己是假。假设它为假，它却得出了自己是真。
哥德尔在1931年发表了哥德尔定理，简而言之，就是无论涉及什么样的公理系统可证性总比公理性要弱。
一切或许都可以认为是来自“自指”的怪圈。或者是一个环，比如下面这个例子，有这么两句话：
下面这个句子是假的。
上面这个句子是真的。
罗素和怀海特致力于消除这样的怪圈，《数学原理》就是一套比较奇怪的自下而上的看似能消除怪圈的公理系统。
希尔伯特方案：
希尔伯特希望有人能证明《数学原理》既是一致性的又是完全的。即自身无矛盾但是又能证明出里面所有的定理。这里面多少有点循环论证的味道，有点像强迫一个人，拉着自己的鞋带把自己举起来。
但是很遗憾，哥德尔证明了“没有一个公理系统可以产生所有的数论真理，除非它是一个不一致的系统”。
下面来谈谈什么是智能。
- 对于情境有很灵活的反应。
- 充分利用机遇。
- 弄懂含糊不清或彼此矛盾的信息。
- 认识到一个情境中什么是重要的因素，什么是次要的。
- 在存在差异的清净之间能发现它们的相似处。
- 从那些由相似之处联系在一起的事物中找出差别。
- 用旧的概念综合处新的概念，把它们用新的方法组合起来。
- 提出全新的观念。
2012年12月08日星期五 三部创意曲 WU谜题
下面来谈谈历史上最著名的芝诺悖论，运动无有。
跑得飞快的阿基里斯要追一只乌龟。前提是他让乌龟10米远。每次阿基里斯跑了距离的二分之一时，乌龟会向前移动一段距离。所以阿基里斯一直在缩小距离，但是永远也追不上乌龟。
这个悖论更一般的理解是：一个人从A走到B点，他每次走剩下距离的十分之一，所以他永远也走不到B点。
这个悖论的关键问题是时间。假设距离长为10米，而速度为10米每秒。实际上之所以走不到是因为每次用的时间是0.1，0.01，0.001……秒。合起来只有0.11111111111……秒，根本不到1秒，当然走不到。
后来再去查了查芝诺悖论，除了阿基里斯追乌龟之外，还有一个例子是飞矢不动，此处不详细描述，但是我觉得物理学上有句话叫静止时相对的，运动时绝对的，可以解释这个悖论。
本书的一个特点是每到一个新的章节作者都会借用阿基里斯和乌龟来聊聊天作为抛砖引玉。
第一章讲的内容是WU谜题，由于有离散数学和数理逻辑的基础理解起来不是很复杂。但是里面的确有很多巧妙和让人回味的地方。
一个初始串WJ，要构造或者推导出一个目标串WU。
一些规则：
- 如果一个归你所有的符号串结尾时J，则可以在其后面再加上一个U。
- 如果你有Wx，那么Wxx也是你的。
- 如果JJJ出现在你的储备中的一个符号串里，那么你可以用U代替JJJ而得到一个新的串。
- 如果UU出现在你的串中，你可以去掉它。
要构造WU人和机器是区别的，机器不会累但是也不会思考，所以他会一直按照你的规则找下去，而人不一样，会通过一些洞察力去寻找这个串，或者抱怨找不到。
或者更直观的讲，人有一种能力可以跳出来！跳出系统，去看别的，机器可不行。
判定过程：我们定义判定过程，就是在有限的时间内，指出一个串到底是不是一个定理。一般地讲，我们可以推出一个串是不是一个定理，但是它可能需要花上无穷的时间。
假设有一个怪物，它就是有足够的时间，如果他来解这个WU谜题，他可能会：
- 对于公理WJ应用每一条可以应用的规则，这产生出两个新的定理：WJU，WJJJ。
- 对于1产生的定理应用所有可以应用的规则，产生出新的定理：WJJU，WJUJU和WJJJJ。
- 对于2中的定理同样应用规则，并产生出新的定理。
- ……
乌龟说给阿基里斯的话。
这次的对话看似荒谬，但是却给我一种启迪或者叫震撼！什么叫做证明！推理！推论！我也见识到了假言命题的威力。
下面来看一个论证的小片段：
- 同等于一物的彼此亦相等
- 这个三角形的两条边同等于一物
- 这个三角形的两条边彼此相等
欧几里德的读者都会认为Z是合乎逻辑的推论，所以任何人只要认为A和B为真，则必定Z为真。
但是提出以下两种疑问：
1.有人不认为A、B为真。同意“如果A、B为真，则Z为真”
2.有人同意A、B为真。不认为“如果A、B为真，则Z为真”
1的情况我们可以理解，暂时不考虑。
下面讨论2的情况，请问如何试图让持2观点的人同意ABZ的这个论证呢。
下面尝试这种证法：
不妨把假言命题：“如果A、B为真，则Z为真”定义为命题C
以下证明是否可行呢？
ABCZ
OK! 那么出现质疑假言命题“若ABC为真则Z为真”的人呢？
难道要再次定义假言命题D? 循环往复？这儿是否让人想到巴赫的无穷升调呢！
多么有趣的一个抛砖引玉的例子~
先定义一个简单的系统：pq系统：
**三种符号：**p q –
**公理的定义：**只要x仅由一串短杠组成，那么x-qxp-就是一条公理
**规则：**假设x、y、z都代表只包含短杠的特定的符号产，并假设xqypz是一条已知的公理的话，那么x-qypz-是一条定理。
那么给定一个串如何判定他是否是一条定理？
1.自底向上该方法类似于前面的WU谜题此处不再说明。
2.自顶向下：按照规则不停地寻找它的前驱串，并确认该串是否是一条公理。（当然我们有显然的方法判定一个串是否是一个公理，不然侯世达说：一切都没有希望了。）
经过仔细研究pg系统，可以发现一个经过洞察力可以发现的规律，就是若为定理那么一定是xqypz，且|x|=|y|+|z|
实际上，这是之前笔记中提到的一种东西叫同构：两个复杂的结构可以相互映射，并且每一个结构的每一部分在另一个结构中都有一个相应的部分。我们将一些列单纯的符号，赋予了现实生活的意义：加法。
可以看到这是我们的一厢情愿，当然你可以说q对应马，p对应幸福，-对应苹果。但是得出来的定理都是奇奇怪怪的目前现实生活毫无意义的关于马幸福和苹果的解释。当然我们的系统是实现定义好的，不能因为可以对应为加法，我们就异想天开地觉得x-q-x-p-x-是一个定理，因为6=2+2+2。这在现实生活中正确，但是在我们的pq系统是显然说不通的。
当然这种同构也不是唯一的，比如你可以把q对应为减法，p对应为等号这也说得通。以上一些简单但是在我看来比较妙趣横生的例子让我们感到了形式系统与现实的差别。
最后来讲讲给我最震撼的一个小例子：
12乘以12等于多少？144？对！如果我们对它怀疑可以去数一下12乘以12的矩阵格子有多少个。
那么123456789乘以987654321呢？我们不能去数数了吧。谁有能说这个值就是现在这个值呢？怎么证明呢？
下面介绍一个叫欧几里德定理的定理：针对有无穷多个素数这个命题，没有一个计数过程能够证明它的真假。不管我们数出了多少的素数，我们都无法确定素数的个数是有穷的还是无穷的。
欧几里德给出了一个神一样的证明，至少我觉得在当时甚是当时之后的相当长一段时间，大家都这样想。
挑出一个数N，可求得N!，得到一个新的数N!+1，这个数不能被2,3,4,5,6,7,8,9……N的任何数整除。
这种情况下只有两种结果N!+1要么是一个素数，要么它的素因数比N大，任何一种情况下，我们都找到了一个比N更大的素数。
所以当我们想绕过无穷这个概念来证明问题的时候可以使用类似于“所有”这种本身有穷的但是体现了无穷概念的词。
先来看看一幅艾舍尔的镶嵌