撰文 | 张天蓉

● 　● 　●

人人都见过瓷砖，铺瓷砖不需要什么大技术，但瓷砖的形状，以及如何将它们无缝隙地铺满平面，却有很多学问。它涉及数学中的一个分支，叫做密铺（或平铺）几何。

01

密铺几何

什么叫“密铺”呢？就是说，某些几何图形，一块靠一块铺满整个平面没有缝隙。比如说，我们可以用正多边形的瓷砖来铺地，这种选择性不是很多，只有3种：正三角形、正方形、正六边形。

试想正五边形的瓷砖，是不可能用来密铺平面的。因为其五条边和内角都相等，其内角是108°，不能整除360°。在用来覆盖表面时不可避免地会留下缝隙。不过，通过放宽角度和长度限制，你可以找到各种类型的凸五边形，它们可以整齐地拼合在一起覆盖一个表面。

是的，乍一看，密铺几何也不难。刚才说的五边形密铺，只有15种，而其中的4种都是被一位高中学历、身为家庭妇女的业余女数学家赖斯（Marjorie Rice，1923–2017）找到的[1]。见图1。

图1：赖斯发现的四幅五边形拼贴图

密铺有“周期性密铺”和“非周期性密铺”之分。周期性密铺具有周期性的重复模式，没有周期的平铺是非周期的。

不过，别小看密铺瓷砖的问题。事实上，其中的学问大着呢，研究它的人，有学者，有教授，有诺贝尔奖得主，有菲尔茨奖得主！不急，听我慢慢道来。本篇文章介绍的主角，名叫王浩。

02

王浩是何方神圣？

王浩（Wáng Hào，1921 – 1995）[2]是一位著名的华裔美国逻辑学家兼哲学家，我们先看看他的照片和他的与“密铺”有关的作品：“王浩瓷砖”（也称王氏砖），见图2。

图2：王浩和王浩瓷砖

也许你不太听到“王浩”这个名字，但听了他的故事后你就明白了：这的确不是一个等闲之辈，完全可以归于“大咖”之列。他出生于山东济南，父亲王祝晨是教育家，满清的最后一届举人。王浩曾经两次考取西南联大。第一次录取的是经济系，他不喜欢，没去。第二次又考，以第一名进了西南联大数学系，和杨振宁同住一屋。他1945年清华大学哲学系毕业，师从著名逻辑学家金岳霖。他当年的高等代数课老师就是杨振宁老爸杨武之。又据说当年金岳霖开逻辑学入门课时，课堂上基本就是师徒俩对练功夫，金岳霖经常讲着讲着就问王浩：“哎，你小子说说咋回事啊？”

王浩清华毕业之后便到哈佛大学留学，跟随美国最有影响的哲学家蒯因研究逻辑和分析哲学。1948年获得哈佛大学逻辑学博士，同年成为哈佛的助理教授……很难列举完他的经历和成就，简单用一篇文章中的一段评价来概括[3]：

“王浩是中国有史以来唯一对哲学做过深刻贡献的学者。尽管在数学、计算机、逻辑都做过开拓性工作，但他内心把自己当哲学家，这极像哥德尔。中国接触哲学比科学更晚，胡适、金岳霖和冯友兰都属入门。如果按学术共同体的接受作为标准，胡适、金岳霖和冯友兰都不算专业的哲学家。”

上面这段话是否准确？很难判定，只能说见仁见智吧。不过，据我所知，王浩在人工智能史上也算个“牛人”。例如，人工智能先驱之一，马文·闵斯基与王浩是校友、系友，对他很崇拜。

王浩是机器定理证明的奠基人。当年在达特茅斯的会上，人工智能创始人 Newell, Shaw 和 Simon（司马贺）展示过他们的程序“逻辑理论家”（Logic Theorist），证明了《数学原理》第2章52个定理中的38个。此事震惊计算机学界，王浩却不怎么放在眼里，曾经称“逻辑理论家”是一个“不专业”的工作，并嘲讽他们“杀鸡用牛刀”，还说：“拿着宰牛刀也没能把鸡杀了”。而王浩自己呢，1958年夏天，他到纽约IBM访问，兴趣一来便写了个程序，在一台IBM-704机上，只用9分钟就证明了《数学原理》中罗列的一阶逻辑的全部定理。王浩机器证明的工作为他赢得了 1983 年定理证明里程碑大奖。

图3：学术忘年交

尽管王浩在机器证明及逻辑等领域都做出不凡的贡献，但他热衷的，最看得上眼的却只有哲学。他有不少大师级的好友，比如，他与普林斯顿高研院的哥德尔是忘年交（图3）。

王浩后来只专注哲学研究。1995年死于淋巴癌。

03

哥德尔定理

言归正传回到瓷砖问题。那是在六十多年前，1960年左右，王浩在英国牛津大学任教时，到美国新泽西州的贝尔电话实验室进行学术访问的期间，研究了周期性平铺问题，并提出“王氏瓷砖”。

到贝尔实验室学术交流没问题，又为什么要研究“周期性平铺问题”呢？这要从另两位科学家：哥德尔和图灵的工作说起……

数学家希尔伯特于上世纪20年代，提出了一个被称为“希尔伯特纲领”的数学计划，主要目标是为全部数学提供一个安全的理论基础，具体而言，对数学系统的要求包括几个方面：1，形式化；2，完备性；3，一致性；4，确定性。如果能满足这4条，任何一个问题都有解，只需数学推演，就可以得到解，数学中永远没有我们不知道的。

然而就在1年之后，哥德尔提出的不完备性定理打碎了希尔伯特的美梦。比希尔伯特小40岁，当年才25岁的哥德尔，证明了数学的一致性和完备性不可能同时存在。也就是说，希尔伯特计划中的第2、3两条，不可能同时满足。然后，继哥德尔发表不完备性定理后没几年，比哥德尔还小6岁的图灵，对希尔伯特计划中有关确定性的第4条做出了结论。

