Dlaždice Wang (nebo Wang domino ), které poprvé navrhl matematik, logik a filozof Hao Wang v roce 1961, jsou třídou formálních systémů . Jsou vizuálně modelovány pomocí čtvercových dlaždic s probarvením na každé straně. Definuje se sada takových dlaždic (např. jako na obrázku), poté se na sebe nanesou kopie těchto dlaždic s podmínkou shody barev stran, ale bez rotace nebo symetrického odrazu dlaždic.
Hlavní otázkou u Vanovy sady dlaždic je, zda dokážou obložit rovinu nebo ne, tedy zda lze rovinu takto vyplnit. Další otázkou je, zda může být vyplněna v periodickém vzoru.
V roce 1961 Wang předpokládal, že pokud konečný počet Wangových dlaždic může obložit rovinu, pak existuje periodická dlažba , tedy dlaždice, která je invariantní při překladu vektory ve dvourozměrné mřížce jako tapeta. Poznamenal také, že tato domněnka implikuje existenci algoritmu, který určuje, zda daná konečná sada Wangových dlaždic může obložit rovinu [1] [2] . Myšlenka omezení spojení sousedních destiček vznikla ve hře domino , takže destičky Wang jsou také známé jako Wangova domina [3] a algoritmický problém určení, zda destičky mohou položit letadlo, je známý jako problém domino [ 3] 4] .
Podle studenta Van Roberta Bergera [4] ,
Problém domino se zabývá třídou všech sad domino. Úkolem je určit pro každou sadu domino, zda je možné pokládat dlaždice. Říkáme, že problém Domino je rozhodnutelný nebo nerozhodnutelný , v závislosti na tom, zda existuje nebo neexistuje algoritmus, který při dané sadě libovolné množiny domino určuje, zda je problém s dlaždicemi pro tuto množinu rozhodnoutelný nebo ne.
Jinými slovy, problém domino se ptá, zda existuje účinná metoda , která správně řeší problém pro dané sady domino.
V roce 1966 vyřešil Berger problém s dominou tím, že vyvrátil Wangovu domněnku. Dokázal, že nemůže existovat žádný algoritmus, když ukázal, jak přeměnit jakýkoli Turingův stroj na sadu Wangových dlaždic tak, aby dlaždice vydláždily letadlo tehdy a jen tehdy, pokud se Turingův stroj nezastavil. Z nemožnosti vyřešit problém zastavení (problém kontroly, zda se Turingův stroj nakonec zastaví), pak vyplývá nemožnost vyřešit Wangův problém s obklady [4] [4] .
Kombinace Bergerova výsledku s Wangovým pozorováním ukazuje, že musí existovat konečná množina Wangových dlaždic, které obkládají rovinu, ale pouze neperiodicky . Tuto vlastnost má Penroseův obklad a uspořádání atomů v kvazikrystalu . Přestože Bergerův původní soubor obsahoval 20 426 dlaždic, navrhl, že by mohly existovat i menší sady, včetně podmnožin jeho původní sady, a ve své nepublikované práci snížil počet dlaždic na 104. Později byly nalezeny ještě menší sady [5] [6]. [7] . Například sada 11 dlaždic a 4 barev výše je neperiodická sada a byla objevena Emmanuelem Jandelem a Michaelem Rao v roce 2015 pomocí vyčerpávajícího hledání, aby dokázali, že 10 dlaždic nebo 3 barvy nestačí k tomu, aby byly aperiodické [8]. .
Dlaždice Wang lze zobecnit různými způsoby a všechny jsou také nerozhodnutelné ve výše uvedeném smyslu. Například kostky Wang jsou kostky stejné velikosti s barevnými plochami, které se musí barevně shodovat při vytváření mnohostěnných obkladů ( voštiny ). Kulik a Kari ukázali neperiodické sady Wangových kostek [9] . Winfrey a spol., prokázali možnost vytvoření molekulárních „dlaždic“ na bázi DNA (deoxyribonukleové kyseliny), které mohou fungovat jako Wangovy dlaždice [10] . Mittal et al., ukázali, že peptidonukleové kyseliny (PNA), stabilní umělé podobnosti DNA, lze skládat z těchto dlaždic [11] .
Dlaždice Wang se v poslední době staly oblíbeným prostředkem pro vytváření algoritmických , výškových polí a dalších velkých, neopakujících se 2D datových sad. Malý počet předem vypočítaných nebo ručně vyrobených dlaždic lze sestavit rychle a levně bez zjevného opakování nebo periodicity. V tomto případě by běžné neperiodické obklady vykazovaly svou strukturu. Mnohem méně omezující sady, které poskytují alespoň dvě možnosti pro jakékoli dvě barvy stran, jsou přijatelnější, protože obklady lze snadno dosáhnout a každou dlaždici lze vybrat pseudonáhodně [12] [13] [14] [15] . Dlaždice Wang se také používají při kontrole rozhodnutelnosti teorie celulárních automatů [16] .
Povídka Grega Egana „ Van's Carpet “, později rozšířená do novely „Diaspora“ , vypráví o vesmíru plném organismů a myslících bytostí v podobě Vanových dlaždic, tvořených vzory složitých molekul [17] .
| geometrické mozaiky | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Pravidelné |
| ||||||||
| aperiodický |
| ||||||||
| jiný |
| ||||||||
| Podle konfigurace vrcholu |
| ||||||||