圖源：pixabay

撰文 | 張天蓉

人人都見過瓷磚，鋪瓷磚不需要什么大技術，但瓷磚的形狀，以及如何將它們無縫隙地鋪滿平面，卻有很多學問。它涉及數學中的一個分支，叫做密鋪（或平鋪）幾何。

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]：

“王浩是中國有史以來唯一對哲學做過深刻貢獻的學者。盡管在數學、計算機、邏輯都做過開拓性工作，但他內心把自己當哲學家，這極像哥德爾。中國接觸哲學比科學更晚，胡適、金岳霖和馮友蘭都屬入門。如果按學術共同體的接受作為標準，胡適、金岳霖和馮友蘭都不算專業的哲學家?！?br/>

上面這段話是否準確？很難判定，只能說見仁見智吧。不過，據我所知，王浩在人工智能史上也算個“牛人”。例如，人工智能先驅之一，馬文·閔斯基與王浩是校友、系友，對他很崇拜。

王浩是機器定理證明的奠基人。當年在達特茅斯的會上，人工智能創始人 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–）在他的博士學位論文中推翻了王浩的猜想，不過，王浩的觀察是正確的。伯杰證明了王氏磚問題是不可判定的，即不存在能夠解決該問題的算法?；舅枷胧牵嚎梢詫⑷魏螆D靈機轉變成一組密鋪整個平面的王氏磚，當且僅當此圖靈機永不停止。而停機問題是不可判定的，因此王氏平鋪問題也是不可判定的。

此外，伯杰還具體構造了一組可以實現非周期性密鋪的王氏磚。不過這組王氏磚數目很大，需要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%A9%E6%98%AF%E4%B8%AD%E5%9B%BD%E6%9C%89%E5%8F%B2,%E7%AE%97%E4%B8%93%E4%B8%9A%E7%9A%84%E5%93%B2%E5%AD%A6%E5%AE%B6%E3%80%82