王氏砖

王氏砖（）也稱為王氏多米诺骨牌，最早由美籍華裔数学家、逻辑学家和哲学家王浩于1961年提出，屬於，也是形式系統。

王氏砖的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏砖拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。

关于特定一組王氏砖的基本问题是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式填合无限大的平面。下一個问题是是否存在周期性的密鋪方式？

 多米诺骨牌问题 
缩略图|400x400像素|例：由13个王氏砖組成的密鋪
王浩于1961年提出猜想，如果一组有限多個的王氏砖可以在邻边相互匹配的條件下，密铺整个平面，那么也存在針對這組王氏砖的周期性密铺铺法，也就是说这种铺法在二维点阵中的矢量平移转换下不变，就如壁纸图案一般。他还观察到，若這個猜想成立意味着有一种算法，可以用来判断任何一组有限多個的王氏砖是否可以密铺整个平面 . Presents the domino problem for a popular audience.。将瓷砖按照相邻边相互匹配的想法见于多米诺骨牌游戏中，所以王氏砖也被称为王氏多米诺骨牌。 .判断一组骨牌是否可以平铺整个平面的算法问题被称为多米诺骨牌问题. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them. 。  

根据王浩的学生，所言. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.多米诺骨牌问题指的是，如何判断任何一组多米诺骨牌是否可解？对于任意规格的一组多米诺骨牌，若存在一种算法来帮助判定它是否可解，则我们讲多米诺骨牌问题是「可判定」的。 否则是「无法判定」的。换句话说，多米诺骨牌问题问的是，是否存在一个，对任何多米诺骨牌集，都能正确地解决问题？

1966年，伯杰解决了王氏砖的多米诺骨牌问题，他证明了不存在能够解决该问题的算法。其解法如下：可以将任何图灵机转变成一组密铺整个平面的王氏平铺，当且仅当此图灵机永不停止。而停机问题（测试图灵机是否最终停止的问题）的不可判断性导致了王氏平铺问题的不可判定性。

 非周期性的瓷砖组 
结合王浩的观察以及伯杰的不可判断性结果，可以推测存在一组有限多個的王氏砖，可以密铺整个二维平面，但只能非周期性密铺。此密铺类似，或准晶体中原子的排列。

伯杰在論文中有提到一種非周期性密铺集合，是由20,426块王氏砖組合，但他猜测也可能存在只能非周期性密铺的較小集合。伯杰发表的博士学位论文中有提到數量較少（104个）的王氏砖。在后来的几年中，又发现了越来越少的王氏砖组. （包括5個顏色的13個王氏磚） . （包括4個顏色的11個王氏磚）}。例如，上图中给出的13个图块是由Karel Culik II于1996年出版的非周期集。它可以密铺二维平面，但不能周期性密铺。2015年Emmanuel Jeandel和Michael Rao发现了使用4种颜色的11块非周期性密铺集合，并使用暴力搜索来確定，若減到10块王氏磚或是只有3种颜色，都不足以强制非周期性。

 擴展 
王氏砖可以擴展為其他的形式，而許多相關的問題也是不可判定的。例如，王氏立方体（Wang cubes）是具有彩色面的正立方体，相对的面拼合时需要有相同的颜色。Culik和Kari展示了非周期性的王氏立方体.。 Winfree等已经证明了用DNA制成的分子“砖”的可行性，它与王氏砖有相似之处。米塔尔等人已经证明，这些王氏“砖”可以由肽核酸 （PNA）组成，肽核酸是稳定的DNA人工模拟物.。

 应用 
王氏砖已用來做為程序化生成的產生工具，可以用來產生纹理、地形和其他大型和非重复的二维数据集。可以用较便宜的成本，预先计算或手工制作一小组的「源砖」，確認其它们拼貼出的结果不会有太明显的重复，且没有周期性。在这种情况下，传统的非周期性方格排列显示其非常规则的结构。王氏砖程序化生成的限制較少，而且确保可以密铺，并且可以用伪随机的方式选择每块砖 . Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system. . Introduces stochastic tiling. . Applies Wang Tiles for real-time texturing on a GPU. . . Shows advanced applications.。

王氏砖也用于細胞自動機理论中决定性问题的证明.。

 流行文化 
澳洲作家格雷格·伊根有一個短篇故事《王氏地毯》，后来扩展為小说《》（Diaspora），描写了有有居民生物和智慧生物的假想宇宙，這些生物都是由复杂分子模式实现的王氏砖。

 参见 



 TetraVex

 参考文献 

 外部链接 

 Steven Dutch的页面，包括许多非周期性瓷砖的图片 
 一个简单的王氏平铺方法的动画演示  - 需要Javascript和HTML5

 延伸阅读 


Category:計算理論
Category:1961年面世
Category:镶嵌