Regel 30

Regel 30 ( engelsk  Rule 30 ) er en elementær cellulær automat , det vil sige en endimensionel cellulær automat med to tilstande (0 og 1), først beskrevet af Stephen Wolfram i 1983 [2] . Stephen Wolfram siger "dette er hans yndlingsregel" og beskriver det i detaljer i sin bog A New Kind of Science . Af de fire adfærd, der er beskrevet i denne bog, har Regel 30 adfærdsklasse III, der viser aperiodisk, kaotisk adfærd .

Reglen er interessant, fordi den genererer komplekse, på mange måder tilfældige strukturer ud fra simple, veldefinerede regler. Wolfram mener, at cellulære automater generelt, og regel 30 i særdeleshed, er nøglen til at forstå, hvordan simple regler kan generere komplekse strukturer og forskellige komplekse adfærdsmønstre for forskellige naturlige objekter. For eksempel kan en struktur, der ligner den, der genereres af Regel 30, findes på skallen af ​​den udbredte tropiske musling Conus-tekstil . Regel 30 bruges også som en pseudo-tilfældig talgenerator (PRNG) i Wolfram Research  's Mathematica [3] . Denne regel blev også foreslået til brug som en sekvenskoder i kryptografi [4] .

M. Sipper og M. Tomassini viste imidlertid, at den ligesom PRNG- regel 30 klarer sig dårligt på Pearsons godhedstesten (χ²-testen) sammenlignet med andre pseudo-tilfældige sekvenser, der blev opnået ved hjælp af andre cellulære automater .

Regel 30 kaldes så, fordi 30 er den mindste kode til at beskrive Wolframs adfærdsregel fra 1983 for cellulære automater.

Beskrivelse af reglen

En uendelig endimensionel række af celler (celler) i en cellulær automat med to mulige tilstande betragtes. Hver af cellerne har en begyndelsestilstand . På diskrete tidspunkter ændrer hver celle sin tilstand, og denne tilstand afhænger af den tidligere tilstand af denne celle og den tidligere tilstand af to naboceller - naboceller. For regel 30 giver tabellen reglerne for overgangen af ​​treklangens centrale celle til den næste tilstand, og til sammenligning er der givet reglerne 120, 225 og 135.

Binære tal 11110 2 = 30 10 , 1111000 2 = 120 10 , 11100001 2 = 225 10 , 10000111 2 = 135 10 , derfor kaldes disse regler ifølge Wolfram 3, 52 respektiv reglerne 3, 2 og 5 respektiv.

Struktur og egenskaber

Givet forskellige begyndelsestilstande af celler, giver regel 30 anledning til forskellige udviklinger af efterfølgende generationer af celler.

For eksempel er udviklingen i henhold til regel 30 givet, hvis begyndelsestilstand kun er en sort celle omgivet af hvide celler. (Det antages, at en sort celle svarer til en enkelt celletilstand ifølge tabellen).

Udvikling af en enkelt celle i tid i henhold til reglen om 30

I dette billede er tiden plottet langs den lodrette akse, idet hvert vandrette lag afspejler tilstanden af ​​alle celler i generationens cellulære automat under udviklingen af ​​regel 30. Flere funktioner kan ses i billedet, såsom den hyppige fremkomst af hvide trekanter af forskellige størrelser, som ligner formen af ​​en plet på en muslingeskal og en tydelig regulær struktur i venstre side af billedet. Tegningens generelle struktur egner sig dog ikke til en generel almindelig beskrivelse. Antallet af sorte celler i efterfølgende generationer af automate-evolution er sekvensen:

og tilnærmelsesvis stiger som  - generationstallet.

Som det kan ses af figuren, genererer Regel 30 en sekvens, der ser ud til at være tilfældig på mange måder, givet begyndelsesbetingelser, der ikke er tilfældige. Stephen Wolfram foreslog brugen af ​​lodrette streger i udviklingen af ​​cellulære automater for en given begyndelsestilstand som en pseudo-tilfældig sekvens. Sekvenser opnået på denne måde består mange af standardtestene for tilfældighed . Stephen Wolfram bruger 30-reglen til at generere tilfældige heltal i Mathematica -pakken .

Regel 30 producerer tilfældige strukturer på mange sæt begyndelsesbetingelser. Der er dog også et uendeligt antal starttilstandsvektorer, der genererer periodiske strukturer i evolution. Et trivielt eksempel er starttilstandsvektoren , der kun består af hvide blodlegemer (0). Et mindre trivielt eksempel fundet af Matthew Cook  er enhver uendelig sekvens bestående af gentagelser af mønsteret 00001000111000 , muligvis adskilt af seks 1'ere. Flere af disse mønstre blev fundet af Frans Faase og præsenteres her Arkiveret 8. august 2013 på Wayback Machine .

