Regula 30

Rule 30 ( English  Rule 30 ) este un automat celular elementar , adică un automat celular unidimensional cu două stări (0 și 1), descris pentru prima dată de Stephen Wolfram în 1983 [2] . Stephen Wolfram spune că „aceasta este regula lui preferată” și o descrie în detaliu în cartea sa A New Kind of Science . Dintre cele patru comportamente descrise în această carte, Regula 30 are clasa de comportament III, arătând un comportament aperiodic, haotic .

Regula este interesantă deoarece generează structuri complexe, în multe privințe aleatorii, din reguli simple, bine definite. Wolfram consideră că automatele celulare în general, și Regula 30 în special, sunt cheia pentru înțelegerea modului în care regulile simple pot genera structuri complexe și diferite comportamente complexe ale diferitelor obiecte naturale. De exemplu, o structură similară cu cea generată de Regula 30 poate fi găsită pe coaja textilului larg răspândit de scoici tropicale Conus . Regula 30 este, de asemenea, folosită ca generator de numere pseudo-aleatoare (PRNG) în Wolfram Research  's Mathematica [3] . De asemenea, această regulă a fost propusă pentru utilizare ca codificator de secvență în criptografie [4] .

Cu toate acestea, M. Sipper și M. Tomassini au arătat că, la fel ca regula PRNG 30, are rezultate slabe la testul de bunătate a potrivirii Pearson (testul χ²) în comparație cu alte secvențe pseudo-aleatoare care au fost obținute folosind alte automate celulare .

Regula 30 este numită așa deoarece 30 este cel mai mic cod pentru descrierea regulii de comportament a lui Wolfram din 1983 pentru automatele celulare. codurile de sistem de numere zecimale 120, 225 și, respectiv, 135.

Descrierea regulii

Este considerată o matrice infinită unidimensională de celule (celule) ale unui automat celular cu două stări posibile. Fiecare dintre celule are o stare inițială . La momente discrete de timp, fiecare celulă își schimbă starea, iar această stare depinde de starea anterioară a acestei celule și de starea anterioară a două celule învecinate - celule învecinate. Pentru Regula 30, tabelul oferă regulile pentru tranziția celulei centrale a triadei la următoarea stare și, pentru comparație, sunt date regulile 120, 225 și 135.

Numerele binare 11110 2 = 30 10 , 1111000 2 = 120 10 , 11100001 2 = 225 10 , 10000111 2 = 135 10 , motiv pentru care aceste reguli, conform lui Wolfram, se numesc regulile 2251203, respectiv 0 22 51203.

Structură și proprietăți

Având în vedere diferite stări inițiale ale celulelor, regula 30 dă naștere la diferite evoluții ale generațiilor ulterioare de celule.

De exemplu, este dată evoluția conform Regulii 30, a cărei stare inițială este doar o celulă neagră înconjurată de celule albe. (Se presupune că o celulă neagră corespunde unei singure stări de celulă conform tabelului).

Evoluția unei singure celule în timp conform regulii celor 30

În această imagine, timpul este reprezentat de-a lungul axei verticale, fiecare strat orizontal reflectând starea tuturor celulelor automatului celular de generație în timpul evoluției Regulii 30. În imagine pot fi observate mai multe caracteristici, cum ar fi apariția frecventă a triunghiurilor albe de diferite dimensiuni, care seamănă cu forma unei pate pe o coajă de scoici și cu o structură regulată clară în partea stângă a imaginii. Cu toate acestea, structura generală a desenului nu se pretează la o descriere generală obișnuită. Numărul de celule negre din generațiile ulterioare de evoluție a automatelor este secvența:

și crește aproximativ ca  - numărul generației.

După cum se poate observa din figură, Regula 30 generează o secvență care pare a fi aleatorie în multe feluri, având în vedere condițiile inițiale care nu sunt aleatoare. Stephen Wolfram a propus utilizarea barelor verticale în evoluția automatelor celulare pentru o anumită stare inițială dată ca o secvență pseudo-aleatorie. Secvențele obținute în acest fel trec multe dintre testele standard de aleatorie . Stephen Wolfram folosește regula lui 30 pentru a genera numere întregi aleatorii în pachetul Mathematica .

Regula 30 produce structuri aleatorii pe multe seturi de condiții inițiale. Cu toate acestea, există și un număr infinit de vectori de condiție inițială care generează structuri periodice în evoluție. Un exemplu banal este vectorul de condiție inițială , constând numai din celule albe (0). Un exemplu mai puțin trivial găsit de Matthew Cook  este orice succesiune infinită constând din repetări ale modelului 00001000111000 , posibil separate de șase 1. Mai multe dintre aceste modele au fost găsite de Frans Faase și sunt prezentate aici Arhivat 8 august 2013 la Wayback Machine .

