Wissenschaftssommer 2008

Das Parkettierungsproblem

Die Aufgabe

Gegeben sind 16 verschiedene Kachelmuster. Kann man damit beliebig große Flächen überdecken, so daß jeweils benachbarte Kacheln aneinanderpassen?
Wir haben ca. 300 Kacheln der Fläche 8cm x 8cm, es sollte möglich sein, damit (auf dem Fußboden) ein Quadrat aus 17 x 17 Kacheln zu legen.
Mit unseren Kacheln ist es möglich, beliebig große Flächen zu überdecken, aber unmöglich, dabei ein periodisches Muster zu benutzen.

Mathematischer Hintergrund

Die Frage nach regelmäßigen Flächenfüllungen mit wenigen verschiedenen Grundformen ist uralt. Die Architekturgeschichte zeigt uns kunstvolle Beispiele.
Nicht alle Kacheln passen beliebig zusammen. Das ergibt folgende Frage:

  • Eingabe: eine endliche Menge von quadratischen Kacheln mit farbig markierten Seiten
  • Frage: gibt es eine Überdeckung der gesamten Ebene mit solchen Kacheln, wobei benachbarte Kanten gleichfarbig sind?
Man dachte, daß diese Frage entscheidbar sei. Das Argument war folgendes:
  • Die Menge aller Eingaben, für die die Antwort « nein» ist, ist aufzählbar: wenn man nicht die gesamte Ebene überdecken kann, gibt es bereits eine Zahl n, so daß man ein Quadrat der Größe n Mal n nicht überdecken kann. Man kann der Reihe nach für jede Seitenlänge alle Möglichkeiten durchprobieren, das Quadrat zu überdecken. Da es unendlich viele Eingaben gibt, muß man alle parallel behandeln: man testet für die erste Eingabe die Seitenlänge 1, dann für die zweite Eingabe die Seitenlänge 1, dann für die erste Eingabe die Seitenlänge 2, dann für die dritte Eingabe die Seitenlänge 1 usw.
  • Die Menge aller Eingaben, für die die Antwort « ja» ist, sollte auch aufzählbar sein, wenn man annimmt, daß man immer auch eine periodische Überdeckung der Ebene wählen kann, wenn die Überdeckung überhaupt möglich ist. Man testet dann ebenfalls in der oben beschriebenen Weise, ob für die Eingaben eine periodische Überdeckung mit gewisser Anzahl von Kacheln möglich ist.
Dieses Argument ist allerdings unvollständig: Berger gab 1966 eine Kachelmenge an, mit der man die Ebene überdecken konnte, die jedoch keine periodische Überdeckung gestattet. Diese Menge besteht aus 20426 Kacheln. Die Existenz einer solchen aperiodischen Menge war damals eine große Überraschung. Ammann fand 1978 die hier benutzte aperiodische Menge von 16 Kacheln. Es ist (Stand 1987) unklar, ob es eine kleinere aperiodische Menge gibt.
Das oben angeführte Argument läßt sich tatsächlich nicht reparieren, weil die Frage nach der Parkettierung nicht algorithmisch lösbar ist: Das Parkettierungsproblem ist unentscheibar. Man kann das etwa so einsehen: durch die Kacheln kann man eine Rechnung einer Turingmaschine simulieren. Dabei ist die eine Koordinate die Zeit, die andere der Weg (auf dem Band). Da die Maschine nur endliche viele Zeichen und Zustände besitzt, ist auch die benötigte Menge der Kacheln endlich. Die Maschine hält, wenn die Kacheln nur einen beschränkten Teil der Ebene überdecken. Das Halteproblem ist bekanntermaßen unentscheidbar.
Aus dieser Überlegung folgt auch, daß die Menge der Eingaben mit Antwort «ja» zur Komplexitätsklasse co-RE gehört (ihr Komplement ist aufzählbar) und dort sogar vollständig ist.

Anwendungen

Die Unentscheidbarkeit des Halteproblems ist seit 1940 bekannt, also seit den Anfangstagen der modernen Informatik.
Es handelt sich hierbei nicht um eine Fehler eines bestimmten Maschinenmodelles, sondern um eine grundsätzliche Beschränkung aller Algorithmen (für Turing-Maschinen, C-Programme, Java-Programme, für einfache Desktop-Rechner, für teuere Multi-Core-Rechner): man kann ihr Verhalten nicht automatisch vorhersagen.
Daraus zieht man in der Softwaretechnik die Lehre, daß dann eben der Informatiker für diese Vorhersage verantwortlich ist: es ist seine Aufgabe, das gewünschte Programmverhalten zu spezifizieren und dann auch zu beweisen, daß es immer tatsächlich so eintritt. Für das Spezifizieren und Beweisen gibt es geeignete Sprachen und Hilfsmittel.

Komplexitätsklasse: RE
Selber Ausprobieren:Hier!
Quellen / Fußnoten:[1] Branko Grünbaum und G. C. Shephard,
Tilings and Patterns, W. H. Freeman, 1987.

© HTWK