热门问题
时间线
聊天
视角
王氏砖
来自维基百科，自由的百科全书
Remove ads
王氏砖（英语：Wang tile）也称为王氏多米诺骨牌，最早由美籍华裔数学家、逻辑学家和哲学家王浩于1961年提出，属于边缘匹配拼图，也是形式系统。
王氏砖的外观是正方形，正方形的每一边可以有不同的颜色，也可以以各边和中心点组成的三角形来着色，一个王氏砖中里可以有二个至四个不同的颜色。二个王氏砖拼合时，其相邻的边需要有相同的颜色，在王氏砖拼合时，不允许旋转王氏砖，王氏砖也不能翻面。
关于特定一组王氏砖的基本问题是：是否可以用这组王氏砖密铺平面？也就是以符合王氏砖规则的方式填合无限大的平面。下一个问题是是否存在周期性的密铺方式？
多米诺骨牌问题
王浩于1961年提出猜想，如果一组有限多个的王氏砖可以在邻边相互匹配的条件下，密铺整个平面，那么也存在针对这组王氏砖的周期性密铺铺法，也就是说这种铺法在二维点阵中的矢量平移转换下不变，就如壁纸图案一般。他还观察到，若这个猜想成立意味着有一种算法，可以用来判断任何一组有限多个的王氏砖是否可以密铺整个平面[1] [2]。将瓷砖按照相邻边相互匹配的想法见于多米诺骨牌游戏中，所以王氏砖也被称为王氏多米诺骨牌。 [3]判断一组骨牌是否可以平铺整个平面的算法问题被称为多米诺骨牌问题[4] 。
根据王浩的学生，罗伯特·伯杰所言[5]
多米诺骨牌问题指的是，如何判断任何一组多米诺骨牌是否可解？对于任意规格的一组多米诺骨牌，若存在一种算法来帮助判定它是否可解，则我们讲多米诺骨牌问题是“可判定”的。 否则是“无法判定”的。
换句话说，多米诺骨牌问题问的是，是否存在一个有效方法，对任何多米诺骨牌集，都能正确地解决问题？
1966年，伯杰解决了王氏砖的多米诺骨牌问题，他证明了不存在能够解决该问题的算法。其解法如下：可以将任何图灵机转变成一组密铺整个平面的王氏平铺，当且仅当此图灵机永不停止。而停机问题（测试图灵机是否最终停止的问题）的不可判断性导致了王氏平铺问题的不可判定性[5]。
Remove ads
非周期性的瓷砖组
结合王浩的观察以及伯杰的不可判断性结果，可以推测存在一组有限多个的王氏砖，可以密铺整个二维平面，但只能非周期性密铺。此密铺类似彭罗斯平铺，或准晶体中原子的排列。
伯杰在论文中有提到一种非周期性密铺集合，是由20,426块王氏砖组合，但他猜测也可能存在只能非周期性密铺的较小集合。伯杰发表的博士学位论文中有提到数量较少（104个）的王氏砖。在后来的几年中，又发现了越来越少的王氏砖组[6] [7] [8] [9]。例如，上图中给出的13个图块是由Karel Culik II于1996年出版的非周期集。[7]它可以密铺二维平面，但不能周期性密铺。2015年Emmanuel Jeandel和Michael Rao发现了使用4种颜色的11块非周期性密铺集合，并使用暴力搜索来确定，若减到10块王氏砖或是只有3种颜色，都不足以强制非周期性[9]。
扩展
王氏砖可以扩展为其他的形式，而许多相关的问题也是不可判定的。例如，王氏立方体（Wang cubes）是具有彩色面的正立方体，相对的面拼合时需要有相同的颜色。Culik和Kari展示了非周期性的王氏立方体[10]。 Winfree等已经证明了用DNA制成的分子“砖”的可行性，它与王氏砖有相似之处[11]。米塔尔等人已经证明，这些王氏“砖”可以由肽核酸 （PNA）组成，肽核酸是稳定的DNA人工模拟物[12]。
应用
王氏砖已用来做为程序化生成的产生工具，可以用来产生纹理、地形和其他大型和非重复的二维数据集。可以用较便宜的成本，预先计算或手工制作一小组的“源砖”，确认其它们拼贴出的结果不会有太明显的重复，且没有周期性。在这种情况下，传统的非周期性方格排列显示其非常规则的结构。王氏砖程序化生成的限制较少，而且确保可以密铺，并且可以用伪随机的方式选择每块砖 [13] [14] [15] [16]。
流行文化
澳洲作家格雷格·伊根有一个短篇故事《王氏地毯》，后来扩展为小说《海外侨民》（Diaspora），描写了有有居民生物和智慧生物的假想宇宙，这些生物都是由复杂分子模式实现的王氏砖[18]。
参见
- 边缘匹配拼图
- 永恒II拼图
- 珀西·亚历山大麦克·马洪
- TetraVex
参考文献
外部链接
延伸阅读
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads