Regel 30
Regel 30 (englisch Rule 30) ist ein eindimensionaler zellulärer Automat, der 1983 von Stephen Wolfram entdeckt wurde.[2] Die Regel legt fest, wie sich der Zustand einer bestimmten Zelle in einem eindimensionalen Gitter verändert (schwarz oder weiß). Werden viele Ausführungen der Regel untereinander abgetragen, entsteht ein für die Regel typisches zweidimensionales Muster (siehe Abbildung unten). Nach Wolframs Klassifikationsschema gehört dieser zelluläre Automat der „Klasse 3“ an, was bedeutet, dass er nichtperiodisches, chaotisches Verhalten zeigt.
Beschreibung
[Bearbeiten | Quelltext bearbeiten]Die Regel 30 ist von besonderem Interesse, da sie komplexe, scheinbar zufällige Strukturen hervorruft, die klare lokale Regelmäßigkeiten aufweisen. Genau diese Strukturen weisen die Schneckenhäuser des Weberkegel, einer Meeresschneckenart, auf. Mit der Regel wurde ebenfalls ein Zufallszahlengenerator für Mathematica entwickelt[3] und eine Stromchiffre zur Verschlüsselung von Informationen[4][5] vorgeschlagen. Jedoch wurde gezeigt, dass andere zelluläre Automaten zur Verschlüsselung besser geeignet sind.
Definition
[Bearbeiten | Quelltext bearbeiten]Die vorrangig von Stephen Wolfram untersuchten elementaren zellulären Automaten bestehen aus einem unendlich langen, eindimensionalen Gitter aus Zellen. Diese Zellen können den Zustand 0 (weiß) oder 1 (schwarz) annehmen. Zu Beginn wird die Konfiguration der Zellen festgelegt, z. B. eine einzelne schwarze Zelle. In jedem folgenden Zeitschritt wird auf die einzelnen Zellen eine Regel angewandt, die bestimmt, ob die Zelle im nächsten Schritt schwarz oder weiß ist. Dabei hängt der jeweils nächste Zustand von der Zelle selbst und von ihrer linken und rechten Nachbarzelle ab. Eine Regel muss deshalb mögliche Zellkombinationen definieren, z. B. 010 (die Zelle ist schwarz, linker und rechter Nachbar sind weiß):
| Aktueller Zustand von linkem Nachbar, Zelle und rechtem Nachbar | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Neuer Zustand der betrachteten Zelle | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Jeder der acht Möglichkeiten (000 bis 111) kann ein beliebiger Zustand 0 oder 1 zugewiesen werden. Insgesamt gibt es daher elementare zelluläre Automaten. Ihre Benennung erfolgt nach dem von Wolfram aufgestellten Schema, indem man die acht nebeneinander geschriebenen Zustände als eine Binärzahl liest, z. B. 00011110, die entsprechende Dezimalzahl ergibt den Namen des elementaren Automaten (in diesem Fall 30).
Ihr Spiegelbild, Komplement und komplementäres Spiegelbild sind die Regeln 86 (01010110), 135 (10000111) und 149 (10010101).
Das folgende Diagramm zeigt die Hintereinanderausführung der Regel, wobei zu Beginn nur eine einzige Zelle schwarz und alle anderen weiß gefärbt sind. Die vertikale Achse beschreibt die Zeit und jede horizontale Linie zeigt den Zustand der Zellen zu einem bestimmten Zeitschritt.
Eigenschaften des Musters
[Bearbeiten | Quelltext bearbeiten]
Vor allem zwei Strukturen sind zu erkennen: Das häufige Auftreten weißer Dreiecke und das regelmäßige gestreifte Muster auf der linken Seite. Die Anzahl der schwarzen Zellen zu einem bestimmten Zeitpunkt beschreibt die Folge
und ist ungefähr gleich .
Chaos
[Bearbeiten | Quelltext bearbeiten]Die Regel 30 scheint nicht nur aus optischen Gründen chaotisch, sondern sie erfüllt auch die mathematischen Bedingungen an Chaos:
- Sie hängt hochsensibel von den Anfangswerten ab. Das heißt, dass zwei geringfügig verschiedene Anfangskonfigurationen sich sehr schnell auseinanderentwickeln (divergieren).
- Alle periodischen Konfigurationen sind zusammen eine dichte Teilmenge der Menge aller Konfigurationen.
- Sie ist topologisch transitiv auf der Menge aller Konfigurationen (sie wirbelt die Konfigurationen durcheinander).
Weblinks
[Bearbeiten | Quelltext bearbeiten]
- Eric W. Weisstein: Rule 30. In: MathWorld (englisch).
- Regel 30 in Wolfram's Atlas of Cellular Automata (englisch)
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Stephen Coombes: The Geometry and Pigmentation of Seashells. (PDF; 3,3 MB) In: maths.nottingham.ac.uk. University of Nottingham, Februar 2009, abgerufen am 10. April 2013 (englisch).
- ↑ Stephen Wolfram: Statistical mechanics of cellular automata. In: Rev. Mod. Phys. 55. Jahrgang, Nr. 3, 1983, S. 601–644, doi:10.1103/RevModPhys.55.601, bibcode:1983RvMP...55..601W (englisch).
- ↑ Random Number Generation. In: Wolfram Mathematica 8 Documentation. Abgerufen am 31. Dezember 2011 (englisch).
- ↑ Stephen Wolfram: Cryptography with cellular automata. Conference on the Theory and Application of Cryptographic Techniques. In: Proceedings of Advances in Cryptology - CRYPTO '85. Lecture Notes in Computer Science 218, Springer-Verlag, 1985, S. 429, doi:10.1007/3-540-39799-X_32 (englisch).
- ↑ Willi Meier, Othmar Staffelbach: Analysis of pseudo random sequences generated by cellular automata. Workshop on the Theory and Application of of Cryptographic Techniques. In: Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547, Springer-Verlag, 1991, S. 186, doi:10.1007/3-540-46416-6_17 (englisch).