Regel 90

Regel 90 ( eng.  Rule 90 ) er en elementær cellulær automat , det vil sige en endimensionel cellulær automat med to tilstande, baseret på funktionen af ​​addition modulo 2 (eksklusiv "OR", eng.  XOR ). Navnet "Regel 90" er defineret af Wolfram-koden .

Automaten består af et endimensionelt array af celler, som hver indeholder værdien 0 ("tom", "død") eller 1 ("fuld", "levende"). Automatens trin består i den samtidige udskiftning af værdien i enhver celle med summen modulo 2 af dens to naboer [1] . Regel 90 er den enkleste ikke-trivielle cellulære automat [2] . Det er beskrevet detaljeret i Stephen Wolframs bog A New Kind of  Science  [ 3  ] .

For den enkleste konfiguration - hvis startposition kun indeholder én levende celle - har tids-rum-diagrammet formen af ​​Sierpinski-trekanten . Opførslen af ​​enhver anden konfiguration kan forklares ved modulo 2 tilføjelse af de enkleste konfigurationer. Især er enhver konfiguration med et begrænset antal ikke-nul celler en replikator, der gradvist fylder hele feltet med dets kopier. Hvis den indledende konfiguration af Regel 90 er tilfældig, så er de efterfølgende også det. Det tilsvarende tid-rum-diagram har mange trekantede "vinduer" af forskellige størrelser, der er et resultat af den gradvise udfyldning af en række af flere nuller.

Tidlig udforskning af Regel 90 var motiveret af Gilbraith-formodningen  , et uløst problem i talteori relateret til forskellene mellem naboprimtal. Også fra et talteoretisk synspunkt er Gould-sekvensen interessant , der indeholder antallet af ikke-nul-celler i forskellige trin i den enkleste konfiguration. Dens værdier er to potenser med eksponenter lig med antallet af ikke-nul cifre i den binære repræsentation af trinnumre (nummerering starter fra 0).

Enhver konfiguration af Regel 90 har præcis fire forgængere, så i modsætning til mange andre cellulære automater som Game of Life , har denne automat ikke en Edens Have , en konfiguration uden forgængere. Regel 90 er således en cellulær automat, der er surjektiv (hver konfiguration har en forgænger), men ikke injektiv (der er konfigurationer, der fører til den samme i næste trin), og giver således et modeksempel til den omvendte sætning til havesætningen Eden .

Noter

1. ↑ Wolfram, Stephen (1983), Statistical mechanics of cellular automata , Reviews of Modern Physics bind 55 (3): 601–644, doi : 10.1103/RevModPhys.55.601 , < http://www.stephenwolfram.com/publications/ articles/ca/83-statistical/ > Arkiveret 21. september 2013 på Wayback Machine . 
2. ↑ Martin, Olivier; Odlyzko, Andrew M. & Wolfram, Stephen (1984), Algebraic properties of cellular automata , Communications in Mathematical Physics bind 93 (2): 219–258, doi : 10.1007/BF01223745 , < http://www.stephenwolfram.com /publications/articles/ca/84-properties/ > Arkiveret 10. september 2012 på Wayback Machine . 
3. ↑ Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media  . Bogens alfabetiske indeks viser over 50 underemner relateret til Rule 90-maskinen.