Käännettävä soluautomaatti

Reversiibeli soluautomaatti  on soluautomaatti , jossa jokaisella tilalla on yksi edeltäjä. Se on siis säännöllinen solujen hila, joiden kunkin tila on otettu äärellisestä tilojen joukosta, ja sääntö solujen tilojen samanaikaiselle päivittämiselle naapuriensa tilojen perusteella. Käänteisyyden ehtona on, että minkä tahansa solun edellinen tila voidaan määrittää, kun tiedetään hilan kaikkien solujen päivitetyt tilat. Ajan kääntämisen jälkeen saadaan toinen reversiibeli soluautomaatti, jolla on ehkä paljon suuremmat naapurit, mutta myös sääntö solun tulevan tilan määrittämiseksi sen naapureiden nykyisten tilojen perusteella.

Reversiibelien solukkoautomaattien määrittämiseen tunnetaan useita menetelmiä, mukaan lukien lohkosoluautomaatit , joissa jokainen lohko päivitetään muista riippumatta, ja toisen asteen solukkoautomaatit , joissa solun päivityssäännön määrää automaatin kaksi aikaisempaa tilaa. Lisäksi jos automaatti määritellään sääntötaulukon avulla, sen palautuvuuden tarkistusongelma on yksiulotteisen soluautomaatin osalta ratkaistavissa , mutta yleisessä tapauksessa ratkaisematon.

Reversiibelit solukkoautomaatit määrittelevät luonnollisen mallin reversiibelille laskennalle  , teknologialle, joka mahdollistaa erittäin alhaisen virrankulutuksen laskentalaitteiden luomisen. Kvanttisoluautomaattien , jotka mahdollistavat laskelmien tekemisen kvanttimekaniikan periaatteiden avulla , oletetaan usein olevan palautuvia. Lisäksi monet fysiikan mallit, kuten ideaalikaasumolekyylien liike tai Ising-malli magneettisten varausten sijoittamisesta, ovat luonnostaan ​​palautuvia ja ne mallinnetaan palautuvilla soluautomaateilla.

Reversiibelien soluautomaattien ominaisuuksien avulla voidaan tutkia automaatteja, jotka ovat peruuttamattomia, mutta joilla on houkuttelija  , tilojen osajoukko, joihin satunnaiset alkutilat konvergoivat. Kuten Stephen Wolfram kirjoittaa , "lähestyessään attraktoria, mikä tahansa järjestelmä, jopa peruuttamaton, osoittaa joitakin ominaisuuksia, jotka ovat lähellä palautuvuutta" [1] .

Esimerkkejä

Perussolukkoautomaatit

Yksinkertaisimmilla soluautomaateilla on yksiulotteinen joukko soluja, joista jokainen sisältää 0 tai 1, kun taas solun lähialue koostuu itsestään ja yhdestä naapurista kummallakin puolella; tällaisia ​​soluautomaatteja kutsutaan alkeisautomaateiksi [2] . Jos siirtymäfunktio ei koskaan muuta solun tilaa, kääntää sen aina päinvastaiseksi, korvaa sen naapurinsa tilalla (aina sama, vasemmalla tai oikealla) tai soveltaa kahden viimeisen toiminnon yhdistelmää, niin tällainen alkeissoluautomaatti on palautuva. . Yksinkertaisuudestaan ​​huolimatta siirtymäfunktio, joka antaa kullekin solulle naapurinsa arvon, on tärkeässä roolissa symbolisessa dynamiikassa , jossa se tunnetaan siirtooperaattorina [3] .

Elementaariset soluautomaatit ovat peruuttamattomia, lukuun ottamatta edellä mainittuja triviaaleja tapauksia, joissa kunkin solun määrää vain yhden naapurinsa tila. 90-sääntö on kuitenkin lähellä reversiibeliä , jossa kunkin solun tuleva tila on sen kahden naapurin nykyisten tilojen modulo 2 -summa (tunnetaan myös nimellä XOR ) .  Vaikka sääntö 90 on peruuttamaton, kullakin sen kokoonpanolla on täsmälleen neljä edeltäjää, ja sääntö 90 on myös paikallisesti palautuva , eli millä tahansa peräkkäisten tilojen sekvenssillä on vähintään yksi edeltäjä [4] .