图灵借用他发明的“通用图灵机”证明了，即使这种机器具有无限内存，能够按任何指令持续地作计算，也不能在有穷的步骤内，对某些问题，给出“是”或“否”的确定性答案。对此，“停机问题”是一个典型的例子。下面稍微用反证法解释一下，为何计算机判定不了是否“停机”？

假设，停机程序可写成一个二值函数P(w)：如果结果是停机，P(w)=0；如果结果是死循环，P(w)=1。然后，如果存在一个判断停机问题的程序P(w)，那么我们再构造一个新的程序Q(P(w))，这个程序与P的输出正好相反：如果w经P判断为停机，则Q作死循环；如果P判断w为死循环，则Q立刻停机。这时，如果我们把w=Q输入P，新程序会得到什么结果呢？

结果应该是Q(P(w))= Q(P(Q))。意思是说：P判定Q是死循环，但Q停机了，所以又不是死循环。也就是说，判定的结果是自相矛盾的：说是死循环又能停机，说能停机又变成死循环。因此，出现了计算机判定不了的情况，所以，最初的假设是不正确的，即判定程序P(w)不存在，即不能判定停机与否。

以上对停机问题的叙述，听起来非常类似更广为人知的那个数学悖论“理发师悖论”。传说有一个理发师，将他的顾客定义为城中所有“不给自己理发之人”。但某一天，当他想给自已理发时却发现他的“顾客”定义是自相矛盾的。因为如果他不给自己理发，他自己就属于“顾客”，就应该给自己理发；但如果他给自己理发，他自己就不属于“顾客”了，但他给自己理了发，又是顾客，到底自己算不算顾客？该不该给自己理发？这逻辑似乎怎么也理不清楚，由此而构成了“悖论”。

图4：与自我指涉有关的问题

实际上，停机问题、理发师悖论等，本质上都与所谓的“自我指涉”有关，意思就是自已描述自己，自己参照自己，形成一个无限循环永无止境的逻辑“怪圈”。此类例子还有很多，见图4。

例如埃舍尔的画：“画手”，左手要画右手，右手要画左手，结果形成怪圈而无解：没法画！

图5：王浩是诠释哥德尔的专家

实际上，王浩不仅是哥德尔的忘年交，更是诠释哥德尔思想的权威性专家，他有好几本深刻解释哥德尔理论的著作，见图5。王浩从1953年就开始考虑机器证明问题，因此对哥德尔定理和图灵机都感兴趣，可惜图灵在1954年就去世了。那年王浩刚到英国牛津大学任数学哲学教授，他作了一些图灵机的相关工作，直到1958年开始到纽约IBM访问，王浩与普林斯顿的哥德尔可以经常见面了，并成为忘年交。正是在那段时间，他发明了王氏瓷砖。

04

王氏瓷砖问题

所谓王式瓷砖是一系列涂有颜色的方形瓷砖，正方形的每一边可以有不同的颜色，一个王氏砖的正方形中里可以涂2至4个不同的颜色。因为有了颜色，所以拼合时就有了一些规则：首先，二个砖相邻边的颜色必须相同；另外，每一个砖，不允许旋转和翻面。

关于特定一组（有限多个）王氏砖的基本问题是：是否可以用一组王氏砖来密铺平面？

更进一步，这个问题引起一个与图灵“可计算函数”类似的问题：能否找到一个计算机算法，判定一组王氏砖的基本问题“是否”有解？换言之，王氏砖的问题是“可判定性”的，还是不“可判定性”的？

王浩观察到，如果这个问题是不可判定的，那么就必须存在一组非周期的王氏砖拼图。王浩觉得难以想象存在这种拼图，于是便猜想：王氏砖问题是“可判定性”的，非周期王氏砖密铺不存在。

然而，1964年，王浩的学生罗伯特·伯杰（Robert Berger，1938–）在他的博士学位论文中推翻了王浩的猜想，不过，王浩的观察是正确的。伯杰证明了王氏砖问题是不可判定的，即不存在能够解决该问题的算法。基本思想是：可以将任何图灵机转变成一组密铺整个平面的王氏砖，当且仅当此图灵机永不停止。而停机问题是不可判定的，因此王氏平铺问题也是不可判定的。

此外，伯杰还具体构造了一组可以实现非周期性密铺的王氏砖。不过这组王氏砖数目很大，需要20426 个。1968 年，美国计算机科学家唐纳德·高德纳（Donald E. Knuth，1938–）修改了伯杰的构造程序，发现只需要 92 个王氏砖就可以了。之后，这个数目不断减少，直到2015年，法国计算机科学家 Emmanuel Jeandel 和 Michael Rao 证明了，只需11个王氏砖便足够实现非周期性密铺，如图2所示。

从对王浩砖的研究开始，第一次将密铺问题与“可计算理论”、“图灵机”等联系起来，由此也引发了数学家们对“非周期性密铺”的兴趣。例如，诺贝尔奖得主彭罗斯对此作了不少贡献。此外，两年前，菲尔兹奖得主、美国华裔数学家陶哲轩（Terence Tao）发表了一篇长文，宣布他推翻了高维空间的“周期性平铺猜想”。

参考资料：

[1]https://en.wikipedia.org/wiki/Marjorie_Rice

[2]https://zh.wikipedia.org/wiki/%E7%8E%8B%E6%B5%A9_(%E6%95%B0%E5%AD%A6%E5%AE%B6)

[3]百年清华，王浩和他的朋友们（作者 尼克）https://www.tsighua.org.cn/info/1951/18400.htm#:~:text=%E7%8E%8B%E6%B5%A