ワンのタイル
ワンのタイル（英: Wang tiles, Wang dominoes,中: 王氏砖）とは、数学者、論理学者、哲学者であったハオ・ワン（王浩）が1961年に始めて提案した一種の形式体系である。視覚的には辺ごとに色付けされた正方形タイルとしてモデル化される。数種のタイルからなる集合を選び、隣り合う辺の色が一致するようにタイルのコピーを並べていく。このときタイルを回転・鏡映させてはいけない。
あるタイルの集合が与えられたとき、それが平面を敷き詰めることができるか、つまり上記のルールに沿って無限平面を埋め尽くすことができるかどうかが基本の問題である。その次には周期的なパターンで敷き詰められるかが問題になる。
ドミノ問題
[編集]
ワンは1961年に、あるワンのタイルの有限集合が平面を敷き詰め可能なら、敷き詰める方法のなかに周期的なものが存在すると予想した。すなわち、壁紙の模様のように、2次元格子ベクトルによる並進の下で不変なパターンを作れるということである。ワンはこの予想が、与えられたタイルの有限集合が平面を敷き詰め可能かどうか判別するアルゴリズムの存在を含んでいることにも気付いていた[1][2]。互いに合致するタイルしか隣同士になれないアイデアはドミノゲームにも通じるため、ワンのタイルはワンのドミノとも呼ばれる[3]。あるタイルの集合が平面を敷き詰められるかを判別するアルゴリズムの問題はドミノ問題として知られるようになった[4]。
ワンの学生だったロバート・バーガーは以下のように書いている[4]。
ドミノ問題はドミノの集合すべてからなるクラスを扱っており、それぞれの集合が決定可能かどうかを判別する問題によって構成される。ドミノ問題が「決定可能である」もしくは「決定不能である」というのは、任意のドミノの集合が指定されたときに、それが決定可能であるかどうかを判別するアルゴリズムが存在するかどうかを言っている。
換言すればドミノ問題とは、いかなるドミノの集合が与えられても問題を正しく解決できるような実効的な手順があるかということである。
1966年にバーガーはドミノ問題を否定的に解決した。バーガーはドミノ問題を解くアルゴリズムが存在しないことを証明するために、任意のチューリングマシンをワンのタイルの集合に変換し、なおかつそのチューリングマシンが停止する場合にのみタイルが平面を敷き詰められるようにする方法を示した。チューリングマシンがいずれ停止するかどうかは決定不能な問題（停止性問題）であるため、ワンのタイル問題も決定不能となる[4]。
非周期的なタイルの集合
[編集]バーガーが証明した決定不能性とワンの観察を組み合わせると、ワンのタイルの有限集合の中には、平面を敷き詰めることはできるが非周期的にしか行えないものが存在すると言える。これはペンローズ・タイルや準結晶中の原子配列に似ている。1966年にバーガーが提示した最初のその種の集合には20,426種のタイルが含まれていたが[4]、彼はもっと小さい集合、たとえばその集合の部分集合でも同じ性質を持ちうると考えていた。バーガーは未刊行の博士論文でタイルの数を104にまで減らした。後年にはより小さい集合が次々に発見されていった[5][6][7][8]。例として、前節の図に示す13タイルの集合はカレル・クーリックII世が1996年に発表した非周期的な集合である[6]。この集合は平面を敷き詰め可能だが、周期的な敷き詰めは行えない。エマニュエル・ジャンデルとマイケル・ラオは2015年にそれより小さい4色11種のタイルからなる集合を発見した。ジャンデルらは全数検索によりタイル10種もしくは3色では非周期的敷き詰めを実現するには不十分だと証明した[8]。
一般化
[編集]ワンのタイルを一般化する方法はさまざまだが、それらはすべて前述の意味で決定不能である。辺の色を一致させるルールはいかなる多角形敷き詰めにも適用できる。「ワンの立方体」は面が色づけされた大きさ一定の立方体である。クーリックとカリは非周期的なワンの立方体の集合が存在することを示した[9]。
ウィンフリーらはデオキシリボ核酸 (DNA) で作られた分子の「タイル」をワンのタイルとして機能させられることを実証した[10]。ミッタルらはDNAの安定な人工代替物であるペプチド核酸 (PNA) でもワンのタイルを構築できることを示した[11]。
応用
[編集]ワンのタイルはテクスチャや高さ場などの大規模な非反復2次元データセットを自動生成するツールとして広まってきている。あらかじめ計算もしくは自作した少数のソース・タイルをアセンブルする方法は安価であり、あからさまな繰り返しは生じず周期性もない。このような問題では、従来の非周期的タイリングでは構造に規則性が強く現れてしまうことになる。それよりも制約を減らして、2辺の色の任意の組み合わせに対してタイルの選択肢が少なくとも2つあるような集合が一般的に使われる。この種の集合では敷き詰め可能性が保障されており、各タイルを疑似的に無作為に選ぶことが可能になるためである[12][13][14][15]。
ワンのタイルはセル・オートマトン理論における決定可能性の証明にも使用されている[16]。
大衆文化における描写
[編集]グレッグ・イーガンの長編SF小説『ディアスポラ』の下敷きとなった短編「ワンの絨毯[† 1]」では、ワンのタイルと同じ数学的な構造を持つ複雑な高分子パターンの中に、知性生命体を備えた一つの宇宙が内包される[17]。
関連項目
[編集]脚注
[編集]注釈
[編集]- ^ "Wang's Carpets", 『プランク・ダイヴ』（2011年、早川書房）収録
出典
[編集]- ^ Wang, Hao (1961), “Proving theorems by pattern recognition—II”, Bell System Technical Journal 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x. Wang proposes his tiles, and conjectures that there are no aperiodic sets.
- ^ Wang, Hao (November 1965), “Games, logic and computers”, Scientific American: 98–106. Presents the domino problem for a popular audience.
- ^ Renz, Peter (1981), “Mathematical proof: What it is and what it ought to be”, The Two-Year College Mathematics Journal 12 (2): 83–103, doi:10.2307/3027370.
- ^ a b c d Berger, Robert (1966), “The undecidability of the domino problem”, Memoirs of the American Mathematical Society 66: 72, MR0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
- ^ Robinson, Raphael M. (1971), “Undecidability and nonperiodicity for tilings of the plane”, Inventiones Mathematicae 12: 177–209, Bibcode: 1971InMat..12..177R, doi:10.1007/bf01418780, MR0297572.
- ^ a b Culik, Karel, II (1996), “An aperiodic set of 13 Wang tiles”, Discrete Mathematics 160 (1-3): 245–251, doi:10.1016/S0012-365X(96)00118-5, MR1417576. (Showed an aperiodic set of 13 tiles with 5 colors).
- ^ Kari, Jarkko (1996), “A small aperiodic set of Wang tiles”, Discrete Mathematics 160 (1-3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR1417578.
- ^ a b Jeandel, Emmanuel; Rao, Michael (2015), “An aperiodic set of 11 Wang tiles”, CoRR, arXiv:1506.06492, Bibcode: 2015arXiv150606492J. (Showed an aperiodic set of 11 tiles with 4 colors)}
- ^ Culik, Karel, II; Kari, Jarkko (1995), “An aperiodic set of Wang cubes”, Journal of Universal Computer Science 1 (10): 675–686, doi:10.1007/978-3-642-80350-5_57, MR1392428.
- ^ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), “Design and self-assembly of two-dimensional DNA crystals”, Nature 394: 539–544, Bibcode: 1998Natur.394..539W, doi:10.1038/28998, PMID 9707114.
- ^ Lukeman, P.; Seeman, N.; Mittal, A. (2002), “Hybrid PNA/DNA nanosystems”, 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.
- ^ Stam, Jos (1997), Aperiodic Texture Mapping. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
- ^ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), “Wang tiles for image and texture generation”, ACM SIGGRAPH 2003, New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN 1-58113-709-5. Introduces stochastic tiling.
- ^ Wei, Li-Yi (2004), “Tile-based texture mapping on graphics hardware”, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55–63, doi:10.1145/1058129.1058138, ISBN 3-905673-15-0. Applies Wang Tiles for real-time texturing on a GPU.
- ^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), “Recursive Wang tiles for real-time blue noise”, ACM SIGGRAPH 2006, New York, NY, USA: ACM, pp. 509–518, doi:10.1145/1179352.1141916, ISBN 1-59593-364-6. Shows advanced applications.
- ^ Kari, Jarkko (1990), “Reversibility of 2D cellular automata is undecidable”, Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, 45, pp. 379–385, Bibcode: 1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U, MR1094882.
- ^ Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297.
関連文献
[編集]- Grünbaum, Branko; Shephard, G. C. (1987), Tilings and Patterns, New York: W. H. Freeman, ISBN 0-7167-1193-1.
外部リンク
[編集]
- ワンのタイルの原始的な敷き詰め方を示したアニメーション - （JavascriptとHTML5が必要）