Ziegel von Wang (oder Dominos von Wang), zuerst vorgeschlagen vom Mathematiker, Logiker, und Philosophen Hao Wang 1961, sind eine Klasse von formellen Systemen. Sie werden visuell durch gleich-große Quadrate mit einer Farbe an jedem Rand modelliert, der nebeneinander eingeordnet werden kann (auf einem regelmäßigen Quadratbratrost), so dass angrenzende Ränder von angrenzenden Ziegeln dieselbe Farbe haben; die Ziegel können nicht rotieren gelassen oder widerspiegelt werden.

Die grundlegende Frage, die ungefähr eine Reihe von Ziegeln von Wang ist, ob sie das Flugzeug oder nicht mit Ziegeln decken kann, d. h., ob Kopien der Ziegel eingeordnet werden können, um ein unendliches Flugzeug im Anschluss an die Angrenzen-Regeln zu füllen.

1961 hat Wang dass vermutet, wenn ein begrenzter Satz von Ziegeln das Flugzeug mit Ziegeln decken kann, dann dort besteht auch periodisch mit Ziegeln zu decken, d. h., mit Ziegeln zu decken, der invariant laut Übersetzungen durch Vektoren in einem 2-dimensionalen Gitter wie ein Tapete-Muster ist. Er hat auch bemerkt, dass diese Vermutung die Existenz eines Algorithmus einbeziehen würde, um zu entscheiden, ob ein gegebener begrenzter Satz von Ziegeln das Flugzeug mit Ziegeln decken kann.

Aber 1966 hat Robert Berger bewiesen, dass kein solcher Algorithmus durch die Vertretung bestanden hat, wie man jede Maschine von Turing in eine Reihe von Ziegeln von Wang übersetzt, die das Flugzeug mit Ziegeln deckt, wenn, und nur wenn die Maschine von Turing nicht hinkt. Die Unentscheidbarkeit des stockenden Problems bezieht dann die Unentscheidbarkeit des mit Ziegeln deckenden Problems von Wang ein. Das Kombinieren davon mit der Beobachtung von Wang zeigt, dass dort ein begrenzter Satz von Ziegeln von Wang bestehen muss, der das Flugzeug, aber nur aperiodisch mit Ziegeln deckt. Das ist einem Penrose ähnlich, der oder der Einordnung von Atomen in einem Quasikristall mit Ziegeln deckt. Obwohl der ursprüngliche Satz von Berger 20,426 Ziegel enthalten hat, hat er vermutet, dass kleinere Sätze einschließlich Teilmengen seines Satzes arbeiten würden. In späteren Jahren wurden zunehmend kleinere Sätze gefunden. Zum Beispiel ist der Satz von 13 Ziegeln, die oben gegeben sind, ein aperiodischer Satz, der von Karel Culik II 1996 veröffentlicht ist. Es kann das Flugzeug, aber nicht regelmäßig mit Ziegeln decken.

Ziegel von Wang können auf verschiedene Weisen verallgemeinert werden, von denen alle auch im obengenannten Sinn unentscheidbar sind. Zum Beispiel sind Würfel von Wang gleich-große Würfel mit farbigen Gesichtern, und Seitenfarben können auf jedem polygonalen tessellation verglichen werden.

Culik und Kari haben aperiodische Sätze von Würfeln von Wang demonstriert. Winfree. haben die Durchführbarkeit demonstriert, molekulare von der DNA gemachte "Ziegel" zu schaffen (deoxyribonucleic Säure), der als Ziegel von Wang handeln kann. Mittal u. a. haben gezeigt, dass diese Ziegel auch aus Peptide-Nukleinsäure (PNA), ein Stall künstlich mimisch der DNA zusammengesetzt werden können.

Ziegel von Wang sind kürzlich ein populäres Werkzeug für die Verfahrenssynthese von Texturen, heightfields, und andere große und sich nichtwiederholende bidimensional Dateien geworden; ein kleiner Satz von vorgeschätzten oder handgefertigten Quellziegeln kann sehr preiswert ohne zu offensichtliche Wiederholungen und ohne Periodizität gesammelt werden.

