Wolfram-kod
Wolfram-kod är ett allmänt använt numreringssystem för endimensionella cellulära automatregler , introducerat av Stephen Wolfram i en tidning från 1983 och populär i hans bok A New Kind of Science .
Koden är baserad på observationen att en tabell som specificerar det nya tillståndet för varje cell i automaten, som en funktion av tillstånden i dess närhet, kan tolkas som ett k-siffrigt tal i det S -ära positionsnummersystemet, där S är antalet tillstånd som varje cell i automaten kan ha, k = S 2 n + 1 är antalet grannskapskonfigurationer och n är radien för grannskapet. Således är Wolfram-koden för en viss regel ett tal i intervallet från 0 till S S 2 n + 1 − 1, omvandlat från S -är till decimalnotation . Det kan beräknas enligt följande:
- Lista alla S 2 n + 1 möjliga tillståndskonfigurationer för grannskapet av en given cell.
- Tolka varje konfiguration som ett nummer enligt beskrivningen ovan, sortera dem i fallande numerisk ordning.
- För varje konfiguration, lista tillståndet som den givna cellen kommer att ha, enligt denna regel, vid nästa iteration.
- Tolka den resulterande listan med tillstånd igen som ett S -är tal, och konvertera detta tal till decimal. Det resulterande decimaltalet är Wolfram-koden.
Wolfram-koden specificerar inte storleken (eller formen) av grannskapet, inte heller antalet stater - dessa antas vara kända från sammanhanget. När de används på egen hand utan ett sådant sammanhang, antas koderna ofta hänvisa till klassen av elementära cellulära automater , tvåtillstånds endimensionella cellulära automater med ett (sammanhängande) trecellskvarter, vilket Wolfram undersöker utförligt i sin bok. Anmärkningsvärda regler i den här klassen inkluderar regel 30 , regel 110 och regel 184 . Regel 90 är också intressant eftersom den skapar Pascals triangel modulo 2. En kod av denna typ med suffix med ett R, såsom "Regel 37R", indikerar en andra ordningens cellulär automat med samma grannskapsstruktur.
Medan i strikt mening varje Wolfram-kod i det giltiga intervallet definierar en annan regel, är vissa av dessa regler isomorfa och anses vanligtvis vara likvärdiga. Till exempel är regel 110 ovan isomorf med reglerna 124, 137 och 193, som kan erhållas från originalet genom vänster-högerreflektion och genom att numrera om tillstånden. Enligt konventionen representeras varje sådan isomorfismklass av regeln med det lägsta kodnumret i den. En nackdel med Wolfram-notationen, och användningen av decimalnotation i synnerhet, är att den gör sådana isomorfismer svårare att se än vissa alternativa notationer. Trots detta har det blivit det de facto standardsättet att referera till endimensionella cellulära automater.
Generaliserade cellulära automater
Antalet möjliga regler, R , för en generaliserad cellulär automat där varje cell kan anta ett av S- tillstånd som bestäms av en grannskapsstorlek på n , i ett D -dimensionellt utrymme ges av: R=S S (2n+1) ) D
Det vanligaste exemplet har S = 2 , n = 1 och D = 1 , vilket ger R = 256 . Antalet möjliga regler är extremt beroende av systemets dimensionalitet. Om du till exempel ökar antalet dimensioner ( D ) från 1 till 2 ökar antalet möjliga regler från 256 till 2 512 (vilket är ~1,341×10 154 ).