圖源：pixabay

撰文 | 張?zhí)烊?/strong>

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

01 密鋪幾何

什么叫“密鋪”呢？就是說(shuō)，某些幾何圖形，一塊靠一塊鋪滿整個(gè)平面沒有縫隙。比如說(shuō)，我們可以用正多邊形的瓷磚來(lái)鋪地，這種選擇性不是很多，只有3種：正三角形、正方形、正六邊形。

試想正五邊形的瓷磚，是不可能用來(lái)密鋪平面的。因?yàn)槠湮鍡l邊和內(nèi)角都相等，其內(nèi)角是108°，不能整除360°。在用來(lái)覆蓋表面時(shí)不可避免地會(huì)留下縫隙。不過，通過放寬角度和長(zhǎng)度限制，你可以找到各種類型的凸五邊形，它們可以整齊地拼合在一起覆蓋一個(gè)表面。

是的，乍一看，密鋪幾何也不難。剛才說(shuō)的五邊形密鋪，只有15種，而其中的4種都是被一位高中學(xué)歷、身為家庭婦女的業(yè)余女?dāng)?shù)學(xué)家賴斯（Marjorie Rice，1923–2017）找到的[1]。見圖1。

圖1：賴斯發(fā)現(xiàn)的四幅五邊形拼貼圖

密鋪有“周期性密鋪”和“非周期性密鋪”之分。周期性密鋪具有周期性的重復(fù)模式，沒有周期的平鋪是非周期的。

不過，別小看密鋪瓷磚的問題。事實(shí)上，其中的學(xué)問大著呢，研究它的人，有學(xué)者，有教授，有諾貝爾獎(jiǎng)得主，有菲爾茨獎(jiǎng)得主！不急，聽我慢慢道來(lái)。本篇文章介紹的主角，名叫王浩。

02 王浩是何方神圣？

王浩（Wáng Hào，1921 – 1995）[2]是一位著名的華裔美國(guó)邏輯學(xué)家兼哲學(xué)家，我們先看看他的照片和他的與“密鋪”有關(guān)的作品：“王浩瓷磚”（也稱王氏磚），見圖2。

圖2：王浩和王浩瓷磚

也許你不太聽到“王浩”這個(gè)名字，但聽了他的故事后你就明白了：這的確不是一個(gè)等閑之輩，完全可以歸于“大咖”之列。他出生于山東濟(jì)南，父親王祝晨是教育家，滿清的最后一屆舉人。王浩曾經(jīng)兩次考取西南聯(lián)大。第一次錄取的是經(jīng)濟(jì)系，他不喜歡，沒去。第二次又考，以第一名進(jìn)了西南聯(lián)大數(shù)學(xué)系，和楊振寧同住一屋。他1945年清華大學(xué)哲學(xué)系畢業(yè)，師從著名邏輯學(xué)家金岳霖。他當(dāng)年的高等代數(shù)課老師就是楊振寧老爸楊武之。又據(jù)說(shuō)當(dāng)年金岳霖開邏輯學(xué)入門課時(shí)，課堂上基本就是師徒倆對(duì)練功夫，金岳霖經(jīng)常講著講著就問王浩：“哎，你小子說(shuō)說(shuō)咋回事啊？”

王浩清華畢業(yè)之后便到哈佛大學(xué)留學(xué)，跟隨美國(guó)最有影響的哲學(xué)家蒯因研究邏輯和分析哲學(xué)。1948年獲得哈佛大學(xué)邏輯學(xué)博士，同年成為哈佛的助理教授……很難列舉完他的經(jīng)歷和成就，簡(jiǎn)單用一篇文章中的一段評(píng)價(jià)來(lái)概括[3]：

“王浩是中國(guó)有史以來(lái)唯一對(duì)哲學(xué)做過深刻貢獻(xiàn)的學(xué)者。盡管在數(shù)學(xué)、計(jì)算機(jī)、邏輯都做過開拓性工作，但他內(nèi)心把自己當(dāng)哲學(xué)家，這極像哥德爾。中國(guó)接觸哲學(xué)比科學(xué)更晚，胡適、金岳霖和馮友蘭都屬入門。如果按學(xué)術(shù)共同體的接受作為標(biāo)準(zhǔn)，胡適、金岳霖和馮友蘭都不算專業(yè)的哲學(xué)家。”

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

王浩是機(jī)器定理證明的奠基人。當(dāng)年在達(dá)特茅斯的會(huì)上，人工智能創(chuàng)始人 Newell, Shaw 和 Simon（司馬賀）展示過他們的程序“邏輯理論家”（Logic Theorist），證明了《數(shù)學(xué)原理》第2章52個(gè)定理中的38個(gè)。此事震驚計(jì)算機(jī)學(xué)界，王浩卻不怎么放在眼里，曾經(jīng)稱“邏輯理論家”是一個(gè)“不專業(yè)”的工作，并嘲諷他們“殺雞用牛刀”，還說(shuō)：“拿著宰牛刀也沒能把雞殺了”。而王浩自己呢，1958年夏天，他到紐約IBM訪問，興趣一來(lái)便寫了個(gè)程序，在一臺(tái)IBM-704機(jī)上，只用9分鐘就證明了《數(shù)學(xué)原理》中羅列的一階邏輯的全部定理。王浩機(jī)器證明的工作為他贏得了 1983 年定理證明里程碑大獎(jiǎng)。

