Vorlesung: Praxis der Funktionalen Programmierung

Aperiodische Muster und HD0L

Penrose

Die bisher betrachteten euklidischen Parkette waren periodisch. Betrachten wir diese zwei Bausteine (Rhomben mit Ecken- und Kantenfärbung) (Quelltext). Eine Parkettierung der Ebene scheint möglich, zeigt jedoch keine offensichtliche Periodizität.

Diese Steine fand Roger Penrose 197?. Man kann tatsächlich zeigen (Hausaufgabe, siehe später), daß sie überhaupt keine periodische Parkettierung der Ebene gestatten.

Ammann

Woran das liegt, sehen wir an einem einfacheren Beispiel: wir nehmen nur einen Baustein, ein L mit gleichdicken und -langen Schenkeln. Dieser gestattet viele Parkettierungen, darunter auch periodische.

Wir können jedoch auch leicht eine aperiodische Parkettierung angeben, und zwar durch eine rekursive Vorschrift, nach der wir das L in vier zum Original ähnliche, und untereinander kongruente Exemplare mit halber Seitenlänge zerlegen. Durch wiederholte Anwendung (Inflation) können wir dadurch immer größere Teile der Ebene überdecken, erhalten also tatsächlich eine Parkettierung.

Aufgabe: implementiere den Vorgang der Inflation, und zeige das Parkett nach jedem Schritt. Eine simple Variante liefert dieses Programm.

Färbungen

Diese Parkett aus L können wir andererseits erzwingen, in dem wir geeignete Ecken- und/oder Kantenfarben vergeben und dann nur kohärentes Aneinanderlegen gestatten. Übungsaufgabe: finde solch eine Färbung für das Ammann-L.

Aperiodizität

Das Parkett ist aperiodisch, was man wie folgt einsieht: angenommen, das Parkett P gehe durch eine Verschiebung um d in sich selbst über. Wir konstruieren aus P sein Urbild vor einer Inflation (nennen wir das Deflation). Das ist nur auf eine Weise möglich (muß man kurz prüfen).

Wir erhalten ein neues Parkett P' mit doppelt so großen Steinen. Es hat aber weiterhin die Verschiebung um d als Symmetrie-Abbildung.

Wir können das Verfahren so oft wiederholen, bis die Seitenlände der Steine größer als d ist, und erhalten damit einen Widerspruch. Die Verschiebung um d konnte also von Anfang an keine Symmetrie-Abbildung gewesen sein.

Aufgabe: für das Penrose-Parkett funktioniert die gleiche Idee, man muß sich aber die Inflation genau überlegen. Teste die Inflation (grafisch) mit oben erwähntem Programm.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de