王氏砖

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

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

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

多米诺骨牌问题
王浩于1961年提出猜想，如果一组有限多個的王氏砖可以在邻边相互匹配的條件下，密铺整个平面，那么也存在針對這組王氏砖的周期性密铺铺法，也就是说这种铺法在二维点阵中的矢量平移转换下不变，就如壁纸图案一般。他还观察到，若這個猜想成立意味着有一种算法，可以用来判断任何一组有限多個的王氏砖是否可以密铺整个平面。将瓷砖按照相邻边相互匹配的想法见于多米诺骨牌游戏中，所以王氏砖也被称为王氏多米诺骨牌。判断一组骨牌是否可以平铺整个平面的算法问题被称为多米诺骨牌问题 。

根据王浩的学生，所言
多米诺骨牌问题指的是，如何判断任何一组多米诺骨牌是否可解？对于任意规格的一组多米诺骨牌，若存在一种算法来帮助判定它是否可解，则我们讲多米诺骨牌问题是「可判定」的。否则是「无法判定」的。

换句话说，多米诺骨牌问题问的是，是否存在一个，对任何多米诺骨牌集，都能正确地解决问题？

1966年，伯杰解决了王氏砖的多米诺骨牌问题，他证明了不存在能够解决该问题的算法。其解法如下：可以将任何图灵机转变成一组密铺整个平面的王氏平铺，当且仅当此图灵机永不停止。而停机问题（测试图灵机是否最终停止的问题）的不可判断性导致了王氏平铺问题的不可判定性。例如，上图中给出的13个图块是由Karel Culik II于1996年出版的非周期集。。 Winfree等已经证明了用DNA制成的分子“砖”的可行性，它与王氏砖有相似之处。米塔尔等人已经证明，这些王氏“砖”可以由肽核酸（PNA）组成，肽核酸是稳定的DNA人工模拟物。

应用
王氏砖已用來做為程序化生成的產生工具，可以用來產生纹理、地形和其他大型和非重复的二维数据集。可以用较便宜的成本，预先计算或手工制作一小组的「源砖」，確認其它们拼貼出的结果不会有太明显的重复，且没有周期性。在这种情况下，传统的非周期性方格排列显示其非常规则的结构。王氏砖程序化生成的限制較少，而且确保可以密铺，并且可以用伪随机的方式选择每块砖。

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

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

参见
*
*
*

TetraVex

参考文献
外部链接

[https://web.archive.org/web/20060830155826/http://www.uwgb.edu/dutchs/symmetry/aperiod.htm Steven Dutch的页面，包括许多非周期性瓷砖的图片]
[http://catseye.tc/installation/Backtracking_Wang_Tiler 一个简单的王氏平铺方法的动画演示] - 需要Javascript和HTML5

评论 (0)