王氏砖

维基共享资源中有与王氏砖相关的媒体。

王氏砖（或王氏多米诺骨牌）是一类形式系统，由数学家、逻辑学家和哲学家王浩于 1961 年首先提出。 它们在视觉上由方形瓷砖建模，每边都有一种颜色。 选择一组这样的图块，并以匹配的颜色并排排列图块的副本，而不旋转或反射它们。

一组王氏砖的基本问题是它是否可以平铺平面，即是否可以这样填充整个无限平面。 下一个问题是这是否可以以周期性模式完成。

1961 年，Wang 猜想如果有限的王氏砌块集可以平铺平面，则还存在周期性平铺，从数学上讲，这种平铺在二维点阵中的向量平移下是不变的。 这可以比作墙纸图案中的周期性平铺，其中整体图案是一些较小图案的重复。 他还观察到，这个猜想意味着存在一种算法来决定给定的有限王氏砖集是否可以平铺平面。 限制相邻牌相互匹配的想法出现在多米诺骨牌游戏中，因此王氏砖也被称为王骨牌。 确定一个图块集是否可以平铺平面的算法问题被称为多米诺骨牌问题。

根据 Wang 的学生 Robert Berger 的说法，

多米诺骨牌问题处理所有多米诺骨牌集合的类别。 它包括为每个多米诺骨牌组决定它是否可以解决。 我们说多米诺骨牌问题是可判定的或不可判定的，取决于是否存在一种算法，该算法在给定任意多米诺骨牌集合的规范的情况下，将决定该集合是否可解。

换句话说，多米诺骨牌问题询问是否有一个有效的程序可以正确解决所有给定的多米诺骨牌集的问题。

1966年，伯杰反面解决了多米诺骨牌问题。 他通过展示如何将任何图灵机转换为一组当且仅当图灵机不停止时平铺平面的王氏砖，证明了不存在解决该问题的算法。 停机问题（测试图灵机是否最终停机的问题）的不可判定性暗示了 Wang 的拼贴问题的不可判定性。

将 Berger 的不可判定性结果与 Wang 的观察相结合表明，必须存在一个有限的王氏砖集来平铺平面，但只是非周期性的。 这类似于彭罗斯平铺，或准晶体中的原子排列。 尽管 Berger 的原始集合包含 20,426 个图块，但他推测更小的集合也可以工作，包括他的集合的子集，并且在他未发表的博士论文中。 在他的论文中，他将瓷砖的数量减少到 104。在后来的几年里，发现了越来越小的瓷砖。 例如，Karel Culik II 于 1996 年发表了一组 13 个非周期性方块。

Emmanuel Jeandel 和 Michael Rao 在 2015 年发现了最小的一组非周期性瓷砖，有 11 块瓷砖和 4 种颜色。 他们使用详尽的计算机搜索来证明 10 个图块或 3 种颜色不足以强制非周期性。 上面标题图片中显示的这个集合可以在 File:Wang 11 tiles.svg 中更仔细地检查。

王氏砖可以用多种方式概括，所有这些在上述意义上也是不可判定的。 例如，Wang 立方体是具有彩色面和侧面颜色的等尺寸立方体，可以在任何多边形镶嵌上匹配。Culik 和 Kari 展示了 Wang 立方体的非周期性集合。 温弗里等人。 已经证明了创建由 DNA（脱氧核糖核酸）制成的分子瓦片的可行性，这些分子瓦片可以充当王氏砖。 米塔尔等。 已经表明，这些瓷砖也可以由肽核酸 (PNA) 组成，这是一种稳定的 DNA 人工模拟物。

王氏砖已被用于纹理、高度场和其他大型非重复二维数据集的程序合成； 一小组预先计算或手工制作的源图块可以非常便宜地组装起来，没有太明显的重复和周期性。在这种情况下，传统的非周期性图块将显示出非常规则的结构； 更少的约束集保证对任何两个给定的边颜色至少有两个瓷砖选择是常见的，因为很容易确保瓷砖的可用性，并且可以伪随机地选择每个瓷砖。

王氏砖也被用于元胞自动机理论的可判定性证明。

短篇小说王的地毯，后来扩展为格雷格·伊根的小说散居地，假设一个宇宙，完整的常驻生物体和智能生物，体现为复杂分子模式实现的王氏砖。