圖3：學(xué)術(shù)忘年交

盡管王浩在機(jī)器證明及邏輯等領(lǐng)域都做出不凡的貢獻(xiàn)，但他熱衷的，最看得上眼的卻只有哲學(xué)。他有不少大師級(jí)的好友，比如，他與普林斯頓高研院的哥德爾是忘年交（圖3）。

王浩后來(lái)只專注哲學(xué)研究。1995年死于淋巴癌。

03 哥德爾定理

言歸正傳回到瓷磚問題。那是在六十多年前，1960年左右，王浩在英國(guó)牛津大學(xué)任教時(shí)，到美國(guó)新澤西州的貝爾電話實(shí)驗(yàn)室進(jìn)行學(xué)術(shù)訪問的期間，研究了周期性平鋪問題，并提出“王氏瓷磚”。

到貝爾實(shí)驗(yàn)室學(xué)術(shù)交流沒問題，又為什么要研究“周期性平鋪問題”呢？這要從另兩位科學(xué)家：哥德爾和圖靈的工作說(shuō)起……

數(shù)學(xué)家希爾伯特于上世紀(jì)20年代，提出了一個(gè)被稱為“希爾伯特綱領(lǐng)”的數(shù)學(xué)計(jì)劃，主要目標(biāo)是為全部數(shù)學(xué)提供一個(gè)安全的理論基礎(chǔ)，具體而言，對(duì)數(shù)學(xué)系統(tǒng)的要求包括幾個(gè)方面：1，形式化；2，完備性；3，一致性；4，確定性。如果能滿足這4條，任何一個(gè)問題都有解，只需數(shù)學(xué)推演，就可以得到解，數(shù)學(xué)中永遠(yuǎn)沒有我們不知道的。

然而就在1年之后，哥德爾提出的不完備性定理打碎了希爾伯特的美夢(mèng)。比希爾伯特小40歲，當(dāng)年才25歲的哥德爾，證明了數(shù)學(xué)的一致性和完備性不可能同時(shí)存在。也就是說(shuō)，希爾伯特計(jì)劃中的第2、3兩條，不可能同時(shí)滿足。然后，繼哥德爾發(fā)表不完備性定理后沒幾年，比哥德爾還小6歲的圖靈，對(duì)希爾伯特計(jì)劃中有關(guān)確定性的第4條做出了結(jié)論。

圖靈借用他發(fā)明的“通用圖靈機(jī)”證明了，即使這種機(jī)器具有無(wú)限內(nèi)存，能夠按任何指令持續(xù)地作計(jì)算，也不能在有窮的步驟內(nèi)，對(duì)某些問題，給出“是”或“否”的確定性答案。對(duì)此，“停機(jī)問題”是一個(gè)典型的例子。下面稍微用反證法解釋一下，為何計(jì)算機(jī)判定不了是否“停機(jī)”？

假設(shè)，停機(jī)程序可寫成一個(gè)二值函數(shù)P(w)：如果結(jié)果是停機(jī)，P(w)=0；如果結(jié)果是死循環(huán)，P(w)=1。然后，如果存在一個(gè)判斷停機(jī)問題的程序P(w)，那么我們?cè)贅?gòu)造一個(gè)新的程序Q(P(w))，這個(gè)程序與P的輸出正好相反：如果w經(jīng)P判斷為停機(jī)，則Q作死循環(huán)；如果P判斷w為死循環(huán)，則Q立刻停機(jī)。這時(shí)，如果我們把w=Q輸入P，新程序會(huì)得到什么結(jié)果呢？

結(jié)果應(yīng)該是Q(P(w))= Q(P(Q))。意思是說(shuō)：P判定Q是死循環(huán)，但Q停機(jī)了，所以又不是死循環(huán)。也就是說(shuō)，判定的結(jié)果是自相矛盾的：說(shuō)是死循環(huán)又能停機(jī)，說(shuō)能停機(jī)又變成死循環(huán)。因此，出現(xiàn)了計(jì)算機(jī)判定不了的情況，所以，最初的假設(shè)是不正確的，即判定程序P(w)不存在，即不能判定停機(jī)與否。

以上對(duì)停機(jī)問題的敘述，聽起來(lái)非常類似更廣為人知的那個(gè)數(shù)學(xué)悖論“理發(fā)師悖論”。傳說(shuō)有一個(gè)理發(fā)師，將他的顧客定義為城中所有“不給自己理發(fā)之人”。但某一天，當(dāng)他想給自已理發(fā)時(shí)卻發(fā)現(xiàn)他的“顧客”定義是自相矛盾的。因?yàn)槿绻唤o自己理發(fā)，他自己就屬于“顧客”，就應(yīng)該給自己理發(fā)；但如果他給自己理發(fā)，他自己就不屬于“顧客”了，但他給自己理了發(fā)，又是顧客，到底自己算不算顧客？該不該給自己理發(fā)？這邏輯似乎怎么也理不清楚，由此而構(gòu)成了“悖論”。

