Sääntö 184

Sääntö 184 ( eng.  Rule 184 ) on alkeissolukkoautomaatti , eli yksiulotteinen soluautomaatti , jossa on kaksi tilaa (0 ja 1).

Määritelmä

Soluautomaatin tila saadaan lineaarisella solujoukolla, joista jokainen sisältää binaariarvon (0 tai 1). Jokaisessa kehitysvaiheessa sääntöä (tässä tapauksessa sääntöä 184) sovelletaan samanaikaisesti jokaiseen taulukon soluun ja se määrittää sen uuden tilan seuraavasti:

Tämän taulukon merkintä määrittää kunkin solun uuden tilan kyseisen solun ja sen kahden vasemmalla ja oikealla olevan naapurin edellisen tilan mukaan.

Säännön nimi on annettua taulukkoa kuvaava Wolfram-koodi : taulukon alarivi (10111000) binääristä desimaaliin käännettynä antaa 8 + 16 + 32 + 128 = 184.

Sääntöä 184 voidaan kuvata intuitiivisesti useilla eri tavoilla:

• Jokaisessa vaiheessa tyypin 10 tilaparit muutetaan tyypin 01 pareiksi. Tämän kuvauksen perusteella Crag ja Spon (1984) viittaavat sääntöön 184 "kineettisen Ising-mallin , jolla on epäsymmetrinen spin-vaihtodynamiikka" deterministisenä versiona.

• Jokaisessa vaiheessa tilan 1 solu, jonka oikealla puolella on tilassa 0 ("vapaa tila") oleva solu, siirtyy oikealle vapauttaen varatun tilan. Tämä kuvaus vastaa liikennevirtojen simulointiin liittyvää sovellusta.

• Jos solu on tilassa 0, sen uusi tila otetaan solusta sen vasemmalle puolelle. Muussa tapauksessa sen tila otetaan sen oikealla puolella olevasta solusta. Toisin sanoen jokainen solu voidaan toteuttaa multiplekserin avulla ja se muistuttaa toiminnaltaan Fredkin-porttia [1] .

Evoluutio

Sääntöjen kuvauksesta voidaan päätellä kaksi sääntöjen dynamiikkaan liittyvää ominaisuutta. Ensinnäkin säännön 184 mukaisen äärellisen solujoukon evoluution aikana automaatissa, jossa on jaksolliset reunaehdot , solujen lukumäärä tilassa 1 (ja 0) pysyy muuttumattomana. Jos tilassa 1 olevien solujen jakautumistiheys määritetään äärettömän pituisten solujen joukossa, se pysyy myös muuttumattomana evoluution aikana [2] .

Toiseksi, vaikka sääntö 184 ei ole symmetrinen vasemman ja oikean suunnan käänteisyyden suhteen, sillä on seuraava symmetria: vasemman ja oikean suunnan käänteinen roolien 1 ja 0 samanaikainen kääntäminen johtaa samoihin evoluution sääntöihin.

Automaatissa, jossa on sääntö 184, kuviot (solujen tilojen sekvenssit) yleensä stabiloituvat nopeasti, mikä johtaa tilasarjaan, joka liikkuu jompaankumpaan kahdesta suunnasta [3] .

• Jos "ykkösten" alkutiheys on alle 50%, evoluution seurauksena ilmaantuu oikealle liikkuvia " ykkösten " ryhmiä "nollalla" erotettuina; klusterit erotetaan "nollien" lohkoilla.
• Jos alkutiheys on suurempi kuin 50 %, näyte kehittyy "nollien" ryhmiksi, jotka liikkuvat vasemmalle ja erotetaan "ykkösillä"; klusterit erotetaan "ykkösten" ryhmillä.
• Jos alkutiheys on 50 %, näyte stabiloituu hitaammin vuorottelevien "ykkösten" ja "nollien" sarjaksi, jonka voidaan katsoa liikkuvan vasemmalle tai oikealle yhtä menestyksekkäästi.

Sääntö 184 mallina

Sääntö 184 antaa meille mahdollisuuden ratkaista tiheysluokitusongelman ja kuvata useita näennäisesti erilaisia ​​hiukkasjärjestelmiä :

