# 王氏砖

## 多米诺骨牌问题

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

## 参考文献

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. 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. 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. Jeandel, Emmanuel; Rao, Michael, An aperiodic set of 11 Wang tiles, Computing Research Repository, 2015, Bibcode:2015arXiv150606492J, （包括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