圖4：與自我指涉有關(guān)的問題

實(shí)際上，停機(jī)問題、理發(fā)師悖論等，本質(zhì)上都與所謂的“自我指涉”有關(guān)，意思就是自已描述自己，自己參照自己，形成一個(gè)無(wú)限循環(huán)永無(wú)止境的邏輯“怪圈”。此類例子還有很多，見圖4。

例如埃舍爾的畫：“畫手”，左手要畫右手，右手要畫左手，結(jié)果形成怪圈而無(wú)解：沒法畫！

圖5：王浩是詮釋哥德爾的專家

實(shí)際上，王浩不僅是哥德爾的忘年交，更是詮釋哥德爾思想的權(quán)威性專家，他有好幾本深刻解釋哥德爾理論的著作，見圖5。王浩從1953年就開始考慮機(jī)器證明問題，因此對(duì)哥德爾定理和圖靈機(jī)都感興趣，可惜圖靈在1954年就去世了。那年王浩剛到英國(guó)牛津大學(xué)任數(shù)學(xué)哲學(xué)教授，他作了一些圖靈機(jī)的相關(guān)工作，直到1958年開始到紐約IBM訪問，王浩與普林斯頓的哥德爾可以經(jīng)常見面了，并成為忘年交。正是在那段時(shí)間，他發(fā)明了王氏瓷磚。

04 王氏瓷磚問題

所謂王式瓷磚是一系列涂有顏色的方形瓷磚，正方形的每一邊可以有不同的顏色，一個(gè)王氏磚的正方形中里可以涂2至4個(gè)不同的顏色。因?yàn)橛辛祟伾云春蠒r(shí)就有了一些規(guī)則：首先，二個(gè)磚相鄰邊的顏色必須相同；另外，每一個(gè)磚，不允許旋轉(zhuǎn)和翻面。

關(guān)于特定一組（有限多個(gè)）王氏磚的基本問題是：是否可以用一組王氏磚來(lái)密鋪平面？

更進(jìn)一步，這個(gè)問題引起一個(gè)與圖靈“可計(jì)算函數(shù)”類似的問題：能否找到一個(gè)計(jì)算機(jī)算法，判定一組王氏磚的基本問題“是否”有解？換言之，王氏磚的問題是“可判定性”的，還是不“可判定性”的？

王浩觀察到，如果這個(gè)問題是不可判定的，那么就必須存在一組非周期的王氏磚拼圖。王浩覺得難以想象存在這種拼圖，于是便猜想：王氏磚問題是“可判定性”的，非周期王氏磚密鋪不存在。

然而，1964年，王浩的學(xué)生羅伯特·伯杰（Robert Berger，1938–）在他的博士學(xué)位論文中推翻了王浩的猜想，不過，王浩的觀察是正確的。伯杰證明了王氏磚問題是不可判定的，即不存在能夠解決該問題的算法。基本思想是：可以將任何圖靈機(jī)轉(zhuǎn)變成一組密鋪整個(gè)平面的王氏磚，當(dāng)且僅當(dāng)此圖靈機(jī)永不停止。而停機(jī)問題是不可判定的，因此王氏平鋪問題也是不可判定的。

此外，伯杰還具體構(gòu)造了一組可以實(shí)現(xiàn)非周期性密鋪的王氏磚。不過這組王氏磚數(shù)目很大，需要20426 個(gè)。1968 年，美國(guó)計(jì)算機(jī)科學(xué)家唐納德·高德納（Donald E. Knuth，1938–）修改了伯杰的構(gòu)造程序，發(fā)現(xiàn)只需要 92 個(gè)王氏磚就可以了。之后，這個(gè)數(shù)目不斷減少，直到2015年，法國(guó)計(jì)算機(jī)科學(xué)家 Emmanuel Jeandel 和 Michael Rao 證明了，只需11個(gè)王氏磚便足夠?qū)崿F(xiàn)非周期性密鋪，如圖2所示。

從對(duì)王浩磚的研究開始，第一次將密鋪問題與“可計(jì)算理論”、“圖靈機(jī)”等聯(lián)系起來(lái)，由此也引發(fā)了數(shù)學(xué)家們對(duì)“非周期性密鋪”的興趣。例如，諾貝爾獎(jiǎng)得主彭羅斯對(duì)此作了不少貢獻(xiàn)。此外，兩年前，菲爾茲獎(jiǎng)得主、美國(guó)華裔數(shù)學(xué)家陶哲軒（Terence Tao）發(fā)表了一篇長(zhǎng)文，宣布他推翻了高維空間的“周期性平鋪猜想”。

參考資料：

[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