王氏砖：修订间差异

维基百科，自由的百科全书
下一版本→
删除的内容 添加的内容
可视化wikitext
Kizzard99（留言 | 贡献）
198次编辑
通过翻译页面“Wang tile”创建
（没有差异）

2019年8月13日 (二) 13:07的版本

这组11张瓷砖将平铺在平面上，但只能非周期性贴砖 。

王氏砖 (或 王氏多米诺骨牌)，首先由数学家、逻辑学家和哲学家王浩于1961年提出，是一类形式系统。视觉上，它们是每一边各有一种颜色的正方形瓷砖。选择一组这样的瓷砖，将每一块瓷砖和其它瓷砖由每一边匹配的颜色排列，既不将其旋转也不反射。

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

多米诺骨牌的问题

例：有13个瓷砖的王密鋪。

1961年，王推测，如果一组有限的王氏砖可以平铺平面，那么也存在周期性的平铺 ，即在二维点阵中的矢量转换下不变的平铺，如壁纸图案一般。他还观察到，这个猜想意味着存在一种算法来决定给定的有限的王氏砖是否可以平铺平面。 [1] [2]约束相邻瓷砖相互匹配的想法发生在多米诺骨牌游戏中，所以王氏砖也被称为王氏多米诺骨牌。 [3]确定一组瓷砖是否可以平铺平面的算法问题被称为多米诺骨牌问题 。 [4]

根据王的学生， 罗伯特·伯杰所言,[4]

多米诺骨牌问题涉及类的所有多米诺骨牌组，它包括决定它是否可以被解决。 对于任意规格的一个多米诺骨牌组，我们讲多米诺骨牌问题是可判定 或无法判定的，根据是否存在一种算法将决定它能不能被解决。

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

1966年，王的学生罗伯特·伯杰解决了多米诺骨牌问题。他证明了不存在该问题的算法：可以将任何图灵机转变成一组平铺平面的王氏平铺，当且仅当此图灵机永不停止。停机问题的不可判断性（测试图灵机是否最终停止的问题）则暗示了王氏平铺问题的不可判定性。 [4]

非周期性的瓷砖组

将伯杰的不可判断性结果与王的观察结合起来，推测必须存在一组有限的王瓦片来平铺飞机，但只是非周期性的 。这类似于彭罗斯平铺 ，或准晶体中原子的排列。虽然伯杰的原始集合包含20,426块瓷砖，但他猜测较小的集合是可以的，包括他的集合的子集。在他未发表的博士学位论文中，他将瓷砖数量减少到104个。在后来的几年中，越来越小的瓷砖组被发现。 [5] [6] [7] [8]例如，上图中给出的13个图块是由Karel Culik II于1996年出版的非周期集。 [6]它可以平铺平面，但不能定期平铺。 2015年Emmanuel Jeandel和Michael Rao发现了使用4种颜色的11块瓷砖组，并使用暴力搜索来证明10块瓷砖或3种颜色不足以强制非周期性。 [8]

推广

王氏砖可以以各种方式推广，所有这些都在上述意义上也是不可判定的。例如， 王氏立方体是具有彩色面的相等大小的立方体，并且在任何多边形镶嵌上由每一面的颜色来匹配。 Culik和Kari展示了非周期性的王氏立方体。 [9] Winfree等已经证明了制造由DNA制成的分子“瓷砖”的可行性，它与王氏瓷砖有相似之处。 [10]米塔尔等人已经证明，这些瓷砖也可以由肽核酸 （PNA）组成，这是一种稳定的DNA人工模拟物。 [11]

应用

王氏砖最近已成为一个受欢迎的工具，用于程序性生成的纹理、 对地形和其他大型和非重复的二维的数据集；一小组预先计算或手工制作的源砖可以非常便宜地组装而不会有太明显的重复且没有周期性。在这种情况下，传统的非周期性瓷砖排列将显示其非常规则的结构；对于任何两个给定的侧面颜色，保证至少两个图块选择的约束更少的瓷砖组是常见的，因为容易确保可图块性，并且可以伪随机地选择每个图块。 [12] [13] [14] [15]

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

在流行文化

格雷格·伊根著短篇故事 王氏地毯，后来扩展到小说 海外侨民（Diaspora），描写了一个假设的宇宙，其中有居民生物和智慧生物，体现为由复杂分子模式实现的王氏砖。 [17]

也参看

  • 边缘匹配拼图
  • 永恒II拼图
  • 珀西·亚历山大麦克·马洪
  • TetraVex

参考文献

  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. ^ 4.0 4.1 4.2 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. ^ 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 .
  6. ^ 6.0 6.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 . (Showed an aperiodic set of 13 tiles with 5 colors).
  7. ^ 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 .
  8. ^ 8.0 8.1 Jeandel, Emmanuel; Rao, Michael, An aperiodic set of 11 Wang tiles, CoRR, 2015, Bibcode:2015arXiv150606492J, arXiv:1506.06492 可免费查阅 . (Showed an aperiodic set of 11 tiles with 4 colors)}
  9. ^ Culik, Karel, II; Kari, Jarkko, An aperiodic set of Wang cubes, Journal of Universal Computer Science, 1995, 1 (10): 675–686, MR 1392428, doi:10.1007/978-3-642-80350-5_57 .
  10. ^ 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 .
  11. ^ 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 .
  12. ^ Stam, Jos, Aperiodic Texture Mapping (PDF), 1997 . Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
  13. ^ 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, ISBN 1-58113-709-5, doi:10.1145/1201775.882265 . Introduces stochastic tiling.
  14. ^ 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, ISBN 3-905673-15-0, doi:10.1145/1058129.1058138 . Applies Wang Tiles for real-time texturing on a GPU.
  15. ^ . 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, ISBN 1-59593-364-6, doi:10.1145/1179352.1141916 . Shows advanced applications.
  16. ^ 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 .
  17. ^ Burnham, Karen, Greg Egan, Modern Masters of Science Fiction, University of Illinois Press: 72–73, 2014, ISBN 9780252096297 .

进一步阅读

外部链接

取自“https://zh.wikipedia.org/w/index.php?title=王氏砖&oldid=55636730”