Regel 30

Ett Conus- textilskal som till utseendet liknar regel 30.

Regel 30 är en elementär cellulär automat som introducerades av Stephen Wolfram 1983. Genom att använda Wolframs klassificeringsschema är Regel 30 en klass III-regel som visar aperiodiskt, kaotiskt beteende.

Denna regel är av särskilt intresse eftersom den producerar komplexa, till synes slumpmässiga mönster från enkla, väldefinierade regler. På grund av detta tror Wolfram att regel 30, och cellulära automater i allmänhet, är nyckeln till att förstå hur enkla regler producerar komplexa strukturer och beteenden i naturen. Till exempel visas ett mönster som liknar regel 30 på skalet av den utbredda konsnigelarten Conus textile . Regel 30 har också använts som en slumptalsgenerator i Mathematica , och har även föreslagits som ett möjligt strömchiffer för användning i kryptografi .

Regel 30 heter så eftersom 30 är den minsta Wolfram-koden som beskriver dess regeluppsättning (som beskrivs nedan). Spegelbilden, komplementet och spegelkomplementet i regel 30 har Wolfram-koderna 86, 135 respektive 149.

Regeluppsättning

I alla Wolframs elementära cellulära automater beaktas en oändlig endimensionell uppsättning av cellulära automatceller med endast två tillstånd, med varje cell i något initialt tillstånd. Med diskreta tidsintervall ändrar varje cell spontant tillstånd baserat på dess nuvarande tillstånd och tillståndet för dess två grannar. För regel 30 är regeluppsättningen som styr nästa tillstånd för automaten:

nuvarande mönster	111	110	101	100	011	010	001	000
nytt tillstånd för mittcellen	0	0	0	1	1	1	1	0

Motsvarande formel är [vänster_cell XOR (central_cell ELLER höger_cell)]. Det kallas regel 30 eftersom i binär , 00011110 ₂ = 30.

Följande diagram visar mönstret som skapas, med celler färgade baserat på det tidigare tillståndet i deras grannskap. Mörkare färger representerar "1" och ljusare färger representerar "0". Tiden ökar längs den vertikala axeln.

Struktur och egenskaper

Följande mönster framträder från ett initialt tillstånd där en enskild cell med tillstånd 1 (visas som svart) omges av celler med tillstånd 0 (vit).

Regel 30 cellulär automat

Här representerar den vertikala axeln tid och varje horisontellt tvärsnitt av bilden representerar tillståndet för alla celler i arrayen vid en specifik punkt i mönstrets utveckling. Flera motiv finns i denna struktur, såsom det frekventa utseendet av vita trianglar och ett väldefinierat randigt mönster på vänster sida; strukturen som helhet har dock inget urskiljbart mönster. Antalet svarta celler vid generation $n$ ges av sekvensen

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (sekvens A070952 i OEIS )

och är ungefär $n$ .

Kaos

Regel 30 uppfyller rigorösa definitioner av kaos som föreslagits av Devaney och Knudson. I synnerhet, enligt Devaneys kriterier, visar regel 30 ett känsligt beroende av initiala förhållanden (två initiala konfigurationer som skiljer sig endast i ett litet antal celler skiljer sig snabbt åt), dess periodiska konfigurationer är täta i utrymmet för alla konfigurationer, enligt Cantor- topologin på utrymmet av konfigurationer (det finns en periodisk konfiguration med valfritt ändligt mönster av celler), och det blandar sig (för två ändliga mönster av celler finns det en konfiguration som innehåller ett mönster som så småningom leder till en konfiguration som innehåller det andra mönstret) . Enligt Knudsons kriterier uppvisar den känsligt beroende och det finns en tät omloppsbana (en initial konfiguration som så småningom visar vilket ändligt mönster av celler som helst). Båda dessa karaktäriseringar av regelns kaotiska beteende följer av en enklare och lätt att verifiera egenskap i regel 30: den lämnas permutativ , vilket betyder att om två konfigurationer $C$ och $D$ skiljer sig åt i tillståndet för en enskild cell vid position $i$ , så efter en ett steg kommer de nya konfigurationerna att skilja sig vid cell $i + 1$ .

Ansökningar

Generering av slumptal

Som framgår av bilden ovan, genererar Regel 30 till synes slumpmässighet trots bristen på något som rimligen skulle kunna betraktas som slumpmässig input. Stephen Wolfram föreslog att använda dess mittkolumn som en pseudoslumptalsgenerator (PRNG); den klarar många standardtest för slumpmässighet, och Wolfram använde tidigare denna regel i Mathematica-produkten för att skapa slumpmässiga heltal.

Sipper och Tomassini har visat att regel 30 som en slumptalsgenerator uppvisar dåligt beteende på ett chikvadrattest när det tillämpas på alla regelkolumner jämfört med andra cellulära automatbaserade generatorer. Författarna uttryckte också sin oro över att "De relativt låga resultaten som erhålls med regel 30 CA kan bero på det faktum att vi ansåg N slumpmässiga sekvenser genererade parallellt, snarare än den enda som Wolfram betraktade."

