Sääntö 90

Sääntö 90 ( eng.  Rule 90 ) on alkeissolukkoautomaatti , eli yksiulotteinen soluautomaatti , jossa on kaksi tilaa ja joka perustuu additiomodulo 2 -funktioon (yksinomainen "OR", eng.  XOR ). Nimi "Sääntö 90" määritellään Wolfram-koodilla .

Automaatti koostuu yksiulotteisesta solujoukosta, joista jokainen sisältää arvon 0 ("tyhjä", "kuollut") tai 1 ("täysi", "elossa"). Automaattivaihe koostuu minkä tahansa solun arvon samanaikaisesta korvaamisesta sen kahden naapurin summalla modulo 2 [1] . Sääntö 90 on yksinkertaisin ei-triviaali soluautomaatti [2] . Se on kuvattu yksityiskohtaisesti Stephen Wolframin kirjassa A New Kind of  Science  [ 3  ] .

Yksinkertaisimmassa konfiguraatiossa - jonka alkusijainti sisältää vain yhden elävän solun - aika-avaruuskaavio on Sierpinskin kolmion muotoinen . Minkä tahansa muun konfiguraation käyttäytyminen voidaan selittää yksinkertaisimpien konfiguraatioiden lisäämisellä modulo 2:lla. Erityisesti mikä tahansa konfiguraatio, jossa on äärellinen määrä nollasta poikkeavia soluja, on replikaattori, joka vähitellen täyttää koko kentän kopioillaan. Jos säännön 90 alkuperäinen konfiguraatio on satunnainen, niin ovat myös seuraavat. Vastaavassa aika-avaruuskaaviossa on useita erikokoisia kolmiomaisia ​​"ikkunoita", jotka ovat seurausta useiden nollien sarjan asteittaisesta täyttymisestä.

Säännön 90 varhainen tutkiminen motivoi Gilbraithin arvelua  , ratkaisematonta numeroteorian ongelmaa, joka liittyy naapurilukujen välisiin eroihin. Myös lukuteorian kannalta Gould-sekvenssi on mielenkiintoinen , joka sisältää nollasta poikkeavien solujen lukumäärän eri vaiheissa yksinkertaisimmassa konfiguraatiossa. Sen arvot ovat kahden potenssit, joiden eksponentit ovat yhtä suuria kuin nollasta poikkeavien numeroiden lukumäärä askelnumeroiden binäärimuodossa (numerointi alkaa 0:sta).

Jokaisella säännön 90 kokoonpanolla on täsmälleen neljä edeltäjää, joten toisin kuin monet muut solukkoautomaatit, kuten Game of Life , tällä automaatilla ei ole Garden of Eden -kokoonpanoa, jolla ei ole edeltäjiä. Siten sääntö 90 on soluautomaatti, joka on surjektiivinen (jokaisella konfiguraatiolla on edeltäjä), mutta ei injektiivinen (on konfiguraatioita, jotka johtavat samaan seuraavassa vaiheessa), ja tarjoaa siten vastaesimerkin puutarhalauseen käänteiselle lauseelle. Eden .

Muistiinpanot

1. ↑ Wolfram, Stephen (1983), Soluautomaattien tilastollinen mekaniikka , Reviews of Modern Physics osa 55 (3): 601–644, doi : 10.1103/RevModPhys.55.601 , < http://www.stephenwolfram.com/publications articles/ca/83-statistical/ > Arkistoitu 21. syyskuuta 2013 Wayback Machinessa . 
2. ↑ Martin, Olivier; Odlyzko, Andrew M. & Wolfram, Stephen (1984), Algebraic properties of cellular automata , Communications in Mathematical Physics osa 93 (2): 219–258, doi : 10.1007/BF01223745 , < http ://www.stephenwolfra /publications/articles/ca/84-properties/ > Arkistoitu 10. syyskuuta 2012 Wayback Machinessa . 
3. ↑ Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media  . Kirjan aakkosellinen hakemisto listaa yli 50 ala-aihetta, jotka liittyvät Rule 90 -koneeseen.