Loading article…
王牌（または王ドミノ）は、数学者、論理学者、哲学者である王浩が1961年に初めて提唱した形式体系の一種である。これらは、各面に色が付けられた正方形のタイルによって視覚的にモデル化される。そのようなタイルのセットが選択され、タイルを回転させたり反転させたりすることなく、同じ色のタイルを横に並べて配置される。
ワンタイルの集合に関する基本的な問題は、それが平面を敷き詰めることができるかどうか、つまり、無限平面全体をこの方法で埋め尽くすことができるかどうかである。次の問題は、これを周期的なパターンで行うことができるかどうかである。
1961年、Wangは、有限個のWangタイルで平面をタイル張りできるならば、周期的なタイル張りも存在すると推測した。周期的なタイル張りとは、数学的には、2次元格子内のベクトルによる平行移動に対して不変なタイル張りのことである。これは、壁紙のパターンにおける周期的なタイル張りに似ており、全体のパターンはより小さなパターンの繰り返しである。彼はまた、この推測は、与えられた有限個のWangタイルで平面をタイル張りできるかどうかを判定するアルゴリズムの存在を意味するとも指摘した。[ 1 ] [ 2 ]隣接するタイル同士を一致させるという制約はドミノゲームに見られるため、WangタイルはWangドミノとも呼ばれる。[ 3 ]タイルセットで平面をタイル張りできるかどうかを判定するアルゴリズムの問題は、ドミノ問題として知られるようになった。[ 4 ]
ドミノ問題は、あらゆるドミノセットのクラスを扱います。この問題は、各ドミノセットが解けるかどうかを判定することから成ります。ドミノ問題が判定可能か判定不可能かは、任意のドミノセットの仕様が与えられたときに、そのセットが解けるかどうかを判定するアルゴリズムが存在するか否かによって決まります。
言い換えれば、ドミノ問題とは、与えられたすべてのドミノの組み合わせに対して、問題を正しく解決する効果的な手順が存在するかどうかを問うものである。
1966年、ベルガーはドミノ問題を否定的に解決した。彼は、チューリングマシンが停止しない場合に限り、任意のチューリングマシンを平面をタイル張りするワンタイルの集合に変換する方法を示すことで、この問題に対するアルゴリズムは存在しないことを証明した。停止問題（チューリングマシンが最終的に停止するかどうかをテストする問題）の決定不能性は、ワンのタイル張り問題の決定不能性を意味する。[ 4 ]
ベルガーの決定不能性の結果とワンの観察を組み合わせると、平面をタイル張りする有限個のワンタイルが存在するが、それは非周期的である必要があることがわかる。これはペンローズタイル張り、または準結晶における原子の配置に似ている。ベルガーの元のセットには 20,426 個のタイルが含まれていたが、彼は自分のセットの部分集合を含むより小さなセットが機能すると推測し、未発表の博士論文でタイルの数を 104 個に減らした。その後、さらに小さなセットが発見された。[ 5 ] [ 6 ] [ 7 ] [ 8 ]例えば、13 個の非周期タイルのセットは、1996 年にカレル・クリク 2 世によって発表された。[ 6 ]
最小の非周期タイルセットは、2015年にエマニュエル・ジャンデルとマイケル・ラオによって発見され、11個のタイルと4つの色で構成されていた。彼らは、10個のタイルまたは3つの色では非周期性を強制するには不十分であることを証明するために、徹底的なコンピュータ探索を使用した。[ 8 ]
ワンタイルはさまざまな方法で一般化できますが、それらはすべて上記の意味で決定不能です。たとえば、ワンキューブは色付きの面を持つ同じサイズの立方体で、側面の色は任意の多角形テセレーションで一致させることができます。Culik と Kari は、ワンキューブの非周期セットを実証しました。[ 9 ] Winfree らは、ワンタイルとして機能するDNA (デオキシリボ核酸) から作られた分子「タイル」の作成の実現可能性を実証しました。 [ 10 ] Mittal らは、これらのタイルは、DNA の安定した人工模倣物であるペプチド核酸(PNA)で構成することもできることを示しました。 [ 11 ]
Wang タイルは、テクスチャ、ハイトフィールド、その他の大規模で繰り返しのない 2 次元データセットの手続き的合成に使用されています。事前に計算された、または手作りのソース タイルの小さなセットは、あまり明白な繰り返しや周期性なしに非常に安価に組み立てることができます。この場合、従来の非周期的なタイリングは非常に規則的な構造を示します。任意の 2 つのサイド カラーに対して少なくとも 2 つのタイル選択を保証する制約の少ないセットが一般的です。これは、タイリング可能性が容易に保証され、各タイルを擬似ランダムに選択できるためです。[ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]
ワンタイルはセルオートマトン理論の決定可能性証明にも使用されている。[ 17 ]
グレッグ・イーガンによる短編小説「王の絨毯」（後に小説『ディアスポラ』に拡張）は、複雑な分子のパターンによって具現化された王のタイルとして具現化された、居住する生物や知的な存在を含む宇宙を想定している。[ 18 ]