ワンのタイル
From Wikipedia, the free encyclopedia
ワンのタイル（英: 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]。
一般化
応用
ワンのタイルはテクスチャや高さ場などの大規模な非反復2次元データセットを自動生成するツールとして広まってきている。あらかじめ計算もしくは自作した少数のソース・タイルをアセンブルする方法は安価であり、あからさまな繰り返しは生じず周期性もない。このような問題では、従来の非周期的タイリングでは構造に規則性が強く現れてしまうことになる。それよりも制約を減らして、2辺の色の任意の組み合わせに対してタイルの選択肢が少なくとも2つあるような集合が一般的に使われる。この種の集合では敷き詰め可能性が保障されており、各タイルを疑似的に無作為に選ぶことが可能になるためである[12][13][14][15]。
ワンのタイルはセル・オートマトン理論における決定可能性の証明にも使用されている[16]。