Muita yksiulotteisia esimerkkejä

Hieman monimutkaisempi esimerkki saadaan seuraavasti: olkoon kunkin solun tila järjestetty pari ( l , r ), ja siirtymäfunktio ottaa uuden tilan vasemman puolen vasemmanpuoleiselta naapuriltaan ja oikean puolen oikea. Tässä tapauksessa oletetaan, että vasen ja oikea osa on otettu kahdesta eri äärellisestä mahdollisten arvojen joukosta. Artikkelin alussa olevassa kuvassa on esimerkki : tilan vasen puoli on muodon muoto ja oikea puoli sen väri. Tällainen automaatti on käännettävä, koska voimme ottaa solun edellisen tilan vasemman puolen oikealta ja oikean puolen vasemmalta.

Toinen esimerkki palautuvasta yksiulotteisesta soluautomaatista, joka suorittaa kertomisen kahdella tai viidellä desimaalimuodossa . Jokainen numero tällaisessa kertolaskussa riippuu vain kahdesta edellisestä numerosta, ja siksi seuraavan arvon määrittävä naapurusto on äärellinen, mikä on välttämätöntä solukkoautomaatille. Yleisesti ottaen paikannusmerkinnällä olevan luvun kertominen tai jako luonnollisella luvulla n määritellään soluautomaatilla, jos ja vain jos kaikki n:n alkutekijät ovat lukujärjestelmän kantaosassa. Tällainen automaatti on yksiulotteinen ja käännettävä, koska se voidaan jakaa tai kertoa vastaavasti samalla numerolla. Ja esimerkiksi kertomista kolmella desimaalimuodossa ei soluautomaatti määritä, koska siirto voi tapahtua mielivaltaisen suuren numeromäärän kautta: kun kerrotaan 333334*3=1000002, siirto tapahtuu 5 numeron kautta [5] .

Eläimet

Game of Life , yksi tunnetuimmista soluautomaateista, ei ole palautuva: esimerkiksi monet kokoonpanot kuolevat pois. Se sisältää myös Gardens of Edenin  , kokoonpanot ilman edeltäjiä. Sen sijaan Tommaso Toffoli ja Norman Margolus keksivät Critterit ,  palautuvan soluautomaatin, jolla on dynaaminen käyttäytyminen paljolti Lifen tavoin [6] .

"Critters" on lohkosolukkoautomaatti , jossa solut on jaettu 2 × 2 lohkoon, jotka päivitetään erillään muista. Samanaikaisesti jokaisen vaiheen jälkeen jako lohkoihin muuttuu: niitä siirretään yhden solun verran vaaka- ja pystysuunnassa. Critters-siirtymäfunktio kääntää jokaisen solun tilan, jos elävien solujen lukumäärä lohkossa ei ole kaksi, ja kääntää koko lohkoa 180°, jos tämä luku on kolme. Koska elävien solujen lukumäärä muuttuu kuolleiden solujen lukumääräksi ja siirtymäfunktiot ovat palautuvia jokaiselle solumäärän arvolle, tällainen soluautomaatti on reversiibeli jokaisessa lohkossa, ja siksi se on palautuva kokonaisuutena [6] .

Jos aloitat pienellä määrällä satunnaisia ​​soluja kuolleiden solujen suuremman alueen sisällä, monet pienet kuviot, kuten Game of Lifen purjelentokone , leviävät keskialueelta ja ovat vuorovaikutuksessa monimutkaisilla tavoilla. Samaan aikaan otokset sallivat monimutkaiset avaruusalukset ja oskillaattorit äärettömällä määrällä eri jaksoja [6] .

Rakennukset

Tunnetaan useita yleisiä menetelmiä palautuvien soluautomaattien rakentamiseksi.

Estä solukkoautomaatit

