同构

本书从数字、递归、对称、范畴、融合、无穷、悖论七个方面介绍了计算机程序的数学基础和原理，并以“同构”概念为线索揭示出编程本质上是和数学同构的。第1章介绍皮亚诺算术公理系统,通过5条公理，构筑了计算机程序大厦的基石;通过单向链表、斐波那契数列等例子，展示了和自然数同构的计算结构。第2章介绍递归，通过欧几里得算法作为开端，最终把递归的数学原理构建在Lambda演算和Y组合子之上。第3章介绍对称群、环、域等抽象代数结构，解释了伽罗瓦理论这一抽象思维的明珠。第4章介绍范畴论，把列表、异常、多态、类型系统、复合数据结构等众多编程概念构筑在范畴论的基础上。第5章介绍融合律，它是进行算法推导和优化的有力工具。第6章介绍无穷，给出了康托尔的无穷集合论和超限数概念，介绍了编程中流的概念和无穷的关系。第7章以罗素悖论、可计算性和哥德尔不完全性定理结束本书，介绍了计算能力的边界和对编程基础哲学的影响。
本书还在各个章节中介绍相关数学家的人生经历和逸闻趣事，讲解他们如何克服困难、追求真理、创造奇迹，并穿插讲述编程、数学、艺术、音乐之间的有趣联系。

刘新宇 亚马逊中国研发中心研发经理，负责分布式仓储物流系统的开发。1999年和2002年在清华大学自动化系分别获得学士和硕士学位。长期专注于函数式基础算法，著有《算法新解》一书（2017年出版）。

从数字、递归、对称、范畴、融合、无穷、悖论七个方面介绍了计算机程序的数学基础和原理

前言
我先来讲一个从马爷爷那里听来的故事。有一年春节，北京地坛公园的庙会热闹非凡，人山人海，小朋友们拿着压岁钱在各种摊位上买自己喜欢的玩具。公园外路边有一个摊位上围了一群人。地上一字排开摆了九个小玩具，每个玩具上依次贴着一元、二元、三元……九元的标签，如下所示：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789注：1，2，…，9分别表示一元、二元……九元。
摊主一边向大家吆喝，一边讲解游戏规则：“大家快来玩套圈游戏！一次一元钱，你扔一个，我扔一个，一个玩具只能套一个圈。谁能先套中三个加在一起值十五元的玩具算谁赢，你要是赢了，所有套中的玩具都归你。”
有个小男孩掏出一元钱，拿了一个红色的圈，使劲一扔。真准！正好套在了七元钱的玩具汽车上，摊主拿出一个蓝色的圈，一下子套中了八元钱的兔爷，结果如下：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789男孩摊主
小男孩又花了一元钱，这次他套中了价值两元的风车，这样只要他下次再套中那个六元钱的九连环就赢了。可这次摊主不慌不忙地套住了那只九连环，结果如下：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789男孩摊主男孩摊主
这下可糟了，如果接下来摊主再套中那个一元钱的中国结，小男孩就要输了。小男孩涨红了脸，只能抢先去套那个中国结，他试了两次终于套中了，结果如下：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789男孩男孩摊主男孩摊主
摊主接下来扔了一个圈，套住了四元钱的孙悟空面具，小男孩套住了五元钱的小猪存钱罐，结果如下：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789男孩男孩摊主男孩摊主男孩摊主
但是摊主扔出一个圈，套住了三元钱的不倒翁，结果如下：中国结风车不倒翁孙悟空面具小猪存钱罐九连环汽车兔爷走马灯123456789男孩男孩摊主摊主男孩摊主男孩摊主
由于3+4+8=15，小男孩输了。
周围的人看着很好玩，也纷纷掏钱套圈玩。马爷爷看了一阵，觉得很奇怪，大多数情况下都是摊主赢，偶尔会平局。马爷爷怀疑摊主一定有什么秘密，他只是为了避免人们怀疑，有时才故意输掉游戏。
马爷爷回到家，电视里正在讲中国古老的“河图洛书”，据说在文字尚未发明之前，伏羲治理天下的时候，在黄河支流，有乌龟背负着神秘的图案爬上岸来。如果把图案中的圆点数目用现代的方法表示出来，就是一个数学上的三阶幻方，如图0.1所示。
可别被这个名字吓到，就是方形的九个格子里每行、每列、两条对角线上的三个数字加起来都相等，都等于15。例如，第一行的数字相加是4+9+2=15，第三列的数字相加是2+7+6=15，左上右下的对角线的数字相加是4+5+6=15。“等一等，”马爷爷想，“我现在知道庙会里套圈游戏背后的秘密了。”如果要套中的三个玩具加起来等于十五元，那么就相当于套中了三阶幻方的一行、一列或一条对角线。如果摊主在柜台里偷偷藏一张三阶幻方的图，那么他实际上相当于在和游人玩俗称“一条龙”的井字棋游戏，如图0.2所示。图0.1河图洛书与三阶幻方图0.2三阶幻方与井字棋游戏庙会中那个小男孩和摊主的套圈游戏相当于下面的井字棋对局。摊主在关键的第三步中给小男孩设置了一个陷阱，他在第一列上和一条对角线上同时可能连成直线，如果小男孩套中3，则摊主套中5依然能赢，如图0.3所示。如果了解过博弈游戏，或者知道一点编程，你就知道井字棋游戏没有必胜的策略，如果游戏双方都足够小心，结果一定是平局。偷偷拥有三阶幻方图的摊主这样就站在了不败的地位上，而其他游客一无所知。
图0.3对弈过程
这个故事是真的吗？当然不是，马爷爷是个虚构的人物，他在真实世界中名叫马丁·加德纳——举世闻名的美国趣味数学大师。这个故事来自他的《啊哈！灵机一动》。故事不是发生在北京的地坛公园，而是美国的乡村小镇。摊主名叫卡内，而玩游戏的小男孩实际是一位女士。这个游戏也不是中国传统的套圈游戏，而是用硬币盖住一排数字。
这个故事和其中所讲的游戏不断地在说着一个重要的概念——同构。庙会上的套圈游戏和井字棋同构，一行九个数字对应三行三列的格子，相加等于15的目标对应九宫格中的行、列、对角线，古老的“河图洛书”对应三阶幻方，马爷爷对应加德纳，中国的春节庙会对应美国乡村游乐……这其实也是本书想传达的概念——编程与数学同构，与艺术同构，与音乐同构。伟大的发现背后有曲折的故事和性格迥异的数学家。
这个故事还有一层隐喻，问题的表象下隐藏着和它同构的理论实质，我们需要了解抽象的本质而不被具体的现象蒙住眼睛。在人工智能和机器学习日新月异的今天，我们能否还靠着一点点聪明和工程实践继续前行？我们是否要打开那些神秘的黑盒子找到那个指引我们前进的地图？

刘新宇
2022年5月于北京