((报告 书) = (书 (报告 书)) ——《Gödel, Escher, Bach——集异璧之大成》读书报告

坯朴
本文最初作为作业撰写,因此语言习惯异于本博客通例。

最初接触《哥德尔、艾舍尔、巴赫——集异璧之大成》(以下简称《集》)是在我高一因故赋闲之时。彼时我对计算机的理解,至多不过能用 C 语言输出菱形;加之在高中时期,即便不在校园也偏离不了主航道太远,遑论打开这部装帧古旧的厚书「冒充」学习。因此,《集》一向被我束之高阁,时至今日才真正与之共鸣。

缘起——编码,编码

人之上是仙,明、霄、汉、垒、层、高、上、天,人之下是地、下、低、减、落、逝、泉、暗、鬼……1
——金庸《射雕英雄传》

我们这一代数字原住民,对计算机的认识一定程度上是先验的——借用计算理论术语 ,像是「神谕机」。被我们或多或少忽略的是,计算机与杠杆锲子别无二致,只是更为晚近而已2。在纳粹德国的密码尚未在烽火狼烟间蔓延之时,康托尔集合论与哥德尔不完备性已经展现出山雨欲来风满楼之势:无论是前者用「算两次」思想处理数表,抑或后者将形式系统写作数字,无不揭橥了可编程机器的雏形。这便是冯ㆍ诺伊曼体系的核心——程序即数据。

我们将视线继续拉回。当 14 世纪翡冷翠流水淙淙的亭台楼榭,在某个角度上看顶端与底端重合,如同螣蛇食尾;当宏伟殿堂中赞颂神灵的音响此起彼伏,相同声部从低音渐入至高音渐出,宛如呼朋引伴的野蜂划着圈圈;这些则体现了计算机或人工智能体系的又一核心——自指和同构。《集》之所以看似离题而谈到音乐或美术上的这种圆合,正是说明计算机起源的墙内开花墙外香。

生命是自指的,毫无疑问——例如我可以讲「我爱兰州大学」。但用「我」这区区一个汉字,指代一个数以万亿计细胞组成的庞然大物,不免轻率了些,何况阿隆佐ㆍ丘奇的 λ 演算和本书中先后提及的多种形式系统都将运算严格限制在文本替换(如 C 语言的宏一般刻板)的范围内,在「我」定义完全之前是不能用这个「我」字的。这可能是为避免一种对罗素悖论的常见诤讼,即把说谎者拒之集合定义的门外。这种条件下的自指不必多言,会是远远复杂于 Y 组合子的一种文字游戏,这给《集》以一种较之科普著作更像相声贯口的奇妙质感。

畸变——井龙王法力衰微

……人类也无法知晓他为何来自一无所有……
——帕斯卡

「我爱兰州大学」还蕴藏着另一个把戏:「我」究竟指谁?振动从声带产生,经过调制承载音素(例如,对现代标准汉语是 Wǒ ài Lánzhōu Dàxué),并以空气为介质传播。如果一名对地球生物双耳茫然的外星人能够正确理解这句话,它可能为划分这句话的发出者而犯难:或许认为我的肝脏是一个生命体,这句话仅仅来自我的肝脏,其他器官均属于外界,与这句话的形成无关;或许认为我身处的建筑才是一个生命体,这句话只有该建筑才能完整形成3

公理化系统时常面临相同的窘境。日常生活是复杂的,许多情况是在多个层次的公理化系统同时发生。治计算机科学的我们较为熟悉的开放式通信系统(OSI)参考模型即是一例,这里的「层次」不严格等于公理化系统的「层次」但无伤大雅——甚至在物理层之底,我们还来不及讨论电子的运动和量子态纠缠呢!

Haskell 语言的用户对此再熟悉不过。写一个类型声明为 Int -> [Int](整数映射到含整数的数组)的函数无伤大雅,但若类型声明是 a -> [a],解释器会指摘不允许定义无限类型,因为 a 取值不限,有 [a] 就有 [[a]],有 [[a]] 就有 [[[a]]],无穷匮也4

公理化系统的层次源于高阶逻辑。例如「汉语二字词能表达的动作集合」中,「表达」是二阶逻辑。这促成了以「下一句话是假的,上一句话是真的」成名的罗素悖论。中学教师由于无暇在课堂使用公理化集合论,往往临时加椽拒绝以含高阶逻辑(及「包含自身的集合」)的方式定义集合。

在罗素悖论解决前,有人设想过像 Haskell 一般对集合分层以解决悖论,即划定一些不含更小元素的原子元素,由之构成 α,由 α 构成 β……当然,这种不自在的划分最终被历史遗弃。

残影——落日旌旗大将坛

……又如何被卷入了无穷无尽。
——帕斯卡

简而言之,对角线方法之所以在黑暗中为公理化系统罗曼史的最终破灭引航,是因为它完全不是戴德金式或测度论式的。选取自然数作为本位便是对二者的离经叛道,对角线方法更使数字在行和列上充当两种角色:在行是数字本身,在列是它的位置。更特殊的是,对角线方法总能在一个无穷列表(不仅是数表)里牵出一匹害群之马:它与数表中的同胞一样良定,却不在数表中。

对角线方法是哥德尔配数法跟图灵停机问题的嚆矢5。对后者,数表变为程序在每种输入下的输出值,像

实数  #1 #2 #3 #4 #5 #6... 输入  1  2  3  4  5  6...
甲   [1] 9  4  9  1  0 ... 甲   [停]不 不 不 停 不...
乙    2 [0] 2  3  0  8 ... 乙    停[停]停 停 停 停...
丙    1  4 [1] 5  9  2 ... 丙    不 不[不]不 不 不...
...                        ...

对此进行规约,便是「考虑以下程序:输入一段程序,若其终止则循环,若其循环则终止;将之输入自身,得到矛盾」的经典证明了。继续前进,便是 Y 组合子和 λ 演算——本文标题便用了前者——朴素自指概念在计算机畛域的重生。

缘灭——英雄因何搁笔

Μη μου τους κύκλους τάραττε! 毋残我圆!
——阿基米德的遗言

至于对角线方法如何通向哥德尔不完备,这篇文章5的介绍也语焉不详。在将停机问题的「停机」换成「证明」(在形式系统中,「证明」的含义更像是推导)之前,我们先回到对系统层次的讨论上。

公理化系统是可数的,如今我们只消想想字符编码即可理解。一个自然数可以对应一个含有自由或约束变元、运算符号及全称或存在量词的命题。一个自然数也可以对应一段证明,只需将表示证明过程中每个命题的自然数顺次连接(需要一个序列表示分隔符)即可。

现在系统已经可以表示「证明甲是对命题乙的证明」了。将甲这个数按分隔符分开,若每一步均符合推理规则且最终得到了乙,则为真,否则为假。这一过程可在可确知的步数内完成,是所谓原始递归的。可以证明,我们的系统可以表示(但不限于)所有原始递归的谓词。进一步,我们可以用系统表示「某命题是定理」,只要在「证明甲是对命题乙的证明」中给甲以存在量词即可。

「某命题是定理」是一个系统内的合法命题。因而我们可以说系统具有「次诠释力」,能够诠释它本身。《集》用印符数论(TNT)称呼这种系统,TNT 的次诠释力即 TNT 向元 TNT 伸出了触手。事实上,TNT 还可以表示元元 TNT、元元元 TNT 等。不具次表现力的符号系统是较弱的,即不足以表达足够多的数论。而一旦某个符号系统达到我们目前具有的丰度,便能构造命题使强将投戈,像罗素悖论构造的集合一般:我们要劝降!

我们的手段是使命题嵌入自身。这需要一个开放结构,我们设想含自由变元的表达式(亦写成一个自然数)可以接受参数而变成命题,这样便能输入自身了。例如如果「a 等于 1 吗?」表达式用 2,333,333 表示,输入自身则变为「2,333,333 等于 1 吗?」,是假命题。这一操作《集》称为「算术擓摁6」。我们取

$p(x)=EE q(not "是定理"(q) ^^ "算术擓摁"(x) = q)$

于是,命题

$"算术擓摁"(p)$

便是不可判定的。它在说「我不是定理!」,如同我说「我爱兰州大学」一般,但如此曲折不易。

哥德尔不完备是自欧几里德以来,两千年数学家对公理化憧憬的流产。如果微积分初创时或罗素悖论刚提出时,悲观还在水中悬浮,现在则再无隐藏的必要了。肇始于 19 世纪下半叶的直觉主义数学甚嚣尘上,该派主张放弃排中律,给所有概念以构造定律,然而与更多其他的主张均一筹莫展。如同《三体》的丁仪呼喊物理已不复存在一般,数学真正陷入了彷徨。

入海——光年之外

茂陵不见封侯印,独向渊波哭逝川。
——温庭筠

回到意识上。我们的行为不太会受哥德尔不完备制约,原因之一前文已经述及,即我们同时处于多个系统中。借用《集》的描述,新手对弈时仅仅会排除不合规则的走法(例如车斜走或象横走),而大师会一并忽略多数符合规则的走法,真正需要像计算机般作一番检索的只有几种局面。大师可以快速记忆一个真实的局面,但记忆随机摆放的棋子与常人无异。这表明,大师对棋局的理解超脱于表面。如果新手所用的是 A 系统,大师则可能是在元 A 或元元 A 等系统。

使用多系统意味着能在系统间折跃。例如,棋手会认输或讲和,从而退出棋局所在的系统。我们的系统内部则是怪圈或缠结,其中又蕴含某种自指,丝毫不像 Windows 线程的消息循环一般简单粗暴。

在公理化系统宣告破灭后——公理化系统意在寻找「万能证明」,像是如果停机问题可解,用一段为哥德巴赫方程寻求新解的程序输入停机判定程序,便可根据输出判断哥德巴赫猜想是否成立——人的追求似乎 180 度倒转,来到对意识的模拟上。将意识的层次结构置于与神经元迥异的集成电路(何况我们不知道神经元的连通方式,后者也构成缠结)谈何容易。然而耐人寻味的是,在美国军方停止支持漫无边际的所谓高端研究,而 IBM 等企业渴求短平快时,人工智能由艰深一跃而至火热。

1997 年,《集》迎来出版 20 周年。作者于再版序中称,有人建议根据「深蓝」等最新成果,更动关于人工智能发展的论断,但作者并未应允。彼时,始龀的 Python 语言还在忍受成名前的漫漫长夜。

但当人工智能在大众的印象中「枯木逢春」时,作者终于面对果壳网的镜头给出了答案。他竟用 30 年时间躲开巨头企业的熙熙攘攘,而在最艰难的道路上踽踽独行,试图从他个人的意识流——甚至文艺加无聊的游戏中——挖掘规律。他直言现有的研究项目背离智能的本性,却正如前卫的学者认为智能不必同生物相仿。

如今看来,老侯的自命清高,不过是符号主义—连结主义之争的一部分。前者抱定智能程序必须在高层上(心智)与生物同构(如具有情绪),而底层实现(神经元或逻辑门)可以天差地别;而后者不计较表观上的相似,只强调模拟神经元彼此接通。二者在当下一衰一盛毋庸置疑。报道的笔调明显倾向于相信会有「暮年诗赋动江关7」的一天;不过倘若勒内ㆍ笛卡儿泉下有知,是否会愤然一砸坐标轴,大呼二者皆非?

结论——与败者共舞

爱丁堡大学哲学及心理及语言科学学院的杰弗里ㆍKㆍ普鲁姆曾将停机问题写成一首诗8——虽然不无强行押韵,「坠入理障,无以彰诗歌咏叹之美9」之感。最后一节道:

You can never find general mechanical means
for predicting the acts of computing machines.
It’s something that cannot be done. So we users
must find our own bugs. Our computers are losers!
昏昏幻梦唯归谬,问津所报失文籀。
负笈犹堪寻舛误,计算机尔真瞀瞀!

与其如稚童般称颂计算机的强大,不如接受冷峻的现实,计算机不过是两千年来数学家对公理化的求索郁郁而终的劫后余生。想到这里,再回顾《皇帝新脑》对人工智能的百般讥讽,自是悲悯蕴乎其中。

且慢。计算机是败者?这似乎很不可思议。从表象来看,YouTuber 何同学的镜头之下,信息产业这片「无边赤色之海10」,依旧勃勃生机,不息的信息流正流光溢彩。但当我们以理论的目光洗尽铅华,覆巢之下无完卵,缥缈绝境下哀求自然界不杀之恩的计算机科学11,路在何方?

一夜思想千条路,天明还是拧草绳。我们不应忘记荒野。侯道仁因《集》成名,如今中译版已经再版 50 余次,但他不为仍在增加的读者所理解。老侯不是渴望认同,只是对无人道路的固执坚持而已。

如果我像「汉语是先天缺陷语种」论者一样,四处鼓吹「计算机科学是先天缺陷学科」,也太不解风情了。只希望,老者安之,朋友信之,少者怀之。

(完)

  1. 这段叙述源于宋元时期的高次方程数值解法。「人」是常数项。 

  2. 我之前的《少儿编程与机械启蒙》一文详述过这一现象。 

  3. 不知生物学家在野外观测时是否为此犯难。 

  4. C++ 模板则粗暴有加,不仅将故事严格限制在编译期,还设置层数上限。 

  5. 刘未鹏. 康托尔、哥德尔、图灵:永恒的金色对角线. 2007-08-20  2

  6. 我建议取「揆」字。揆字为群母 A 类旨韵,段玉裁《说文解字注》:「揆,度也」。 

  7. 杜甫《咏怀古迹》其一。 

  8. 史上最牛诗歌:一个停机问题不可判定的证明 | Matrix67: The Aha Moments. 转引自 Matrix67. 

  9. 胡先骕《水杉歌》。 

  10. William Shakesphere 的 Macbeth(《麦克白》)。原文为 multitudinous seas incarnadine。 

  11. 有人声称不能对悬而未决的命题(如 P 与 NP 问题)带有过分幻想,认为守恒量已经是宇宙的恩赐,不该再向宇宙苛求更多。这种想法看似神秘,但以统计力学观之,越平凡的状态越可能出现,也可以理解。