• Sääntöä 184 voidaan käyttää yksinkertaisena liikennevirtamallina yksikaistaisella moottoritiellä, ja se on monien mikroskooppisten liikennevirtamallien taustalla . Ajoneuvoja edustavat hiukkaset liikkuvat samaan suuntaan, pysähtyvät ja alkavat liikkua suoraan edessä olevien autojen "tilasta" riippuen. Hiukkasten määrä pysyy muuttumattomana koko simulaation ajan. Tämän hakemuksen yhteydessä sääntöä 184 kutsutaan myös "tiesäännöksi" [4] .

• Aerosolifysiikassa sääntöä 184 käytetään simuloimaan hiukkasten laskeutumista epäsäännölliselle pinnalle, jossa seuraavassa simulointivaiheessa pinnan jokainen paikallinen minimi täytetään hiukkasella. Simuloinnin aikana hiukkasten määrä kasvaa; sijoitettu hiukkanen ei liiku.

• Sääntö 184 -automaattia voidaan tarkastella ballistisen tuhoamisen yhteydessä yksiulotteisessa ympäristössä vasemmalle ja oikealle liikkuvana hiukkasjärjestelmänä. Kun kaksi hiukkasta törmäävät, ne tuhoavat toisensa niin, että jokaisessa vaiheessa hiukkasten lukumäärä pysyy samana tai pienenee.

Näennäiset ristiriidat näiden kuvausten välillä ratkaistaan ​​erolla tavoissa, joilla soluautomaatin ominaisuuksien ja ongelman elementtien välistä suhdetta määritetään.

Ensimmäiset sääntöä 184 koskevat tutkimukset näyttävät tehneen Lee (1987) ja Krug ja Spon (1988). Erityisesti Krug ja Spon kuvasivat kaikki kolme tyyppiä 184-säännöllä mallinnettuja hiukkasjärjestelmiä [5] .

Muistiinpanot

1. ↑ Li (1992).
2. ↑ Boccara ja Fukś (1998) ja Moreira (2003) tutkivat yleisempää luokkaa soluautomaatteja, joilla on samanlaiset säilymislait .
3. ↑ Li (1987).
4. ↑ Katso esimerkiksi Fuks (1997).
5. ↑ Monissa myöhemmissä teoksissa viitattaessa sääntöön 184 viitataan Stephen Wolframin varhaisiin artikkeleihin , joissa on kuitenkin otettu huomioon vain automaatit, jotka ovat symmetrisiä vasemman ja oikean suunnan muutoksen ja siten säännön 184 suhteen. ei otettu huomioon.

Kirjallisuus

• Fuks, Henryk. Tiheysluokitusongelman ratkaisu kahdella samankaltaisella soluautomaattisäännöllä  (englanniksi)  // Physical Review E  : journal. - 1997. - Voi. 55 , nro. 3 . - P.R2081-R2084 . - doi : 10.1103/PhysRevE.55.R2081 . - .
• Fuks, Henryk; Boccara, Nino. Yleiset deterministiset liikennesäännöt  (uuspr.)  // Journal of Modern Physics C. - 1998. - V. 9 , No. 1 . - S. 1-12 . - doi : 10.1142/S0129183198000029 . — . Arkistoitu alkuperäisestä 27. syyskuuta 2007.
• Li, Wentian. Säännöllisten kielten ja soluautomaattien tehospektrit  (englanti)  // Complex Systems: Journal. - 1987. - Voi. 1 . - s. 107-130 . Arkistoitu alkuperäisestä 7. lokakuuta 2007.
• Li, Wentian. Ei-paikallisten soluautomaattien fenomenologia  //  Journal of Statistical Physics : päiväkirja. - 1992. - Voi. 68 , no. 5-6 . - s. 829-882 ​​. - doi : 10.1007/BF01048877 . - .
• Moreira, Andres. Numeroa säilyttävien soluautomaattien yleisyys ja ratkeavuus  (englanniksi)  // Theoretical Computer Science: Journal. - 2003. - Voi. 292 , nro. 3 . - s. 711-721 . - doi : 10.1016/S0304-3975(02)00065-8 . - arXiv : nlin.CG/0306032 .

Linkit

• Sääntö 184 arkistoitu 30. lokakuuta 2010 Wayback Machinessa Stephen Wolframin atlasissa
• Java Simulator Arkistoitu 3. syyskuuta 2010 Wayback Machinessa (simulaatio solujen rengasjoukolla, taulukon pituus on kiinteä, sääntö 184 on asetettu oletuksena)