Regel 90

Regel 90 ( eng.  Regel 90 ) är en elementär cellulär automat , det vill säga en endimensionell cellulär automat med två tillstånd, baserat på funktionen av additionsmodulo 2 (exklusivt "OR", eng.  XOR ). Namnet "Regel 90" definieras av Wolfram-koden .

Automaten består av en endimensionell array av celler, som var och en innehåller värdet 0 ("tom", "död") eller 1 ("full", "levande"). Automatens steg består i att samtidigt ersätta värdet i valfri cell med summan modulo 2 av dess två grannar [1] . Regel 90 är den enklaste icke-triviala cellulära automaten [2] . Det beskrivs i detalj i Stephen Wolframs bok A New Kind of  Science  [ 3  ] .

För den enklaste konfigurationen - vars initiala position innehåller endast en levande cell - har tidsrymddiagrammet formen av Sierpinski-triangeln . Beteendet hos vilken annan konfiguration som helst kan förklaras med modulo 2-tillägg av de enklaste konfigurationerna. I synnerhet är varje konfiguration med ett ändligt antal celler som inte är noll en replikator som gradvis fyller hela fältet med sina kopior. Om den initiala konfigurationen av regel 90 är slumpmässig, så är de efterföljande också det. Motsvarande tid-rymddiagram har många triangulära "fönster" av olika storlekar, som är resultatet av den gradvisa fyllningen av en serie med flera nollor.

Tidig utforskning av regel 90 motiverades av Gilbraith-förmodan  , ett olöst problem i talteorin relaterat till skillnaderna mellan närliggande primtal. Dessutom är Gould-sekvensen intressant ur talteoretisk synvinkel , som innehåller antalet icke-noll-celler i olika steg i den enklaste konfigurationen. Dess värden är potenser av två med exponenter lika med antalet icke-nollsiffror i den binära representationen av stegnummer (numreringen börjar från 0).

Varje konfiguration av Regel 90 har exakt fyra föregångare, så till skillnad från många andra cellulära automater som Game of Life , har denna automat inte en Edens trädgård , en konfiguration utan föregångare. Regel 90 är således en cellulär automat som är surjektiv (varje konfiguration har en föregångare) men inte injektiv (det finns konfigurationer som leder till samma i nästa steg), och ger således ett motexempel till den omvända satsen till trädgårdssatsen Eden .

Anteckningar

1. ↑ Wolfram, Stephen (1983), Statistical mechanics of cellular automata , Reviews of Modern Physics vol. 55 (3): 601–644, doi : 10.1103/RevModPhys.55.601 , < http://www.stephenwolfram.com/publications/ articles/ca/83-statistical/ > Arkiverad 21 september 2013 på Wayback Machine . 
2. ↑ Martin, Olivier; Odlyzko, Andrew M. & Wolfram, Stephen (1984), Algebraic properties of cellular automata , Communications in Mathematical Physics vol. 93 (2): 219–258, doi : 10.1007/BF01223745 , < http://www.stephenwolfram.com /publications/articles/ca/84-properties/ > Arkiverad 10 september 2012 på Wayback Machine . 
3. ↑ Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media  . Bokens alfabetiska index listar över 50 underämnen relaterade till Rule 90-maskinen.