Wang-Parkettierung

Wang-Kacheln und die Parkettierungsaufgabe

Wang-Kacheln, auch Wang Domino genannt, wurden 1961 von Hao Wang entworfen. Sie sind Rechtecke gleicher Größe, deren Kanten jeweils mit bestimmten Farben markiert sind. Ein endlicher Satz solcher Kacheln bildet eine Instanz eines unentscheidbaren Entscheidungsproblems.

Die Aufgabe lautet: Für einen gegebenen endlichen Kachelsatz soll entschieden werden, ob sich die unbegrenzte Ebene mit beliebig vielen Kopien dieser Kacheln lückenlos füllen lässt. Benachbarte Kacheln müssen an ihren gemeinsamen Seiten dieselbe Farbe besitzen. Die Kacheln dürfen weder gedreht noch gespiegelt werden.

Periodische und aperiodische Kachelung

Wang schlug 1961 einen Algorithmus für das Parkettierungsproblem vor. Sein Korrektheitsbeweis beruhte auf der Annahme, dass jeder Kachelsatz, der die Ebene füllen kann, dabei eine periodische Parkettierung erzeugt. Periodisch bedeutet hier, dass ein endlicher Ausschnitt der Kachelung sich regelmäßig wiederholt und dadurch die ganze Ebene füllt.

Robert Berger zeigte 1966, dass diese Annahme falsch ist. Er gab einen Satz von Wang-Kacheln an, der die Ebene zwar lückenlos, aber nur aperiodisch kacheln kann. Eine aperiodische Kachelung enthält also keinen sich periodisch wiederholenden endlichen Ausschnitt, der die gesamte Fläche erzeugt. Dies ähnelt der Penrose-Parkettierung und der Anordnung von Atomen in Quasi-Kristallen.

Berger verwendete zunächst 20.426 Kacheln und vermutete, dass kleinere aperiodische Sätze möglich seien. Später wurden kleinere Sätze gefunden; ein von Karel Culik publizierter aperiodischer Satz besteht aus 13 Kacheln.

Warum das Problem unentscheidbar ist

Wangs Algorithmus kann nicht für beliebige Kachelsätze korrekt entscheiden, ob eine Parkettierung möglich ist. Tatsächlich gibt es keinen solchen Algorithmus.

Jede Turingmaschine kann in einen Satz von Wang-Kacheln übersetzt werden, sodass dieser Satz die Ebene genau dann parkettieren kann, wenn die Turingmaschine nicht hält. Das Halteproblem ist nicht entscheidbar: Es gibt keinen Algorithmus, der für jede Turingmaschine entscheiden kann, ob sie anhält. Deshalb ist auch Wangs Kachelungsproblem nicht entscheidbar.

Semi-entscheidbar ist dagegen die Nichtparkettierbarkeit. Ein Algorithmus kann alle endlichen Teilmengen der Ebene untersuchen. Findet er eine endliche Teilmenge, die nicht mit dem Kachelsatz parkettiert werden kann, ist damit bewiesen, dass auch keine Parkettierung der ganzen Ebene möglich ist. Präzise ist das Problem bezüglich der Many-one-Reduktion ein vollständiges semi-entscheidbares Problem.

Grenzen, Verallgemeinerungen und Anwendungen

Dass Wangs ursprüngliches Verfahren nicht allgemein funktioniert, macht es für praktische Anwendungen nicht nutzlos. Sergio Demian Lerner zeigte mit einer optimierten Version der Methode, dass es keine aperiodischen Kachelsätze mit sieben oder weniger Kacheln gibt. Damit bleibt nur eine schmale Lücke für eine Verbesserung dieser unteren Grenze.

Wang-Kacheln lassen sich auf andere Formen übertragen, ohne dass die Unentscheidbarkeit im genannten Sinn verloren geht. Wang-Würfel sind beispielsweise gleich große Würfel mit gefärbten Flächen. Culik und Kari wiesen aperiodische Sätze von Wang-Würfeln nach.

Durch ihre einfache Struktur eignen sich Wang-Kacheln als Modelle für besonders einfache Maschinen mit derselben Leistungskraft wie Turingmaschinen. Winfree et al. zeigten, dass molekulare „Kacheln“ aus Desoxyribonukleinsäure (DNA) hergestellt und als Wang-Kacheln verwendet werden können. Mittal et al. zeigten dies auch für PNA, die Peptid-Nukleinsäure, eine chemische Variante der DNA.