Regel 30: Unterschied zwischen den Versionen
- Seiten mit Skriptfehlern
- Wikipedia:Vorlagenfehler/Vorlage:Cite journal/Parameter language fehlt
- Automatentheorie
- Dynamisches System
imported>Debenben K (HC: Entferne Kategorie:Dynamisches System (Physik); Ergänze Kategorie:Dynamisches System) |
imported>Kein Einstein K (HC: Entferne Kategorie:Biophysik) |
||
| Zeile 1: | Zeile 1: | ||
[[Datei:Textile cone.JPG|mini|Die Schneckenhäuser des [[Weberkegel]]s weisen das Muster der Regel 30 auf.<ref>{{cite web|url=https://www.maths.nottingham.ac.uk/personal/sc/pdfs/Seashells09.pdf|title=The Geometry and Pigmentation of Seashells|author=Stephen Coombes|year=2009|month=Februar|work=maths.nottingham.ac.uk|publisher=[[University of Nottingham]]|accessdate=2013-04-10|format=PDF; 3,3 MB}}</ref>]] | [[Datei:Textile cone.JPG|mini|Die Schneckenhäuser des [[Weberkegel]]s weisen das Muster der Regel 30 auf.<ref>{{cite web|url=https://www.maths.nottingham.ac.uk/personal/sc/pdfs/Seashells09.pdf|title=The Geometry and Pigmentation of Seashells|author=Stephen Coombes|year=2009|month=Februar|work=maths.nottingham.ac.uk|publisher=[[University of Nottingham]]|accessdate=2013-04-10|format=PDF; 3,3 MB}}</ref>]] | ||
'''Regel 30''' ({{enS|''Rule 30''}}) ist ein eindimensionaler [[zellulärer Automat]], der 1983 von [[Stephen Wolfram]] entdeckt wurde.<ref>{{cite journal|author=Stephen Wolfram|title=Statistical mechanics of cellular automata|journal=Rev. Mod. Phys.|volume=55|pages=601–644|year=1983|doi=10.1103/RevModPhys.55.601|bibcode=1983RvMP...55..601W|issue=3}}</ref> 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 [[Zellulärer_Automat#Einteilung|Wolframs Klassifikationsschema]] gehört dieser zelluläre Automat der „Klasse 3“ an, was bedeutet, dass er | '''Regel 30''' ({{enS|''Rule 30''}}) ist ein eindimensionaler [[zellulärer Automat]], der 1983 von [[Stephen Wolfram]] entdeckt wurde.<ref>{{cite journal|author=Stephen Wolfram|title=Statistical mechanics of cellular automata|journal=Rev. Mod. Phys.|volume=55|pages=601–644|year=1983|doi=10.1103/RevModPhys.55.601|bibcode=1983RvMP...55..601W|issue=3}}</ref> 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 [[Zellulärer_Automat#Einteilung|Wolframs Klassifikationsschema]] gehört dieser zelluläre Automat der „Klasse 3“ an, was bedeutet, dass er nichtperiodisches, [[Chaosforschung|chaotisches]] Verhalten zeigt. | ||
== Beschreibung == | == Beschreibung == | ||
Die Regel 30 ist von besonderem Interesse, da sie komplexe, scheinbar [[Zufall|zufällige]] Strukturen hervorruft, die klare [[Umgebung (Mathematik)|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<ref>{{cite web|title=Random Number Generation|url=http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneration.html|work=Wolfram Mathematica 8 Documentation|accessdate=2011-12-31}}</ref> und eine [[Stromchiffre]] zur [[Kryptographie|Verschlüsselung von Informationen]]<ref>{{cite conference|author=Stephen Wolfram|title=Cryptography with cellular automata|date=1985|booktitle=Proceedings of Advances in Cryptology - CRYPTO '85|pages=429|publisher=Lecture Notes in Computer Science 218, Springer-Verlag| | Die Regel 30 ist von besonderem Interesse, da sie komplexe, scheinbar [[Zufall|zufällige]] Strukturen hervorruft, die klare [[Umgebung (Mathematik)|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<ref>{{cite web|title=Random Number Generation|url=http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneration.html|work=Wolfram Mathematica 8 Documentation|accessdate=2011-12-31}}</ref> und eine [[Stromchiffre]] zur [[Kryptographie|Verschlüsselung von Informationen]]<ref>{{cite conference|author=Stephen Wolfram|title=Cryptography with cellular automata|date=1985|booktitle=Proceedings of Advances in Cryptology - CRYPTO '85|pages=429|publisher=Lecture Notes in Computer Science 218, Springer-Verlag|doi=10.1007/3-540-39799-X_32}}</ref><ref>{{cite conference|author=Willi Meier, Othmar Staffelbach|title=Analysis of pseudo random sequences generated by cellular automata|booktitle=Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91|date=1991|pages=186|publisher=Lecture Notes in Computer Science 547, Springer-Verlag|doi=10.1007/3-540-46416-6_17}}</ref> vorgeschlagen. Jedoch wurde gezeigt, dass andere zelluläre Automaten zur Verschlüsselung besser geeignet sind. | ||
== Definition == | == Definition == | ||
| Zeile 50: | Zeile 50: | ||
[[Kategorie:Automatentheorie]] | [[Kategorie:Automatentheorie]] | ||
[[Kategorie:Dynamisches System]] | [[Kategorie:Dynamisches System]] | ||
Aktuelle Version vom 2. August 2021, 16:12 Uhr
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
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
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 $ 2^{3}=8 $ 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 $ 2^{8}=256 $ 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
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 $ n $ beschreibt die Folge
- $ 1,3,3,6,4,9,5,12,7,12,11,14,12,19,13,22,15,19 $ (Sequenz Folge A070952 in OEIS)
und ist ungefähr gleich $ n $.
Chaos
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
- Eric W. Weisstein: Rule 30. In: MathWorld (englisch).
- Regel 30 in Wolfram's Atlas of Cellular Automata (englisch)
Einzelnachweise
- ↑ 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.
- ↑ 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.
- ↑ Random Number Generation. In: Wolfram Mathematica 8 Documentation. Abgerufen am 31. Dezember 2011.
- ↑ Stephen Wolfram: Cryptography with cellular automata. In: Proceedings of Advances in Cryptology - CRYPTO '85 . Lecture Notes in Computer Science 218, Springer-Verlag, S. 429. doi:10.1007/3-540-39799-X_32
- ↑ Willi Meier, Othmar Staffelbach: Analysis of pseudo random sequences generated by cellular automata. In: Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91 . Lecture Notes in Computer Science 547, Springer-Verlag, S. 186. doi:10.1007/3-540-46416-6_17