跳转到内容

王氏砖

维基百科，自由的百科全书
这11张王氏砖可以在邻边相互匹配（有相同的顏色）的條件下，非周期性密鋪（英语：Aperiodic tiling）整個平面

王氏砖（英語：Wang tile）也稱為王氏多米诺骨牌，最早由美籍華裔数学家、逻辑学家和哲学家王浩于1961年提出，屬於边缘匹配拼图（英语：Edge-matching puzzle），也是形式系統。

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

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

多米诺骨牌问题

例：由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 
检索自“https://zh.wikipedia.org/w/index.php?title=王氏砖&oldid=77192140”