Deterministisk kaos

Wolfram foreslog evolutionens tilfældighed i henhold til regel 30, hovedsageligt baseret på dens eksterne grafiske form. Imidlertid blev anvendelsen af ​​Regel 30 senere vist at tilfredsstille de strengere definitioner af kaos formuleret af Devaney og Knudson. I overensstemmelse med Devaney-kriteriet demonstrerer Regel 30 sommerfugleeffekten  - (hvis du angiver 2 begyndelsestilstande, der f.eks. kun afviger med en bit , så vil efterkommerne af disse 2 stater, der er fjernt i mange generationer, være helt forskellige), periodisk konfigurationer er tætte i rummet af alle konfigurationer af Cantor - topologien . Regel 30 har også blandingsegenskaben . Ifølge Knudson-kriteriet viser dette følsomheden over for startbetingelser og tætheden af ​​processens kredsløb (enhver konfiguration fører til sidst til fremkomsten af ​​alle mulige endelige cellekonfigurationer). Begge disse karakteristika ved den kaotiske adfærd i regel 30-evolutionen følger af en egenskab i regel 30, som er let at verificere: hvis to konfigurationer C og B adskiller sig med én celle ved position i , vil de nye konfigurationer efter et trin adskille sig ved celle i + 1 [5] .

Galleri

• Indledende trin i udviklingen af ​​regel 30

• 2000 udviklingstrin Regel 30

• Cirka 15.000 trin i udviklingen af ​​Regel 30

• Periodiske strukturer under evolution

• Evolution under tilfældige begyndelsesbetingelser

Links

• Regel 30: Wolframs pseudo-tilfældige bitgenerator arkiveret 11. september 2019 på Wayback-maskinen . Opskrift 32 på David Griffeaths Primordial Soup Kitchen.
• Weisstein, Eric W. Regel 30  (engelsk) på Wolfram MathWorld- webstedet .
• Gentagelse af regel 30-mønstre Arkiveret 8. august 2013 på Wayback-maskinen . En liste over begyndelsesbetingelser, hvis udvikling resulterer i gentagne sekvenser. Frans Faase, 2003.
• Paving Mosaic Fractal Arkiveret 10. maj 2012 på Wayback Machine . Grundlæggende information om strukturen i Regel 30 af Olivier Schmidt-Chevalier.
• Februar 2010 TED Talk Arkiveret 16. maj 2012 på Wayback Machine . Steven Wolfram taler om beregningsbar videnteori, Regel 30 og mere.
• Wolram Rule 30-præmierne arkiveret 4. oktober 2019 på Wayback Machine . Adskillige spørgsmål om egenskaberne af regel 30, for hvilken løsning Wolfram udpegede bonusser.

Se også

• Kaosteori
• Regel 110
• Regel 184
• Cyklisk cellulær automat

Noter

1. ↑ Stephen Coombes. Muslingeskallenes geometri og pigmentering . www.maths.nottingham.ac.uk . University of Nottingham (februar 2009). Hentet 10. april 2013. Arkiveret fra originalen 18. september 2016. (ubestemt)
2. ↑ Wolfram, S. Statistical mechanics of cellular automata  ,  Rev. Mod. Phys.  : journal. - 1983. - Bd. 55 , nr. 3 . - s. 601-644 . - doi : 10.1103/RevModPhys.55.601 . - .
3. ↑ Generering af tilfældige tal . Wolfram Mathematica 8 Dokumentation . Dato for adgang: 31. december 2011. Arkiveret fra originalen 2. september 2013. (ubestemt)
4. ↑ Wolfram, S. (1985). "Kryptografi med cellulære automater" . Proceedings of Advances in Cryptology - CRYPTO '85 . Lecture Notes in Computer Science 218, Springer-Verlag. s. 429. (utilgængeligt link) . Se også: Meier, Willi; Staffelbach, Othmar (1991). "Analyse af pseudo-tilfældige sekvenser genereret af cellulære automater" . Fremskridt inden for kryptologi: Proc. Workshop om teori og anvendelse af kryptografiske teknikker, EUROCRYPT '91 . Lecture Notes in Computer Science 547, Springer-Verlag. s. 186. (utilgængeligt link)
5. ↑ Cattaneo, Gianpiero; Finelli, Michele; Margara, Luciano. Undersøgelse af topologisk kaos ved elementær cellulær automatdynamik  (engelsk)  // Theoretical Computer Science: journal. - 2000. - Vol. 244 , nr. 1-2 . - S. 219-241 . - doi : 10.1016/S0304-3975(98)00345-4 .