Regel 30

Regel 30

Die Schneckenhäuser des Weberkegels weisen das Muster der Regel 30 auf.[1]

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 aperiodisches, 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.

Hintereinanderausführung der Regel 30, die Zeitschritte verlaufen vertikal.

Eigenschaften des Musters

Nach einer Berechnung von sehr vielen Schritten ergibt sich das typische Muster.

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:

  1. Sie hängt hochsensibel von den Anfangswerten ab. Das heißt, dass zwei geringfügig verschiedene Anfangskonfigurationen sich sehr schnell auseinanderentwickeln (divergieren).
  2. Alle periodischen Konfigurationen sind zusammen eine dichte Teilmenge der Menge aller Konfigurationen.
  3. Sie ist topologisch transitiv auf der Menge aller Konfigurationen (sie wirbelt die Konfigurationen durcheinander).

Weblinks

 <Lang> Commons: Regel 30 – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. 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.
  2. Stephen Wolfram: Statistical mechanics of cellular automata. In: Rev. Mod. Phys.. 55, Nr. 3, 1983, S. 601–644. bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  3. Random Number Generation. In: Wolfram Mathematica 8 Documentation. Abgerufen am 31. Dezember 2011.
  4. Stephen Wolfram: Cryptography with cellular automata. In: Proceedings of Advances in Cryptology - CRYPTO '85 . Lecture Notes in Computer Science 218, Springer-Verlag, S. 429.
  5. 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.

Diese Artikel könnten dir auch gefallen



Die letzten News