Dekoration

Detalj av Cambridge North järnvägsstations beklädnad

Järnvägsstationen Cambridge North är dekorerad med arkitektoniska paneler som visar utvecklingen av regel 30 (eller motsvarande under svart-vit omkastning, regel 135). Designen beskrevs av dess arkitekt som inspirerad av Conways Game of Life , en annan cellulär automat som studerats av Cambridge-matematikern John Horton Conway , men är faktiskt inte baserad på Life.

Programmering

Tillståndsuppdateringen kan göras snabbt genom bitvisa operationer , om cellvärdena representeras av bitarna inom ett (eller flera) datorord. Här visas i C++ :

 
 

  
       
      0     
          
                
    
      
              
  
 #include  <stdint.h>  #include  <iostream>  int  main  ()  {  uint64_t  state  =  1u  <<  31  ;  for  (  int  i  =  ;  i  <  32  ;  ++  i  )  {  for  (  int  j  =  64  ;  j  --  ;)  {  std  ::  cout  <<  char  (  ange  >>  j  &  1  ?  'O'  :  '.'  );  }  std  ::  cout  <<  '\n'  ;  tillstånd  =  (  tillstånd  >>  1  )  ^  (  tillstånd  |  tillstånd  <<  1  );  }  }

Detta program producerar följande utdata:

................................O................. ............................ ...................................OOOO.... .......................................................................... ......OO..O............................................. ..................OO.OOOO................................ . ...........................OO..O...O............... ............ ...........................OO.OOOO.OOO...... ..........................................OO..O ....O..O................................. ................. ........OO.OOOO..OOOOOO........................ ............ ............OO..O...OOO.....O....................... . ......................OO.OOOO.OO..O...OOO................ ...... ......................OO..O....O.OOOO.OO..O...... ............... ......................OO.OOOO..OO.O....O. OOOO..................... ...........................OO..O...OOO. .OO..OO.O...O................... ...................OO .OOOO.OO..OOO.OOO..OO.OOO.................. .................. OO..O....O.OOO...O..OOO..O..O................. ......... ........OO.OOOO..OO.O..O.OOOOO..OOOOOOO................ .......... ......OO..O...OOO..OOOO.O....OOO......O............... .... ...........OO.OOOO.OO..OOO....OO..OO..O....OOO............... . .............OO..O....O.OOO..O..OO.OOO.OOOO..OO..O.......... ... ............OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO.......... .. ............OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O....... .... ...........OO.OOOO.OO..OOO...O...OO....O...OOOOO.OOO........ .. ..........OO..O....O.OOO..O.OOO.OO.O..OOO.OO.OO..O..O..... .... .........OO.OOOO..OO.O..OOO.O...O..OOOO...O..O.OO.OOOOOO...... .. ........OO..O...OOO..OOOO...OO.OOOOO...O.OOOOO.O..O.....O...... .......OO.OOOO.OO..OOO...O.OO..O....O.OO.O.....OOOOO...OOO...... ......OO..O....O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O.. ... .....OO.OOOO..OO.O..OOO.O..OO..OOO..OOOO.O.OO.O..OO.O.OOOO.... ... .OO..O...OOO..OOOO...OOOO.OO.OO..OOO....OO.OOOO..OO..O... ...OO.OOOO.OO..OOO ...O.OO....O..O.OOO..O..OO.OOOO...OOO.OO.OOO.. ..OO..O....O.OOO..O .OO.OO.OOOOO.O..OOOOOO..O...O.OO...O..O..O. .OO.OOOO..OO.O..OOO.O..O.OOOO.....OOOO.....OOOO.OO.OOOOOOOOOOOO

Se även

Wolfram, Stephen, 1985, Cryptography with Cellular Automata , CRYPTO'85.

externa länkar

Weisstein, Eric W. "Regel 30" . MathWorld .
"Tillkännage regel 30-priserna" . Stephen Wolframs skrifter . 1 oktober 2019.
Regel 30 i Wolframs atlas över cellulära automater
Regel 30: Wolframs pseudo-slumpmässiga bitgenerator . Recept 32 på David Griffeaths Primordial Soup Kitchen.
Upprepa regel 30 mönster . En lista med mönster som, när de upprepas för att fylla cellerna i en regel 30-automat, upprepar sig själva efter ändligt många tidssteg. Frans Faase, 2003. Arkiverad från originalet 2013-08-08
Stenläggning Mosaik Fractal . Grundläggande introduktion till mönstret i regel 30 ur perspektivet av en LOGO mjukvaruexpert Olivier Schmidt-Chevalier.
TED Talk från februari 2010 . Stephen Wolfram talar om att beräkna en teori om allting där han bland annat talar om regel 30.