| dbo:abstract
|
- Wang-Kacheln (oder Wang Domino), entworfen 1961 von Hao Wang, sind Gruppen von Rechtecken gleicher Größe, deren Kanten je mit einer bestimmten Farbe markiert sind. Eine solche Gruppe von Kacheln stellt eine Instanz eines unentscheidbaren Entscheidungsproblems dar. Das folgende Bild zeigt einen Satz von 13 Wang-Kacheln: Die zu lösende Aufgabe bzw. das Entscheidungsproblem besteht darin, zu entscheiden, ob es mit einem gegebenen endlichen Satz an Kacheln möglich ist, die Ebene zu parkettieren. Dies heißt, mit beliebig vielen Kopien der Kacheln aus dem Satz die unbegrenzte Ebene lückenlos so zu füllen, dass dabei alle verwendeten Kacheln jeweils mit Seiten gleicher Farbe aneinanderstoßen. Die Kacheln dürfen dabei nicht verdreht oder gespiegelt werden. Wang schlug 1961 einen Algorithmus vor, der dieses Problem lösen sollte. Im Beweis der Korrektheit seines Verfahrens nahm er an, dass jeder Satz von Kacheln, die die Ebene füllen, diese dabei periodisch parkettieren würde. 1966 zeigt Robert Berger jedoch, dass Wangs Vermutung falsch war. Er gab dazu einen Satz Wang-Kacheln an, mit dem man die Fläche nur aperiodisch kacheln konnte. Mit diesen Kacheln kann man zwar die Ebene lückenlos füllen, jedoch nicht so, dass dabei die Fläche von einem sich periodisch immer wiederholenden endlichen Ausschnitt gefüllt wird. Dies ist ähnlich der Lage bei der Penrose-Parkettierung oder der Anordnung der Atome in Quasi-Kristallen. Obwohl Berger ursprünglich einen Satz von 20.426 Kacheln verwendete, vermutete er, dass eine geringere Anzahl von Kacheln mit dieser Eigenschaft ebenfalls möglich wäre. In den folgenden Jahren wurden immer kleinere Sätze von Kacheln gefunden. Beispielsweise ist die oben abgebildete Gruppe aus 13 Kacheln ein von Karel Culik publizierter aperiodischer Satz. Wangs Algorithmus zur Entscheidung, ob ein gegebener Satz von Kacheln die Ebene parkettiert, war also nicht korrekt. In der Tat existiert ein solcher Algorithmus nicht. Es ist möglich, jede Turingmaschine derart in einen Satz von Wang-Kacheln zu übersetzen, dass diese Kacheln die Ebene genau dann parkettieren, wenn die Turingmaschine nicht hält. Da das Halteproblem nicht entscheidbar ist, ist auch das Kachelungsproblem von Wang nicht entscheidbar. Umgekehrt ist das Problem semi-entscheidbar, ob eine Parkettierung nicht möglich ist. Ein entsprechender Algorithmus geht alle endlichen Teilmengen der Ebene durch und braucht nur zu erkennen, dass für eine solche eine Parkettierung nicht möglich ist. Zusammengefasst lassen sich über die Nichtparkettierbarkeit mit einem Satz von Kacheln dieselben Probleme lösen wie mit einer Turingmaschine. Präzise: Das Problem ist bezüglich der Many-one-Reduktion ein vollständiges semi-entscheidbares Problem. Der Umstand, dass Wangs Verfahren prinzipiell nicht auf beliebige Kachelsätze anwendbar ist, macht dieses jedoch nicht nutzlos für praktische Anwendungen. Mit einer optimierten Version der ursprünglichen Methode konnte Sergio Demian Lerner zeigen, dass es keine aperiodischen Kachelsätze mit sieben oder weniger Kacheln gibt. Diese untere Grenze lässt nur noch eine schmale Lücke zur Verbesserung. Wang-Kacheln können in verschiedenster Weise verallgemeinert werden, die alle unentscheidbar in obigem Sinne sind. Zum Beispiel sind Wang-Würfel gleich große Würfel mit gefärbten Flächen. Culik und Kari haben aperiodische Sätze von Wang-Würfeln aufweisen können. Wangs Kacheln eignen sich wegen ihrer Einfachheit zur Herstellung einfachster Maschinen oder Modelle, die dieselbe Leistungskraft wie Turingmaschinen haben. Winfree et al. haben die Herstellbarkeit von molekularen „Kacheln“ aus Desoxyribonukleinsäure (DNA) nachgewiesen, die man als Wang-Kacheln verwenden kann. Mittal et al. haben das Gleiche auch für PNA (Peptid-Nukleinsäure) gezeigt, eine chemische Variante der DNA. (de)
- Azulejos Wang (o Dominó Wang), primero propuestos por el matemático, lógico, y filósofo en 1961, es una clase de sistemas formales. Son modelados visualmente por azulejos cuadrados con un color en cada lado. Un conjunto de tales azulejos está seleccionado, y las copias de los azulejos son puesto lado a lado con colores iguales, sin rotarlos ni reflejándolos. La cuestión básica sobre un conjunto de Wang los azulejos es si puede enladrillar el plano o no, por ejemplo, si un plano infinito entero puede ser llenado de este modo. La siguiente pregunta es si esto puede ser hecho en un patrón periódico. (es)
- Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them. The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern. (en)
- I tasselli di Wang (o domino di Wang), inizialmente proposti dal matematico, logico e filosofo Wang Hao nel 1961, sono una classe di sistemi formali, visualizzabili come tasselli quadrati, con un colore su ciascun lato, che possono tassellare il piano, disponendoli affiancati lungo il lato del medesimo colore, senza ruotarli o rifletterli specularmente. Poiché all'epoca gli esperti ritenevano che non esistessero insiemi di tasselli in grado di tassellare il piano soltanto in modo non periodico, ritenendo che si potessero sempre operare traslazioni tali da ricondursi a schemi periodici, la domanda fondamentale che si pose Wang fu se un insieme dei suoi tasselli, in grado di tassellare il piano in modo non periodico, potesse farlo anche in modo periodico. (it)
- ワンのタイル（英: Wang tiles, Wang dominoes,中: 王氏砖）とは、数学者、論理学者、哲学者であったハオ・ワン（王浩）が1961年に始めて提案した一種の形式体系である。視覚的には辺ごとに色付けされた正方形タイルとしてモデル化される。数種のタイルからなる集合を選び、隣り合う辺の色が一致するようにタイルのコピーを並べていく。このときタイルを回転・鏡映させてはいけない。 あるタイルの集合が与えられたとき、それが平面を敷き詰めることができるか、つまり上記のルールに沿って無限平面を埋め尽くすことができるかどうかが基本の問題である。その次には周期的なパターンで敷き詰められるかが問題になる。 (ja)
- Een wang-betegeling is een betegeling van het tweedimensionale vlak met zogenaamde wang-tegels of wang-domino's. Dit zijn identieke vierkanten die verdeeld zijn in vier driehoekige gedeelten door hun twee diagonalen. Elke driehoek heeft een bepaalde kleur. De betegeling gebeurt met een eindige verzameling van deze tegels, elk met een verschillende keuze van kleuren. De betegeling gebeurt in een rechthoekig patroon en zodanig dat tegels die elkaar raken dat moeten doen met dezelfde kleur. De tegels mogen niet gedraaid of gespiegeld worden. Elke tegel uit de verzameling mag een eindig of oneindig aantal keren gebruikt worden. Deze betegeling werd in 1961 bedacht door de wiskundige . Dit is een voorbeeldverzameling van 13 wang-tegels: (nl)
- 王氏砖（英語：Wang tile）也稱為王氏多米诺骨牌，最早由数学家、逻辑学家和哲学家王浩于1961年提出，屬於，也是形式系統。 王氏砖的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏砖拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。 关于特定一組王氏砖的基本问题是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式填合无限大的平面。下一個问题是是否存在周期性的密鋪方式？ (zh)
- Плитки Вана (или домино Вана), впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток (например, как на иллюстрации), затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток. Основной вопрос о наборе плиток Вана — могут ли они замостить плоскость или нет, то есть может ли плоскость быть заполнена таким способом. Следующий вопрос, может ли она быть заполнена в виде периодического узора. (ru)
- Плитки Вана (або доміно Вана), вперше запропоновані математиком, логіком і філософом в 1961, — це клас формальних систем. Вони моделюються візуально за допомогою квадратних плиток з розфарбуванням кожного боку. Визначається набір таких плиток (наприклад, як на ілюстрації), потім копії цих плиток прикладаються одна до одної з умовою узгодження кольорів сторін, але без обертання або симетричного відображення плиток. Основне питання про набір плиток Вана — чи можуть вони замостити площину чи ні, тобто чи можна площину заповнити таким способом. Наступне питання, чи можна її заповнити у вигляді періодичного візерунка. (uk)
|
| rdfs:comment
|
- Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them. The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern. (en)
- ワンのタイル（英: Wang tiles, Wang dominoes,中: 王氏砖）とは、数学者、論理学者、哲学者であったハオ・ワン（王浩）が1961年に始めて提案した一種の形式体系である。視覚的には辺ごとに色付けされた正方形タイルとしてモデル化される。数種のタイルからなる集合を選び、隣り合う辺の色が一致するようにタイルのコピーを並べていく。このときタイルを回転・鏡映させてはいけない。 あるタイルの集合が与えられたとき、それが平面を敷き詰めることができるか、つまり上記のルールに沿って無限平面を埋め尽くすことができるかどうかが基本の問題である。その次には周期的なパターンで敷き詰められるかが問題になる。 (ja)
- 王氏砖（英語：Wang tile）也稱為王氏多米诺骨牌，最早由数学家、逻辑学家和哲学家王浩于1961年提出，屬於，也是形式系統。 王氏砖的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏砖拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。 关于特定一組王氏砖的基本问题是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式填合无限大的平面。下一個问题是是否存在周期性的密鋪方式？ (zh)
- Wang-Kacheln (oder Wang Domino), entworfen 1961 von Hao Wang, sind Gruppen von Rechtecken gleicher Größe, deren Kanten je mit einer bestimmten Farbe markiert sind. Eine solche Gruppe von Kacheln stellt eine Instanz eines unentscheidbaren Entscheidungsproblems dar. Das folgende Bild zeigt einen Satz von 13 Wang-Kacheln: Wang schlug 1961 einen Algorithmus vor, der dieses Problem lösen sollte. Im Beweis der Korrektheit seines Verfahrens nahm er an, dass jeder Satz von Kacheln, die die Ebene füllen, diese dabei periodisch parkettieren würde. (de)
- Azulejos Wang (o Dominó Wang), primero propuestos por el matemático, lógico, y filósofo en 1961, es una clase de sistemas formales. Son modelados visualmente por azulejos cuadrados con un color en cada lado. Un conjunto de tales azulejos está seleccionado, y las copias de los azulejos son puesto lado a lado con colores iguales, sin rotarlos ni reflejándolos. (es)
- I tasselli di Wang (o domino di Wang), inizialmente proposti dal matematico, logico e filosofo Wang Hao nel 1961, sono una classe di sistemi formali, visualizzabili come tasselli quadrati, con un colore su ciascun lato, che possono tassellare il piano, disponendoli affiancati lungo il lato del medesimo colore, senza ruotarli o rifletterli specularmente. (it)
- Een wang-betegeling is een betegeling van het tweedimensionale vlak met zogenaamde wang-tegels of wang-domino's. Dit zijn identieke vierkanten die verdeeld zijn in vier driehoekige gedeelten door hun twee diagonalen. Elke driehoek heeft een bepaalde kleur. De betegeling gebeurt met een eindige verzameling van deze tegels, elk met een verschillende keuze van kleuren. De betegeling gebeurt in een rechthoekig patroon en zodanig dat tegels die elkaar raken dat moeten doen met dezelfde kleur. De tegels mogen niet gedraaid of gespiegeld worden. Elke tegel uit de verzameling mag een eindig of oneindig aantal keren gebruikt worden. Deze betegeling werd in 1961 bedacht door de wiskundige . (nl)
- Плитки Вана (или домино Вана), впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток (например, как на иллюстрации), затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток. (ru)
- Плитки Вана (або доміно Вана), вперше запропоновані математиком, логіком і філософом в 1961, — це клас формальних систем. Вони моделюються візуально за допомогою квадратних плиток з розфарбуванням кожного боку. Визначається набір таких плиток (наприклад, як на ілюстрації), потім копії цих плиток прикладаються одна до одної з умовою узгодження кольорів сторін, але без обертання або симетричного відображення плиток. (uk)
|