28.06.2021
Quantensimulation: Messung von Verschränkung vereinfacht
Forscher haben ein Verfahren entwickelt, mit dem bisher kaum zugängliche Größen in Quantensystemen messbar gemacht werden können.
28.06.2021
Exotische Supraleiter: Das Geheimnis, das keines ist
Wie reproduzierbar sind Messungen in der Festkörperphysik? Ein Forschungsteam analysierte wichtige Messungen neu. Sie fanden heraus: Ein angeblich sensationeller Effekt existiert gar nicht.
28.06.2021
Paradoxe Wellen: Gefangene Lichtteilchen auf dem Sprung
Physikern ist es gelungen, ein neuartiges Verhalten von Lichtwellen zu beobachten, bei welchem Licht durch eine neue Art von Unordnung auf kleinste Raumbereiche begrenzt wird.
28.06.2021
Isolatoren bringen Quantenbits zum Schwitzen
Schwachleitende oder nichtleitende Materialien haben Innsbrucker Physiker als wichtige Quelle für Störungen in Ionenfallen-Quantencomputern identifiziert.
23.06.2021
Fürs Rechenzentrum: bisher kompaktester Quantencomputer
Quantencomputer waren bislang Einzelanfertigungen, die ganze Forschungslabore füllten.
17.06.2021
Helligkeitseinbruch von Beteigeuze
Als der helle, orangefarbene Stern Beteigeuze im Sternbild Orion Ende 2019 und Anfang 2020 merklich dunkler wurde, war die Astronomie-Gemeinschaft verblüfft.
17.06.2021
Das Elektronenkarussell
Die Photoemission ist eine Eigenschaft unter anderem von Metallen, die Elektronen aussenden, wenn sie mit Licht bestrahlt werden.
17.06.2021
Ultrakurze Verzögerung
Trifft Licht auf Materie geht das an deren Elektronen nicht spurlos vorüber.
17.06.2021
Entdeckung der größten Rotationsbewegung im Universum
D
13.06.2021
Die Taktgeber der Sonne
Nicht nur der prägnante 11-Jahres-Zyklus, auch alle weiteren periodischen Aktivitätsschwankungen der Sonne können durch Anziehungskräfte der Planeten getaktet sein.
13.06.2021
Wenn Schwarze Löcher den Weg für die Sternentstehung in Satellitengalaxien freimachen
Eine Kombination von systematischen Beobachtungen mit kosmologischen Simulationen hat gezeigt, dass Schwarze Löcher überraschenderweise bestimmten Galaxien helfen können, neue Sterne zu bilden.
13.06.2021
Flüssiges Wasser auf Monden sternenloser Planeten
Monde sternenloser Planeten können eine Atmosphäre haben und flüssiges Wasser speichern. Münchner Astrophysiker haben berechnet, dass die Wassermenge ausreicht, um Leben auf diesen wandernden Mond-Planeten-Systemen zu ermöglichen und zu erhalten.
13.06.2021
Solar Orbiter: Neues vom ungewöhnlichen Magnetfeld der Venus
Solar Orbiter ist eine gemeinsame Mission der Europäischen Weltraumorganisation (ESA) und der NASA, die bahnbrechende neue Erkenntnisse über die Sonne liefern wird.
13.06.2021
Quantenbits aus Löchern
Wissenschafter haben ein neues und vielversprechendes Qubit gefunden – an einem Ort, an dem es nichts gibt.
07.06.2021
Gammablitz aus der kosmischen Nachbarschaft
Die hellsten Explosionen des Universums sind möglicherweise stärkere Teilchenbeschleuniger als gedacht: Das zeigt eine außergewöhnlich detaillierte Beobachtung eines solchen kosmischen Gammastrahlungsblitzes.
31.05.2021
Verblüffendes Quantenexperiment wirft Fragen auf
Quantensysteme gelten als äußerst fragil: Schon kleinste Wechselwirkungen mit der Umgebung können zur Folge haben, dass die empfindlichen Quanteneffekte verloren gehen.
31.05.2021
Symmetrie befördert Auslöschung
Physiker aus Innsbruck zeigen in einem aktuellen Experiment, dass auch die Interferenz von nur teilweise ununterscheidbaren Quantenteilchen zu einer Auslöschung führen kann.
31.05.2021
Wie Wasser auf Eisplaneten den felsigen Untergrund auslaugt
Laborexperimente erlauben Einblicke in die Prozesse unter den extremen Druck- und Temperatur-Bedingungen ferner Welten. Fragestellung: Was passiert unter der Oberfläche von Eisplaneten?
31.05.2021
Neues Quantenmaterial entdeckt
Auf eine überraschende Form von „Quantenkritikalität“ stieß ein Forschungsteam der TU Wien gemeinsam mit US-Forschungsinstituten. Das könnte zu einem Design-Konzept für neue Materialien führen.
27.05.2021
Wenden bei Höchstgeschwindigkeit
Physiker:innen beobachten neuartige Lichtemission. und zwar wenn Elektronen in topologischen Isolatoren ihre Bewegungsrichtung abrupt umdrehen.
27.05.2021
Mit Klang die Geschichte der frühen Milchstraße erkunden
Einem Team von Astronominnen und Astronomen ist es gelungen, einige der ältesten Sterne in unserer Galaxie mit noch nie dagewesener Präzision zu datieren.
11.05.2021
Teleskop zur Erforschung von Objekten höchster Dichte im Universum
Eine internationale Gruppe von Astronomen hat erste Ergebnisse eines groß angelegten Programms vorgestellt, bei dem Beobachtungen mit dem südafrikanischen MeerKAT-Radioteleskop dazu verwendet werden, die Theorien von Einstein mit noch nie dagewesener Genauigkeit zu testen.
11.05.2021
Quantencomputing einfach erklärt
„Quantencomputing kompakt“ lautet der Titel eines aktuellen Buchs, das Bettina Just veröffentlicht hat. Die Mathematikerin und Informatikerin, die an der Technischen Hochschule Mittelhessen (THM) lehrt und forscht, behandelt darin ein Teilgebiet der Informationstechnik mit großem Entwicklungspotenzial.
11.05.2021
Auf dem Weg zum kleinstmöglichen Laser
Bei extrem niedrigen Temperaturen verhält sich Materie oft anders als gewohnt.
07.05.2021
Die Entdeckung von acht neuen Millisekunden-Pulsaren
Eine Gruppe von Astronomen hat mit dem südafrikanischen MeerKAT-Radioteleskop acht Millisekunden-Pulsare entdeckt, die sich in Kugelsternhaufen mit hoher Sterndichte befinden.