人人都見過瓷磚，鋪瓷磚不需要什麼大技術，但瓷磚的形狀，以及如何將它們無縫隙地鋪滿平面，卻有很多學問。它涉及數學中的一個分支，叫做密鋪（或平鋪）幾何。
01
密鋪幾何
什麼叫「密鋪」呢？就是說，某些幾何圖形，一塊靠一塊鋪滿整個平面沒有縫隙。比如說，我們可以用正多邊形的瓷磚來鋪地，這種選擇性不是很多，只有3種：正三角形、正方形、正六邊形。
試想正五邊形的瓷磚，是不可能用來密鋪平面的。因為其五條邊和內角都相等，其內角是108°，不能整除360°。在用來覆蓋表面時不可避免地會留下縫隙。不過，通過放寬角度和長度限制，你可以找到各種類型的凸五邊形，它們可以整齊地拼合在一起覆蓋一個表面。
是的，乍一看，密鋪幾何也不難。剛才說的五邊形密鋪，只有15種，而其中的4種都是被一位高中學歷、身為家庭婦女的業餘女數學家賴斯（MarjorieRice，1923–2017）找到的[1]。見圖1。
圖1：賴斯發現的四幅五邊形拼貼圖
密鋪有「周期性密鋪」和「非周期性密鋪」之分。周期性密鋪具有周期性的重複模式，沒有周期的平鋪是非周期的。
不過，別小看密鋪瓷磚的問題。事實上，其中的學問大着呢，研究它的人，有學者，有教授，有諾貝爾獎得主，有菲爾茨獎得主！不急，聽我慢慢道來。本篇文章介紹的主角，名叫王浩。
02
王浩是何方神聖？
王浩（Wáng Hào，1921–1995）[2]是一位著名的華裔美國邏輯學家兼哲學家，我們先看看他的照片和他的與「密鋪」有關的作品：「王浩瓷磚」（也稱王氏磚），見圖2。
圖2：王浩和王浩瓷磚
也許你不太聽到「王浩」這個名字，但聽了他的故事後你就明白了：這的確不是一個等閒之輩，完全可以歸於「大咖」之列。他出生於山東濟南，父親王祝晨是教育家，滿清的最後一屆舉人。王浩曾經兩次考取西南聯大。第一次錄取的是經濟系，他不喜歡，沒去。第二次又考，以第一名進了西南聯大數學系，和楊振寧同住一屋。他1945年清華大學哲學系畢業，師從著名邏輯學家金岳霖。他當年的高等代數課老師就是楊振寧老爸楊武之。又據說當年金岳霖開邏輯學入門課時，課堂上基本就是師徒倆對練功夫，金岳霖經常講着講着就問王浩：「哎，你小子說說咋回事啊？」
王浩清華畢業之後便到哈佛大學留學，跟隨美國最有影響的哲學家蒯因研究邏輯和分析哲學。1948年獲得哈佛大學邏輯學博士，同年成為哈佛的助理教授……很難列舉完他的經歷和成就，簡單用一篇文章中的一段評價來概括[3]：
「王浩是中國有史以來唯一對哲學做過深刻貢獻的學者。儘管在數學、計算機、邏輯都做過開拓性工作，但他內心把自己當哲學家，這極像哥德爾。中國接觸哲學比科學更晚，胡適、金岳霖和馮友蘭都屬入門。如果按學術共同體的接受作為標準，胡適、金岳霖和馮友蘭都不算專業的哲學家。」
上面這段話是否準確？很難判定，只能說見仁見智吧。不過，據我所知，王浩在人工智能史上也算個「牛人」。例如，人工智能先驅之一，馬文·閔斯基與王浩是校友、系友，對他很崇拜。
王浩是機器定理證明的奠基人。當年在達特茅斯的會上，人工智能創始人 Newell, Shaw和Simon（司馬賀）展示過他們的程序「邏輯理論家」（LogicTheorist），證明了《數學原理》第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年，王浩的學生羅伯特·伯傑（RobertBerger，1938–）在他的博士學位論文中推翻了王浩的猜想，不過，王浩的觀察是正確的。伯傑證明了王氏磚問題是不可判定的，即不存在能夠解決該問題的算法。基本思想是：可以將任何圖靈機轉變成一組密鋪整個平面的王氏磚，當且僅當此圖靈機永不停止。而停機問題是不可判定的，因此王氏平鋪問題也是不可判定的。
此外，伯傑還具體構造了一組可以實現非周期性密鋪的王氏磚。不過這組王氏磚數目很大，需要20426個。1968年，美國計算機科學家唐納德·高德納（Donald E. Knuth，1938–）修改了伯傑的構造程序，發現只需要92個王氏磚就可以了。之後，這個數目不斷減少，直到2015年，法國計算機科學家 Emmanuel Jeandel和 MichaelRao證明了，只需11個王氏磚便足夠實現非周期性密鋪，如圖2所示。
從對王浩磚的研究開始，第一次將密鋪問題與「可計算理論」、「圖靈機」等聯繫起來，由此也引發了數學家們對「非周期性密鋪」的興趣。例如，諾貝爾獎得主彭羅斯對此作了不少貢獻。此外，兩年前，菲爾茲獎得主、美國華裔數學家陶哲軒（TerenceTao）發表了一篇長文，宣佈他推翻了高維空間的「周期性平鋪猜想」。
