Wang-plattor (eller Wang-dominobrickor ), som först föreslogs av matematikern, logikern och filosofen Hao Wang 1961, är en klass av formella system . De modelleras visuellt med fyrkantiga plattor med färg på varje sida. En uppsättning sådana brickor definieras (till exempel som i illustrationen), sedan appliceras kopior av dessa brickor på varandra med villkoret att matcha färgerna på sidorna, men utan rotation eller symmetrisk reflektion av brickorna.
Huvudfrågan om Vans uppsättning plattor är om de kan kakla ett plan eller inte, det vill säga om ett plan kan fyllas på detta sätt. Nästa fråga är om den kan fyllas i ett periodiskt mönster.
1961 förmodade Wang att om ett ändligt antal Wang-plattor kan belägga ett plan, så finns det en periodisk beläggning , det vill säga en beläggning som är invariant under translation av vektorer i ett tvådimensionellt gitter som tapeter. Han noterade också att denna gissning antyder att det finns en algoritm som bestämmer om en given ändlig uppsättning Wang-plattor kan belägga ett plan [1] [2] . Idén att begränsa anslutningen av intilliggande brickor har sitt ursprung i spelet dominobrickor , så Wang-brickor är också kända som Wangs dominobrickor [3] , och det algoritmiska problemet med att avgöra om brickor kan belägga ett plan är känt som dominoproblemet [ 4] .
Enligt Van-studenten Robert Berger [4] ,
Dominoproblemet handlar om klassen av alla dominouppsättningar. Uppgiften är att för varje uppsättning dominobrickor avgöra om en plattsättning är möjlig eller inte. Vi säger att Domino-problemet är avgörbart eller oavgörbart , beroende på om det finns en algoritm eller inte som, givet en uppsättning av en godtycklig uppsättning dominobrickor, avgör om plattsättningsproblemet för denna uppsättning är avgörbart eller inte.
Med andra ord frågar dominoproblemet om det finns en effektiv metod som korrekt löser problemet för givna uppsättningar av dominobrickor.
1966 löste Berger dominoproblemet genom att vederlägga Wangs gissningar. Han bevisade att det inte kunde finnas någon algoritm genom att visa hur man förvandlar vilken Turing-maskin som helst till en uppsättning Wang-plattor så att brickorna plattade planet om och bara om Turing-maskinen inte stannade. Från omöjligheten att lösa stoppproblemet (problemet med att kontrollera om Turing-maskinen så småningom stannar), så följer omöjligheten att lösa Wangs kakelproblem [4] [4] .
Kombination av Bergers resultat med Wangs observation visar att det måste finnas en ändlig uppsättning Wang-plattor som belägger planet, men endast icke- periodiskt . Denna egenskap innehas av Penrose-plattläggningen och arrangemanget av atomer i en kvasikristall . Även om Bergers originaluppsättning innehöll 20 426 brickor, föreslog han att mindre uppsättningar också kunde existera, inklusive delmängder av hans originaluppsättning, och i sin opublicerade avhandling minskade han antalet brickor till 104. Ännu mindre uppsättningar hittades senare [5] [6] [7] . Till exempel är uppsättningen med 11 brickor och 4 färger ovan en icke-periodisk uppsättning, och upptäcktes av Emmanuel Jandel och Michael Rao 2015 med hjälp av en uttömmande sökning för att bevisa att 10 brickor eller 3 färger inte räcker för att vara aperiodisk [8] .
Wang-plattor kan generaliseras på olika sätt, och alla är också oavgjorda i ovanstående mening. Till exempel är Wang -kuber kuber av samma storlek med färgade ytor som måste matcha i färg när man skapar polyedriska plattor ( bikakor ). Kulik och Kari visade icke-periodiska uppsättningar av Wang-kuber [9] . Winfrey et al har visat möjligheten att skapa molekylära "plattor" baserat på DNA (deoxiribonukleinsyra) som kan agera som Wangs plattor [10] . Mittal et al har visat att peptidonukleinsyror (PNA), stabila artificiella DNA-likheter, kan sammanställas med dessa plattor [11] .
Wang-plattor har nyligen blivit ett populärt sätt att skapa algoritmiska texturer, höjdfält och andra stora, icke-repeterande 2D-datauppsättningar. Ett litet antal förberäknade eller handgjorda plattor kan monteras snabbt och billigt utan uppenbara upprepningar eller periodicitet. I detta fall skulle vanliga icke-periodiska plattsättningar visa sin struktur. Mycket mindre restriktiva uppsättningar som ger minst två val för två sidofärger är mer acceptabla eftersom plattsättning är lätt att uppnå och varje bricka kan väljas pseudo-slumpmässigt [12] [13] [14] [15] . Wang-plattor används också för att kontrollera avgörbarheten av teorin om cellulära automater [16] .
Greg Egans novell " Van's Carpet ", som senare utökades till novellen "Diaspora" , berättar om ett universum fyllt med organismer och tänkande varelser i form av Vans plattor, bildade av mönster av komplexa molekyler [17] .
| geometriska mosaiker | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Periodisk |
| ||||||||
| Aperiodisk |
| ||||||||
| Övrig |
| ||||||||
| Genom vertexkonfiguration _ |
| ||||||||