Wang-fliser (eller Wang dominobrikker ), først foreslået af matematikeren, logikeren og filosoffen Hao Wang i 1961, er en klasse af formelle systemer . De er modelleret visuelt ved hjælp af firkantede fliser med farve på hver side. Et sæt af sådanne fliser er defineret (for eksempel som i illustrationen), derefter påføres kopier af disse fliser på hinanden med betingelsen om at matche farverne på siderne, men uden rotation eller symmetrisk refleksion af fliserne.
Hovedspørgsmålet om Vans sæt fliser er, om de kan flisebelægge et fly eller ej, altså om et plan kan udfyldes på denne måde. Det næste spørgsmål er, om det kan udfyldes i et periodisk mønster.
I 1961 formodede Wang, at hvis et begrænset antal Wang-fliser kan flisebelægge et plan, så eksisterer der en periodisk flisebelægning , det vil sige en flisebelægning, der er invariant under translation af vektorer i et todimensionelt gitter som tapet. Han bemærkede også, at denne formodning indebærer eksistensen af en algoritme, der bestemmer, om et givet endeligt sæt Wang-fliser kan flisebelægge et plan [1] [2] . Ideen om at begrænse forbindelsen af tilstødende fliser opstod i spillet domino , så Wang fliser er også kendt som Wangs dominobrikker [3] , og det algoritmiske problem med at afgøre, om fliser kan flisebelægge et fly er kendt som dominoproblemet [ 4] .
Ifølge Van-studerende Robert Berger [4] ,
Dominoproblemet omhandler klassen af alle dominosæt. Opgaven er at bestemme for hvert sæt dominobrikker, om en fliselægning er mulig eller ej. Vi siger, at Domino-problemet kan afgøres eller ikke kan afgøres , afhængigt af om der eksisterer en algoritme, der givet et sæt af et vilkårligt sæt dominobrikker bestemmer, om fliseproblemet for dette sæt kan afgøres eller ej.
Med andre ord spørger dominoproblemet, om der er en effektiv metode , der korrekt løser problemet for givne sæt dominobrikker.
I 1966 løste Berger dominoproblemet ved at tilbagevise Wangs formodning. Han beviste, at der ikke kunne være nogen algoritme ved at vise, hvordan man forvandler en hvilken som helst Turing-maskine til et sæt Wang-fliser, så fliserne lagde fliser på flyet, hvis og kun hvis Turing-maskinen ikke stoppede. Fra umuligheden af at løse stopproblemet (problemet med at kontrollere om Turing-maskinen til sidst stopper), så følger umuligheden af at løse Wangs fliseproblem [4] [4] .
Kombination af Bergers resultat med Wangs observation viser, at der skal være et begrænset sæt Wang-fliser, der fliser planet, men kun ikke- periodisk . Denne egenskab besiddes af Penrose-flisebelægningen og arrangementet af atomer i en kvasikrystal . Selvom Bergers originale sæt indeholdt 20.426 fliser, foreslog han, at der også kunne eksistere mindre sæt, inklusive delmængder af hans originale sæt, og i sin upublicerede afhandling reducerede han antallet af fliser til 104. Endnu mindre sæt blev senere fundet [5] [6] [7] . For eksempel er sættet med 11 fliser og 4 farver ovenfor et ikke-periodisk sæt og blev opdaget af Emmanuel Jandel og Michael Rao i 2015 ved hjælp af udtømmende søgning for at bevise, at 10 fliser eller 3 farver ikke er nok til at være aperiodiske [8] .
Wang-fliser kan generaliseres på forskellige måder, og alle er også uafgørlige i ovenstående forstand. For eksempel er Wang -terninger terninger af samme størrelse med farvede flader, der skal matche i farven, når du laver polyedriske fliser ( honningkager ). Kulik og Kari viste ikke-periodiske sæt Wang-terninger [9] . Winfrey et al. har vist muligheden for at skabe molekylære "fliser" baseret på DNA (deoxyribonukleinsyre), der kan virke som Wangs fliser [10] . Mittal et al. har vist, at peptidonukleinsyrer (PNA'er), stabile kunstige DNA-ligheder, kan sammensættes med disse fliser [11] .
Wang-fliser er for nylig blevet et populært middel til at skabe algoritmiske -teksturer, højdefelter og andre store, ikke-gentagende 2D-datasæt. Et lille antal forudberegnet eller håndlavede fliser kan samles hurtigt og billigt uden åbenlyse gentagelser eller periodicitet. I dette tilfælde vil almindelige ikke-periodiske flisebelægninger vise deres struktur. Meget mindre restriktive sæt, der giver mindst to valgmuligheder for alle to sidefarver, er mere acceptable, fordi fliselægning nemt opnås, og hver flise kan vælges pseudo-tilfældigt [12] [13] [14] [15] . Wang-fliser bruges også til at kontrollere afgøreligheden af teorien om cellulære automater [16] .
Greg Egans novelle " Van's Carpet ", senere udvidet til novellen "Diaspora" , fortæller om et univers fyldt med organismer og tænkende væsener i form af Vans fliser, dannet af mønstre af komplekse molekyler [17] .
| geometriske mosaikker | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Periodisk |
| ||||||||
| aperiodisk |
| ||||||||
| Andet |
| ||||||||
| Ved toppunktskonfiguration _ |
| ||||||||