In diesem Fall würde traditioneller aperiodischer tilings ihre sehr regelmäßige Struktur zeigen; viel weniger gezwungene Sätze, die mindestens zwei Ziegel-Wahlen für irgendwelche zwei gegebenen Seitenfarben versichern, sind üblich, weil tileability leicht gesichert wird und jeder Ziegel pseudozufällig ausgewählt werden kann.

Papiere über diese Anwendung schließen ein:

• Jos Stam (1997), Aperiodische Kartografisch darstellende Textur führt die Idee ein, Ziegel von Wang für die Textur-Schwankung mit einem deterministischen Ersatz-System zu verwenden.
• Michael F. Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen (2003), führt Wang Tiles für die Bild- und Textur-Generation ein stochastisch mit Ziegeln zu decken, und ist sehr populär.
• Li-Yi Wei (2004), "Wendet sich Ziegel-basierte auf der Grafikhardware Kartografisch darstellende Textur" an Wang Tiles wegen schritthaltenden texturing auf einem GPU
• Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski (2006), zeigt Rekursiver Wang Tiles für das Blaue Echtzeitgeräusch fortgeschrittene Anwendungen.

Die Novelle-Teppiche von Wang, die später zur neuartigen Diaspora durch Greg Egan ausgebreitet sind, verlangen ein Weltall, das mit Residentorganismen und intelligenten Wesen abgeschlossen ist, aufgenommen als durch Muster von komplizierten Molekülen durchgeführte Ziegel von Wang.

• Wang, Hao (Januar 1961). "Lehrsätze durch die Muster-Anerkennung — II", Glockensystemtechnologie beweisend. Zeitschrift 40 (1):1-41. (Wang schlägt seine Ziegel vor und vermutet, dass es keine aperiodischen Sätze gibt).
• Wang, Hao (November 1965). "Spiele, Logik und Computer" im Wissenschaftlichen Amerikaner, Seiten 98-106. (Präsentiert sie für ein populäres Publikum)
• Berger, R. (1966). "Die Unentscheidbarkeit des Domino-Problems", Lebenserinnerungen Amer. Mathematik. Soc. 66 (1966). (Ruft den Begriff "Ziegel von Wang" ins Leben, und demonstriert den ersten aperiodischen Satz von ihnen).
• Cohen, M. F., Schatten, J., Hiller, S. und Deussen, O. 2003. "Wang Tiles für das Image und die Textur-Generation", In ACM SIGGRAPH 2003-Papiere (San Diego, Kalifornien, am 27-31 Juli 2003). SIGGRAPH '03. ACM Presse, New York, New York, 287-294.
• Culik, K. (1996). "Ein aperiodischer Satz von 13 Ziegeln von Wang", Getrennte Mathematik 160, 245-251. (Hat einen aperiodischen Satz von 13 Ziegeln mit 5 Farben gezeigt).
• Kari, J. (1996). "Ein kleiner aperiodischer Satz von Ziegeln von Wang", Getrennte Mathematik 160, 259-264.
• Culik, K. und J. Kari (1995). "Ein aperiodischer Satz von Würfeln von Wang", Zeitschrift der Universalen Informatik 1, 675-686 (1995).
• Winfree, E., Liu, F., Wenzler, L.A. und Seeman, N.C. (1998). "Design und Selbstzusammenbau von Zweidimensionalen DNA-Kristallen, Natur 394, 539-544.
• Lukeman, P., Seeman, N. und Mittal, (2002). "Hybride PNA/DNA Nanosystems." In der 1. Internationalen Konferenz für die Nanoscale/Molecular Mechanik (N-M2-I), das Outrigger Wailea Resort, Maui, die Hawaiiinseln.

Links

• Die Seite von Steven Dutch einschließlich vieler Bilder von aperiodischem tilings