ドミノ問題

ウィキペディア小見出し辞書

ドミノ問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 05:16 UTC 版)

「ワンのタイル」の記事における「ドミノ問題」の解説

ワンは1961年に、あるワンのタイルの有限集合が平面を敷き詰め可能なら、敷き詰める方法のなかに周期的なものが存在すると予想した。すなわち、壁紙の模様のように、2次元格子ベクトルによる並進の下で不変なパターンを作れるということである。ワンはこの予想が、与えられたタイルの有限集合が平面を敷き詰め可能かどうか判別するアルゴリズムの存在を含んでいることにも気付いていた。互いに合致するタイルしか隣同士になれないアイデアはドミノゲームにも通じるため、ワンのタイルはワンのドミノとも呼ばれる。あるタイルの集合が平面を敷き詰められるかを判別するアルゴリズムの問題はドミノ問題として知られるようになった。 ワンの学生だったロバート・バーガー（英語版）は以下のように書いている。 ドミノ問題はドミノの集合すべてからなるクラスを扱っており、それぞれの集合が決定可能かどうかを判別する問題によって構成される。ドミノ問題が「決定可能である」もしくは「決定不能である」というのは、任意のドミノの集合が指定されたときに、それが決定可能であるかどうかを判別するアルゴリズムが存在するかどうかを言っている。 換言すればドミノ問題とは、いかなるドミノの集合が与えられても問題を正しく解決できるような実効的な手順があるかということである。 1966年にバーガーはドミノ問題を否定的に解決した。バーガーはドミノ問題を解くアルゴリズムが存在しないことを証明するために、任意のチューリングマシンをワンのタイルの集合に変換し、なおかつそのチューリングマシンが停止する場合にのみタイルが平面を敷き詰められるようにする方法を示した。チューリングマシンがいずれ停止するかどうかは決定不能な問題（停止性問題）であるため、ワンのタイル問題も決定不能となる。