Lohkosoluautomaatti  on soluautomaatti, jonka solut on jaettu yhtä suuriin lohkoihin ja jokaiseen lohkoon sovelletaan siirtymäfunktiota erikseen. Tyypillisesti tällainen automaatti käyttää useita osioita lohkoiksi vuorotellen [7] . Tyypillinen esimerkki tällaisesta kaavasta on Margolus-naapurusto , jossa neliömäisen hilan solut on jaettu 2 × 2 lohkoon pysty- ja vaakasuorilla viivoilla, ja jokaisen vaiheen jälkeen lohkojakoa siirretään yhden solun verran vaaka- ja pystysuunnassa. ; siten minkä tahansa lohkon kaikki neljä solua päätyvät eri lohkoihin seuraavassa vaiheessa [8] . Yllä mainitut "otukset"käyttävät Margolusin naapurustoa.

Jotta lohkosoluautomaatti olisi reversiibeli, on välttämätöntä ja riittävää, että jokaisen lohkon siirtymäfunktio on reversiibeli, mikä mahdollistaa lohkosoluautomaatin palautuvuuden tarkistamisen tyhjentävällä luettelolla . Samaan aikaan käänteinen soluautomaatti on myös lohkoautomaatti, jolla on sama rakenne osioiden lohkoiksi, mutta käänteinen siirtymäfunktio [7] .

Peruuttamattomien automaattien simulointi

Mikä tahansa -ulotteinen soluautomaatti voidaan upottaa -ulotteiseen reversiibeliin: lisäksi uuden automaatin jokainen tila tallentaa koko vanhan evoluutiohistorian. Käyttämällä tätä upotusta Toffoli osoitti, että monet peruuttamattomien soluautomaattien ominaisuudet siirtyvät palautuviin, esimerkiksi ne voivat olla Turingin täydellisiä [9] .

Mitan kasvu tällaisessa rakenteessa ei ole sattumaa: joidenkin heikkojen rajoitusten alla (kuten upotuksen muuttumattomuus suhteessa rinnakkaisiin käännöksiin ) on todistettu, että mikä tahansa soluautomaatin upottaminen " Eedenin puutarhaan " on, konfiguraatio ilman edeltäjiä, käännettäväksi soluautomaatiksi, täytyy kasvattaa ulottuvuutta [10] .

Kuitenkin lepotilan ( englanniksi  quiescent states ) läsnä ollessa, eli tilojen, jotka eivät muutu, edellyttäen, että naapurivaltiot eivät myöskään muutu[ miten? ] , on mahdollista mallintaa soluautomaatin lopullinen konfiguraatio samanmittaisessa lohko -käännettävässä soluautomaatissa [11] . Tiedot, jotka olisi pitänyt menettää seuraavassa vaiheessa, tallennetaan sen sijaan äärettömälle solujen alueelle levossa. Samalla konfiguraation osan simulointiin tarvittava aika on verrannollinen sen kokoon. Kuitenkin tällainen rakenne mahdollistaa käännettävän yksiulotteisen Turingin täydellisen soluautomaatin olemassaolon todistamisen [12] .

Muistiinpanot

  1. ↑ Wolfram (2002 ), s. 1018 Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa .
  2. ↑ Schiff (2008 ), s. 44.
  3. ↑ Blanchard, Devaney & Keen (2004 ), s. 38 : "Siirtokartta on epäilemättä symbolisen dynamiikan perusobjekti."
  4. ↑ Sutner (1991 ).
  5. ↑ Wolfram (2002 ), s. 1093 Arkistoitu 20. helmikuuta 2016 Wayback Machinessa .
  6. ↑ 1 2 3 Toffoli & Margolus (1987 ), kohta 12.8.2, "Otuukset", s. 132-134; Margolus (1999 ); Marotta (2005 ).
  7. ↑ 1 2 Toffoli & Margolus (1987 ), jakso 14.5, "Osiointitekniikka", s. 150-153; Schiff (2008 ), osio 4.2.1, "Osiointi Cellular Automata", s. 115-116.
  8. ↑ Toffoli & Margolus (1987 ), luku 12, "The Margolus Neighborhood", s. 119-138.
  9. ↑ Toffoli (1977 )
  10. ↑ Hertling (1998 )
  11. ↑ Morita (1995 )
  12. ↑ Kari (2005 ).

Kirjallisuus