Haos determinist

Wolfram a sugerat caracterul aleatoriu al evoluției conform Regulii 30, bazându-se în principal pe forma sa grafică externă. Cu toate acestea, aplicarea regulii 30 s-a dovedit mai târziu că satisface definițiile mai stricte ale haosului formulate de Devaney și Knudson. În conformitate cu criteriul Devaney, Regula 30 demonstrează efectul fluture  - (dacă specificați 2 stări inițiale care diferă, de exemplu, doar de un bit , atunci descendenții acestor 2 stări îndepărtate de multe generații vor fi complet diferiți), periodic configurațiile sunt dense în spațiul tuturor configurațiilor topologiei Cantor . De asemenea, regula 30 are proprietatea de amestecare . Conform criteriului Knudson, acesta arată sensibilitatea la condițiile inițiale și densitatea orbitelor procesului (orice configurație duce în cele din urmă la apariția tuturor configurațiilor posibile ale celulelor finale). Ambele caracteristici ale comportamentului haotic al evoluției regulii 30 rezultă dintr-o proprietate a regulii 30 care este ușor de verificat: dacă două configurații C și B diferă cu o celulă la poziția i , atunci după un pas noile configurații vor diferi la celulă. i + 1 [5] .

Galerie

• Etapele inițiale în evoluția regulii 30

• 2000 de pași de evoluție Regula 30

• Aproximativ 15.000 de pași în evoluția regulii 30

• Structuri periodice în timpul evoluției

• Evoluție în condiții inițiale aleatorii

Link -uri

• Regula 30: Generatorul de biți pseudo-aleatoriu al lui Wolfram Arhivat pe 11 septembrie 2019 la Wayback Machine . Rețeta 32 la Primordial Soup Kitchen a lui David Griffeath.
• Weisstein, Eric W. Regula 30  (engleză) pe site-ul web Wolfram MathWorld .
• Se repetă tiparele regulii 30 Arhivat la 8 august 2013 la Wayback Machine . O listă de condiții inițiale a căror evoluție are ca rezultat secvențe repetate. Frans Faase, 2003.
• Paving Mosaic Fractal Arhivat 10 mai 2012 la Wayback Machine . Informații de bază despre structura regulii 30 de Olivier Schmidt-Chevalier.
• Februarie 2010 TED Talk Arhivat 16 mai 2012 la Wayback Machine . Steven Wolfram vorbește despre teoria cunoașterii computabile, Regula 30 și multe altele.
• Premiile Wolram Rule 30 Arhivate 4 octombrie 2019 la Wayback Machine . Mai multe întrebări despre proprietățile regulii 30, pentru soluția cărora Wolfram a numit bonusuri.

Vezi și

• Teoria haosului
• Regula 110
• Regula 184
• Automat celular ciclic

Note

1. ↑ Stephen Coombes. Geometria și pigmentarea scoicilor . www.maths.nottingham.ac.uk . Universitatea din Nottingham (februarie 2009). Consultat la 10 aprilie 2013. Arhivat din original la 18 septembrie 2016. (nedefinit)
2. ↑ Wolfram, S. Statistical mechanics of cellular automata  ,  Rev. Mod. Fiz.  : jurnal. - 1983. - Vol. 55 , nr. 3 . - P. 601-644 . - doi : 10.1103/RevModPhys.55.601 . - Cod biblic .
3. ↑ Generarea numerelor aleatorii . Wolfram Mathematica 8 Documentație . Data accesului: 31 decembrie 2011. Arhivat din original pe 2 septembrie 2013. (nedefinit)
4. ↑ Wolfram, S. (1985). „Criptografie cu automate celulare” . Proceedings of Advances in Cryptology - CRYPTO '85 . Note de curs în informatică 218, Springer-Verlag. p. 429. (link indisponibil) . Vezi și: Meier, Willi; Staffelbach, Othmar (1991). „Analiza secvențelor pseudoaleatoare generate de automatele celulare” . Progrese în criptologie: Proc. Workshop de Teoria și Aplicarea Tehnicilor Criptografice, EUROCRYPT '91 . Note de curs în informatică 547, Springer-Verlag. p. 186. (link indisponibil)
5. ↑ Cattaneo, Gianpiero; Finelli, Michele; Margara, Luciano. Investigarea haosului topologic prin dinamica automatelor celulare elementare  (engleză)  // Teoretică Informatică: jurnal. - 2000. - Vol. 244 , nr. 1-2 . - P. 219-241 . - doi : 10.1016/S0304-3975(98)00345-4 .