王氏砖

王氏砖（英语：Wang tile）也称为王氏多米诺骨牌，最早由数学家、逻辑学家和哲学家王浩于1961年提出，属于边缘匹配拼图（英语：Edge-matching puzzle），也是形式系统。

这11张王氏砖可以在邻边相互匹配（有相同的颜色）的条件下，非周期性密铺（英语：Aperiodic tiling）整个平面

王氏砖的外观是正方形，正方形的每一边可以有不同的颜色，也可以以各边和中心点组成的三角形来着色，一个王氏砖中里可以有二个至四个不同的颜色。二个王氏砖拼合时，其相邻的边需要有相同的颜色，在王氏砖拼合时，不允许旋转王氏砖，王氏砖也不能翻面。

关于特定一组王氏砖的基本问题是：是否可以用这组王氏砖密铺平面？也就是以符合王氏砖规则的方式填合无限大的平面。下一个问题是是否存在周期性的密铺方式？

多米诺骨牌问题

 
例：由13个王氏砖组成的密铺

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

根据王浩的学生，罗伯特·伯杰（英语：Robert Berger (mathematician)）所言[5]

多米诺骨牌问题指的是，如何判断任何一组多米诺骨牌是否可解？对于任意规格的一组多米诺骨牌，若存在一种算法来帮助判定它是否可解，则我们讲多米诺骨牌问题是“可判定”的。 否则是“无法判定”的。

换句话说，多米诺骨牌问题问的是，是否存在一个有效方法（英语：Effective method），对任何多米诺骨牌集，都能正确地解决问题？

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

非周期性的瓷砖组

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

伯杰在论文中有提到一种非周期性密铺集合，是由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]。

王氏砖也用于细胞自动机理论中决定性问题的证明[17]。

流行文化

澳洲作家格雷格·伊根有一个短篇故事《王氏地毯》，后来扩展为小说《海外侨民（英语：Diaspora (novel)）》（Diaspora），描写了有有居民生物和智慧生物的假想宇宙，这些生物都是由复杂分子模式实现的王氏砖[18]。

参见

参考文献

  1. ^ Wang, Hao, Proving theorems by pattern recognition—II, Bell System Technical Journal, 1961, 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x 
  2. ^ Wang, Hao, Games, logic and computers, Scientific American, November 1965: 98–106 . Presents the domino problem for a popular audience.
  3. ^ Renz, Peter, Mathematical proof: What it is and what it ought to be, The Two-Year College Mathematics Journal, 1981, 12 (2): 83–103, doi:10.2307/3027370 .
  4. ^ Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954 . Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
  5. ^ 5.0 5.1 Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954 . Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
  6. ^ Robinson, Raphael M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 1971, 12: 177–209, Bibcode:1971InMat..12..177R, MR 0297572, doi:10.1007/bf01418780 .
  7. ^ 7.0 7.1 Culik, Karel, II, An aperiodic set of 13 Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 245–251, MR 1417576, doi:10.1016/S0012-365X(96)00118-5 （包括5个颜色的13个王氏砖）
  8. ^ Kari, Jarkko, A small aperiodic set of Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 259–264, MR 1417578, doi:10.1016/0012-365X(95)00120-L .
  9. ^ 9.0 9.1 Jeandel, Emmanuel; Rao, Michael, An aperiodic set of 11 Wang tiles, Computing Research Repository, 2015, Bibcode:2015arXiv150606492J, arXiv:1506.06492   （包括4个颜色的11个王氏砖）}
  10. ^ Culik, Karel, II; Kari, Jarkko, An aperiodic set of Wang cubes, Journal of Universal Computer Science, 1995, 1 (10): 675–686 [2019-08-13], MR 1392428, doi:10.1007/978-3-642-80350-5_57, （原始内容存档于2019-08-13） .
  11. ^ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C., Design and self-assembly of two-dimensional DNA crystals, Nature, 1998, 394: 539–544, Bibcode:1998Natur.394..539W, PMID 9707114, doi:10.1038/28998 
  12. ^ Lukeman, P.; Seeman, N.; Mittal, A., Hybrid PNA/DNA nanosystems, 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii, 2002 .
  13. ^ Stam, Jos, Aperiodic Texture Mapping (PDF), 1997 [2019-08-13], （原始内容 (PDF)存档于2016-04-30） . Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
  14. ^ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver, Wang tiles for image and texture generation, ACM SIGGRAPH 2003 (PDF), New York, NY, USA: ACM: 287–294, 2003 [2019-08-13], ISBN 1-58113-709-5, doi:10.1145/1201775.882265, 原始内容存档于2006-03-18 . Introduces stochastic tiling.
  15. ^ Wei, Li-Yi, Tile-based texture mapping on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM: 55–63, 2004 [2019-08-13], ISBN 3-905673-15-0, doi:10.1145/1058129.1058138, （原始内容存档于2016-05-07） . Applies Wang Tiles for real-time texturing on a GPU.
  16. ^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani, Recursive Wang tiles for real-time blue noise, ACM SIGGRAPH 2006, New York, NY, USA: ACM: 509–518, 2006 [2019-08-13], ISBN 1-59593-364-6, doi:10.1145/1179352.1141916, （原始内容存档于2019-08-18） . Shows advanced applications.
  17. ^ Kari, Jarkko, Reversibility of 2D cellular automata is undecidable, Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena 45 (1-3): 379–385, 1990, Bibcode:1990PhyD...45..379K, MR 1094882, doi:10.1016/0167-2789(90)90195-U .
  18. ^ Burnham, Karen, Greg Egan, Modern Masters of Science Fiction, University of Illinois Press: 72–73, 2014, ISBN 9780252096297 

外部链接

延伸阅读

  • Grünbaum, Branko; Shephard, G. C., Tilings and Patterns, New York: W. H. Freeman, 1987, ISBN 0-7167-1193-1