text: 王氏磚也稱為王氏多米諾骨牌，最早由美籍華裔數學家、邏輯學家和哲學家王浩於1961年提出，屬於，也是形式系統。王氏磚的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏磚拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。關於特定一組王氏磚的基本問題是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式填合無限大的平面。下一個問題是是否存在週期性的密鋪方式？多米諾骨牌問題.王浩於1961年提出猜想，如果一組有限多個的王氏磚可以在鄰邊相互匹配的條件下，密鋪整個平面，那麼也存在針對這組王氏磚的週期性密鋪鋪法，也就是說這種鋪法在二維點陣中的向量平移轉換下不變，就如桌布圖案一般。他還觀察到，若這個猜想成立意味著有一種演算法，可以用來判斷任何一組有限多個的王氏磚是否可以密鋪整個平面 。將瓷磚按照相鄰邊相互匹配的想法見於多米諾骨牌遊戲中，所以王氏磚也被稱為王氏多米諾骨牌。 判斷一組骨牌是否可以平鋪整個平面的演算法問題被稱為多米諾骨牌問題 。根據王浩的學生，所言多米諾骨牌問題指的是，如何判斷任何一組多米諾骨牌是否可解？對於任意規格的一組多米諾骨牌，若存在一種演算法來幫助判定它是否可解，則我們講多米諾骨牌問題是「可判定」的。 否則是「無法判定」的。換句話說，多米諾骨牌問題問的是，是否存在一個，對任何多米諾骨牌集，都能正確地解決問題？1966年，伯傑解決了王氏磚的多米諾骨牌問題，他證明了不存在能夠解決該問題的演算法。其解法如下：可以將任何圖靈機轉變成一組密鋪整個平面的王氏平鋪，當且僅當此圖靈機永不停止。而停機問題的不可判斷性導致了王氏平鋪問題的不可判定性。非週期性的瓷磚組.結合王浩的觀察以及伯傑的不可判斷性結果，可以推測存在一組有限多個的王氏磚，可以密鋪整個二維平面，但只能非週期性密鋪。此密鋪類似，或準晶體中原子的排列。伯傑在論文中有提到一種非週期性密鋪集合，是由20,426塊王氏磚組合，但他猜測也可能存在只能非週期性密鋪的較小集合。伯傑發表的博士學位論文中有提到數量較少的王氏磚。在後來的幾年中，又發現了越來越少的王氏磚組 。例如，上圖中給出的13個圖塊是由Karel Culik II於1996年出版的非週期集。它可以密鋪二維平面，但不能週期性密鋪。2015年Emmanuel Jeandel和Michael Rao發現了使用4種顏色的11塊非週期性密鋪集合，並使用暴力搜尋來確定，若減到10塊王氏磚或是隻有3種顏色，都不足以強制非週期性。擴充套件.王氏磚可以擴充套件為其他的形式，而許多相關的問題也是不可判定的。例如，王氏立方體組成，肽核酸是穩定的DNA人工模擬物。應用.王氏磚已用來做為程式化生成的產生工具，可以用來產生紋理、地形和其他大型和非重複的二維資料集。可以用較便宜的成本，預先計算或手工製作一小組的「源磚」，確認其它們拼貼出的結果不會有太明顯的重複，且沒有周期性。在這種情況下，傳統的非週期性方格排列顯示其非常規則的結構。王氏磚程式化生成的限制較少，而且確保可以密鋪，並且可以用偽隨機的方式選擇每塊磚 。王氏磚也用於細胞自動機理論中決定性問題的證明。流行文化.澳洲作家格雷格·伊根有一個短篇故事《王氏地毯》，後來擴充套件為小說《》，描寫了有有居民生物和智慧生物的假想宇宙，這些生物都是由複雜分子模式實現的王氏磚。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 王氏磚
metadata: https://zh.wikipedia.org/wiki?curid=6691111