Loading article…
ウィキメディア・コモンズには、王牌に関連するメディアがあります。
王牌（または王ドミノ）は、数学者、論理学者、哲学者である王浩が1961年に初めて提唱した形式体系の一種です。各面に色が付いた正方形のタイルで視覚的にモデル化されます。このようなタイルのセットが選択され、タイルのコピーが回転または反転されることなく、色が一致するように横に並べられます。
王タイルのセットに関する基本的な疑問は、平面をタイルで埋めることができるかどうか、つまり、無限平面全体をこの方法で埋めることができるかどうかです。次の疑問は、これを周期的なパターンで実行できるかどうかです。
ドミノ問題
1961年、ワンは、有限のワンタイルの集合が平面を敷き詰めることができるなら、周期的な敷き詰めも存在すると予想した。これは数学的には、2次元格子のベクトルによる変換に対して不変な敷き詰めである。これは壁紙のパターンにおける周期的な敷き詰めに例えることができ、全体のパターンはより小さなパターンの繰り返しである。彼はまた、この予想は、与えられた有限のワンタイルの集合が平面を敷き詰めることができるかどうかを決定するアルゴリズムの存在を意味するだろうと観察した。[1] [2]隣接するタイルが互いに一致するように制約するというアイデアはドミノゲームで登場するため、ワンタイルはワンドミノとも呼ばれる。[3]タイルセットが平面を敷き詰めることができるかどうかを判断するアルゴリズムの問題は、ドミノ問題として知られるようになった。[4]
王の弟子ロバート・バーガーによれば、[4]
ドミノ問題は、すべてのドミノ セットのクラスを扱います。これは、各ドミノ セットが解決可能かどうかを判断することから成ります。任意のドミノ セットの仕様が与えられたときに、そのセットが解決可能かどうかを判断するアルゴリズムが存在するかどうかによって、ドミノ問題が決定可能か決定不可能かを判断します。
言い換えれば、ドミノ問題は、与えられたすべてのドミノ セットに対して問題を正しく解決する 効果的な手順があるかどうかを問うものです。
1966年、バーガーはドミノ問題を否定的に解いた。彼は、チューリングマシンが停止しない場合にのみ、平面をタイル張りするワンタイルのセットにチューリングマシンを変換する方法を示し、この問題に対するアルゴリズムは存在しないことを証明した。停止問題（チューリングマシンが最終的に停止するかどうかをテストする問題）の決定不能性は、ワンのタイル張り問題の決定不能性を意味する。[4]
非周期的なタイルのセット
バーガーの決定不能性の結果とワンの観察を組み合わせると、平面をタイル張りするワンタイルの有限集合が存在するが、非周期的である必要があることが示される。これはペンローズのタイル張り、または準結晶内の原子の配置に似ている。バーガーの元の集合には20,426個のタイルが含まれていたが、彼は集合のサブセットを含むより小さな集合でも機能すると推測し、未発表の博士論文でタイルの数を104個に減らした。後年、さらに小さな集合が発見された。[5] [6] [7] [8]たとえば、1996年にカレル・クリク2世によって13個の非周期タイルの集合が発表された。[6]
非周期タイルの最小セットは、2015年にエマニュエル・ジャンデルとマイケル・ラオによって発見され、11個のタイルと4色のものでした。彼らは徹底的なコンピューター検索を使用して、10個のタイルまたは3色では非周期性を強制するには不十分であることを証明しました。[8]上記のタイトル画像に示されているこのセットは、File:Wang 11 tiles.svgでさらに詳しく調べることができます。
一般化
ワングタイルは様々な方法で一般化できるが、そのどれもが上記の意味では決定不可能である。例えば、ワングキューブは、任意の多角形タイル分割で側面の色を一致させることができる、色付きの面を持つ同じサイズの立方体である。CulikとKariは、ワングキューブの非周期的な集合を実証した。 [9] Winfreeらは、ワングタイルとして機能するDNA （デオキシリボ核酸）から作られた分子「タイル」の作成の実現可能性を実証した。 [10] Mittalらは、これらのタイルがDNAの安定した人工模倣物であるペプチド核酸（PNA）で構成できることを示した。 [11]
アプリケーション
ワンタイルは、テクスチャ、ハイトフィールド、その他の大規模で反復のない2次元データセットの手続き型合成に使用されています。事前計算済みまたは手作りのソースタイルの小さなセットは、あまり目立たない反復や周期性なしに、非常に安価に組み立てることができます。この場合、従来の非周期的なタイリングは非常に規則的な構造を示します。タイリング可能性が簡単に保証され、各タイルを疑似ランダムに選択できるため、任意の2つのサイドカラーに対して少なくとも2つのタイルの選択肢を保証する制約の少ないセットが一般的です。[12] [13] [14] [15] [16]
王タイルはセルオートマトン理論の 決定可能性証明にも使用されている。 [17]
大衆文化において
グレッグ・イーガンによる短編小説「ワングのカーペット」（後に小説『ディアスポラ』に拡張）では、複雑な分子のパターンによって実現されたワングタイルとして具現化された、常在生物と知的生命体を備えた宇宙が想定されている。[18]
参照
参考文献
- ^ 王昊(1961)、「パターン認識による定理の証明—II」、ベルシステム技術ジャーナル、40 (1): 1–41、doi :10.1002/j.1538-7305.1961.tb03975.x王は自身のタイルを提案し、非周期的な集合は存在しないと推測しています。
- ^ ワン・ハオ（1965年11月）「ゲーム、ロジック、コンピュータ」、サイエンティフィック・アメリカン、213（5）：98–106、doi：10.1038/scientificamerican1165-98ドミノ問題を一般の聴衆に提示します。
- ^ レンツ、ピーター（1981）「数学的証明：それが何であるか、そしてそれが何であるべきか」、2年制大学数学ジャーナル、12（2）：83–103、doi：10.2307 / 3027370、JSTOR 3027370。
- ^ abc Berger, Robert (1966)、「ドミノ問題の決定不可能性」、アメリカ数学会誌、66 :72、MR 0216954バーガーは「ワンタイル」という用語を作り出し、その最初の非周期的な集合を実証しました。
- ^ ロビンソン、ラファエル M. (1971)、「平面のタイリングの決定不能性と非周期性」、Inventiones Mathematicae、12 (3): 177–209、Bibcode :1971InMat..12..177R、doi :10.1007/bf01418780、MR 0297572、S2CID 14259496。
- ^ ab Culik, Karel II (1996)、「13 個の Wang タイルの非周期的集合」、離散数学、160 (1–3): 245–251、doi : 10.1016/S0012-365X(96)00118-5、MR 1417576（5 色の 13 個のタイルの非周期的なセットを示しました。）
- ^ カリ、ヤルッコ(1996)、「ワンタイルの小さな非周期的集合」、離散数学、160 (1–3): 259–264、doi : 10.1016/0012-365X(95)00120-L、MR 1417578。
- ^ ab Jeandel, Emmanuel; Rao, Michaël (2021)、「11 個の Wang タイルの非周期的セット」、Advances in Combinatorics : 1:1–1:37、arXiv : 1506.06492、doi :10.19086/aic.18614、MR 4210631、S2CID 13261182（4 色の 11 個のタイルの非周期的なセットを示し、タイルの数や色が少ない場合は非周期的にならないことを証明しました。）
- ^ Culik, Karel II; Kari, Jarkko (1995)、「Wang キューブの非周期的集合」、Journal of Universal Computer Science、1 (10): 675–686、doi :10.1007/978-3-642-80350-5_57、MR 1392428。
- ^ Winfree, E.; Liu, F.; Wenzler, LA; Seeman, NC (1998)、「2次元DNA結晶の設計と自己組織化」、Nature、394 (6693): 539–544、Bibcode :1998Natur.394..539W、doi :10.1038/28998、PMID 9707114、S2CID 4385579。
- ^ Lukeman, P.; Seeman, N.; Mittal, A. (2002)、「ハイブリッド PNA/DNA ナノシステム」、第 1 回ナノスケール/分子力学国際会議 (N-M2-I)、アウトリガー ワイレア リゾート、マウイ島、ハワイ。
- ^ Stam, Jos (1997)、非周期テクスチャマッピング(PDF)決定論的な置換システムを使用して、テクスチャのバリエーションに Wang タイルを使用するというアイデアを紹介します。
- ^ Neyret, Fabrice; Cani, Marie-Paule (1999)、「パターンベースのテクスチャリングの再考」、第 26 回コンピュータ グラフィックスおよびインタラクティブ技術に関する年次会議の議事録 - SIGGRAPH '99 (PDF)、ロサンゼルス、米国: ACM、pp. 235–242、doi :10.1145/311535.311561、ISBN 0-201-48560-5、S2CID 11247905確率的タイリングを導入します。
- ^ Cohen, Michael F. ; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003)、「画像とテクスチャ生成のための Wang タイル」、ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 (PDF)、ニューヨーク、ニューヨーク、米国: ACM、pp. 287–294、doi :10.1145/1201775.882265、ISBN 1-58113-709-5、S2CID 207162102、2006-03-18に オリジナル（PDF）からアーカイブ。
- ^ Wei, Li-Yi (2004)、「グラフィックス ハードウェア上のタイル ベースのテクスチャ マッピング」、ACM SIGGRAPH/EUROGRAPHICS グラフィックス ハードウェア カンファレンス (HWWS '04) の議事録、ニューヨーク、ニューヨーク、米国: ACM、pp. 55–63、doi :10.1145/1058129.1058138、ISBN 3-905673-15-0、S2CID 53224612GPU 上でリアルタイムのテクスチャリングを行うために Wang Tiles を適用します。
- ^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006)、「リアルタイム ブルー ノイズ用再帰 Wang タイル」、ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06、ニューヨーク、NY、米国: ACM、pp. 509–518、doi :10.1145/1179352.1141916、ISBN 1-59593-364-6、S2CID 11007853高度なアプリケーションを表示します。
- ^ Kari, Jarkko (1990)、「2D セルラーオートマトン可逆性は決定不能」、セルラーオートマトン: 理論と実験 (Los Alamos, NM, 1989)、Physica D: 非線形現象、vol. 45、pp. 379–385、Bibcode :1990PhyD...45..379K、doi :10.1016/0167-2789(90)90195-U、MR 1094882。
- ^ バーナム、カレン（2014）、グレッグ・イーガン、現代のSFの巨匠、イリノイ大学出版局、pp. 72-73、ISBN 978-0-252-09629-7。
さらに読む
- グリュンバウム、ブランコ、シェパード、GC（1987）、タイルとパターン、ニューヨーク：WHフリーマン、ISBN 0-7167-1193-1。
外部リンク
- スティーブン・ダッチのページには、非周期的なタイルの写真が多数掲載されています。
- 単純な Wang タイル法のアニメーション デモ - Javascript と HTML5 が必要です