A Wang csempe (vagy Wang dominó ), amelyet először Hao Wang matematikus, logikus és filozófus javasolt 1961-ben, a formális rendszerek egy osztálya . Vizuálisan modellezték négyzet alakú lapokkal, mindkét oldalon színezéssel. Meghatározzuk az ilyen lapok készletét (például az ábrán látható módon), majd ezeknek a lapoknak a másolatait egymásra helyezzük azzal a feltétellel, hogy az oldalak színei megegyezzenek, de a lapok elforgatása vagy szimmetrikus visszaverődése nélkül .
A Van csempekészletével kapcsolatban az a fő kérdés, hogy tudnak-e csempézni egy síkot vagy sem, vagyis ki lehet-e tölteni egy síkot így. A következő kérdés az, hogy periodikusan kitölthető-e.
1961-ben Wang azt sejtette, hogy ha véges számú Wang-lapka csempézhet egy síkot, akkor létezik periodikus csempézés , azaz olyan csempészet, amely invariáns a vektorok transzlációja alatt egy kétdimenziós rácsban, például a tapétában. Azt is megjegyezte, hogy ez a sejtés egy olyan algoritmus létezését jelenti, amely meghatározza, hogy egy adott véges Wang-lapkák halmaza képes-e csempézni egy síkot [1] [2] . A szomszédos lapkák összekapcsolásának korlátozásának ötlete a dominójátékból származik , ezért a Wang lapkákat Wang dominóiként is ismerik [3] , az algoritmikus problémát pedig annak meghatározására, hogy a lapkák képesek-e csempézni egy síkot, dominóproblémaként ismert . 4] .
Robert Berger Van diák szerint [4] ,
A dominó probléma az összes dominóhalmaz osztályával foglalkozik. A feladat annak meghatározása, hogy minden egyes dominókészletre lehetséges-e a burkolás. Azt mondjuk, hogy a Dominó-probléma eldönthető vagy eldönthetetlen , attól függően, hogy létezik-e olyan algoritmus, amely egy tetszőleges dominóhalmaz alapján meghatározza, hogy ennek a halmaznak a csempézési problémája eldönthető-e vagy sem.
Más szóval, a dominóprobléma azt kérdezi, hogy létezik-e olyan hatékony módszer , amely helyesen oldja meg a problémát adott dominóhalmazokra.
1966-ban Berger Wang sejtésének megcáfolásával oldotta meg a dominóproblémát. Bebizonyította, hogy nem létezhet algoritmus, bemutatva, hogyan lehet bármilyen Turing-gépet Wang-lapkává alakítani úgy, hogy a lapkák akkor és csak akkor csempézzék a síkot, ha a Turing-gép nem áll meg. A megállítási probléma megoldásának lehetetlenségéből (a Turing-gép végül megállásának ellenőrzésének problémája), majd a Wang-féle csempézési probléma [4] [4] megoldásának lehetetlensége következik .
Berger eredményét Wang megfigyelésével kombinálva látható, hogy véges Wang lapkák halmazának kell lennie a síkban, de csak nem periodikusan . Ezt a tulajdonságot a Penrose burkolat és az atomok kvázikristályban való elrendezése birtokolja . Bár Berger eredeti készlete 20 426 lapkát tartalmazott, felvetette, hogy kisebb halmazok is létezhetnek, beleértve az eredeti halmazának részhalmazait is, és kiadatlan dolgozatában 104-re csökkentette a lapkák számát. Később még kisebb halmazokat is találtak [5] [6]. [7] . Például a fenti 11 lapkából és 4 színből álló készlet egy nem periodikus készlet, és Emmanuel Jandel és Michael Rao fedezte fel 2015-ben, kimerítő kereséssel annak bizonyítására, hogy 10 lapka vagy 3 szín nem elég az időszakos készlethez [8] .
A Wang csempe többféleképpen általánosítható, és mindegyik a fenti értelemben eldönthetetlen. Például a Wang kockák azonos méretű kockák színes lappal, amelyeknek meg kell egyeznie a színükkel poliéderes burkolólapok ( méhsejt ) létrehozásakor. Kulik és Kari Wang-kockák nem periodikus halmazait mutatta be [9] . Winfrey és munkatársai megmutatták a DNS-en (dezoxiribonukleinsavon) alapuló molekuláris „csempék” létrehozásának lehetőségét, amelyek Wang -csempékhez hasonlóan működhetnek [10] . Mittal és munkatársai kimutatták, hogy ezekkel a lapokkal peptidonukleinsavak (PNA-k), amelyek stabil mesterséges DNS-hasonlítások alkothatók [11] .
A Wang csempék a közelmúltban az algoritmikus textúrák, magassági mezők és más nagy, nem ismétlődő 2D adatkészletek létrehozásának népszerű eszközeivé váltak . Kis számú előre kiszámított vagy kézzel készített csempét gyorsan és olcsón össze lehet szerelni nyilvánvaló ismétlés vagy periodikusság nélkül. Ebben az esetben a közönséges nem időszakos burkolólapok szerkezetüket mutatják. Sokkal kevésbé korlátozó halmazok, amelyek legalább két választási lehetőséget biztosítanak bármely két oldalszínhez, elfogadhatóbbak, mivel a csempézés könnyen megvalósítható, és minden lapkát pszeudo-véletlenszerűen lehet kiválasztani [12] [13] [14] [15] . A Wang lapkákat a sejtautomaták elméletének eldönthetőségének ellenőrzésére is használják [16] .
Greg Egan " Van's Carpet " című novellája , amelyet később a "Diaspora" novellává bővítettek , egy olyan univerzumról mesél, amely tele van organizmusokkal és gondolkodó lényekkel, Van csempék formájában, amelyeket összetett molekulák mintái alkotnak [17] .
| geometrikus mozaikok | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Időszakos |
| ||||||||
| időszakos |
| ||||||||
| Egyéb |
| ||||||||
| Csúcskonfiguráció szerint _ |
| ||||||||