Eläimet

"Critters" ( eng.  Critters ) - solukkoautomaatti , joka käyttäytyy samankaltaisesti kuin Conwayn peli "Life" ; erityisesti se on Turingin valmis [1] [2] . Sen kuvasivat ensimmäisen kerran Tommaso Toffoli ( it . Tommaso Toffoli ) ja Norman Margolus ( eng. Norman Margolus ) vuonna 1987, samoin kuin jotkut muut palautuvat soluautomaatit [3] .   

Määritelmä

"Eläimet" määritellään neliömäisessä hilassa , kaksiulotteisessa ja äärettömässä. Kuten "Elämässä", jokainen solu on kulloinkin jossakin kahdesta tilasta: elävä tai kuollut. Samaan aikaan Critters ovat lohkosolukkoautomaatti , joka käyttää Margolus-aluetta . Tämä tarkoittaa, että jokaisessa vaiheessa ruudukko jaetaan 2 × 2 lohkoon, joista jokainen päivitetään erikseen muista. Samanaikaisesti jokaisen vaiheen jälkeen jako lohkoihin muuttuu: niitä siirretään yhden solun verran vaaka- ja pystysuunnassa; siten minkä tahansa lohkon kaikki neljä solua päätyvät eri lohkoihin seuraavassa vaiheessa [3] .

Critterien siirtymäfunktio riippuu elävien solujen määrästä lohkossa: jos niitä on kaksi, lohko ei muutu; jos ne ovat nolla, yksi tai neljä, niin jokaisen lohkosolun tila käännetään. Kolmen elävän solun tapauksessa transformaatio tapahtuu kahdessa vaiheessa: kunkin solun tila käännetään ja koko lohkoa käännetään 180°. Koska elävien solujen määrä muuttuu joka tapauksessa kuolleiden solujen lukumääräksi ja kunkin solumäärän toiminnot ovat reversiibelit erikseen, nämä säännöt määrittelevät palautuvan soluautomaatin [3] .

Vaihtoehtoinen versio siirtymäfunktiosta kääntää tilat vain lohkoissa, joissa on kaksi elävää solua, ja kiertää myös kaikkia lohkoja, joissa on kolme elävää solua parittomissa portaissa ja yhdellä parillisilla askelilla. Tämä versio eroaa tavallisesta siinä, että se ei muuta elävien solujen määrää, ja samalla siinä on samanlainen[ miten? ] dynaaminen käyttäytyminen [2] .

Käyttäytyminen

Kuten missä tahansa palautuvassa solulaitteistossa, jos otusten alkutilaksi valitaan satunnainen tila, tila pysyy evoluutioprosessissa epäjärjestyneenä [1] [3] . Mutta jos aloitat pienestä määrästä satunnaisia ​​soluja suuremmalla kuolleiden solujen alueella, niin monet pienet kuviot, jotka ovat samanlaisia ​​kuin Game of Lifen purjelentokone , leviävät keskialueelta ja ovat vuorovaikutuksessa monimutkaisilla tavoilla [1] [2 ] [3] . Yleisesti ottaen otokset sallivat monimutkaiset avaruusalukset ja oskillaattorit, joilla on ääretön määrä eri jaksoja [2] .

On olemassa todistamaton hypoteesi, että valittaessa jaksottaisia ​​reunaehtoja (eli liimattaessa suorakulmaisen kentän reunoja, jolloin muodostuu toru ), alkuasennoilla, joissa elävien solujen määrä on riittävän pieni kentän kokoon verrattuna, on korkea. todennäköisyys johtaa tilaan, jossa yksi purjelentokone vaeltelee satunnaisesti värähtelevien epäjärjestyneiden solujen kentän poikki [4] .

Game of Life -pelissä avaruusalusten törmäykset voivat johtaa keskinäiseen tuhoutumiseen, vakaaseen konfiguraatioon tai oskillaattoriin , mikä on mahdotonta palautuvassa soluautomaatissa. Sen sijaan minkä tahansa törmäyksen pitäisi johtaa vähintään yhteen avaruusalukseen [1] [4] , kun taas symmetrinen törmäys kahden avaruusaluksen välillä tuottaa symmetrisen joukon kahdesta tai useammasta avaruusaluksesta [1] . Jos lasket alkutilan niin, että törmäyspaikat ovat oikein, Crittersissä voit simuloida biljarditietokonetta purjelentokoneilla ja, kuten Life-pelissä, todistaa Turingin täydellisyyden [1] .

Huolimatta käyttäytymisen monimutkaisuudesta, otuksissa on joitain säilymislakeja ja erilaisia ​​symmetrioita . Esimerkiksi elävien solujen lukumäärän pariteetti joidenkin diagonaalien mukaan ei muutu. Lisäksi, jos alkuperäisessä kokoonpanossa on äärellinen määrä eläviä soluja, parillisen määrän vaiheiden jälkeen elävien solujen määrä on sama (ja parittoman määrän vaiheiden jälkeen kuolleiden solujen määrä saa saman arvon ) [1] . Toisin kuin monet Toffolin ja Margolusin tutkimat palautuvat soluautomaatit, "otukset" eivät muutu itsestään, kun ajan suunta käännetään; ne kuitenkin muuttuvat itsestään, samalla kun ne kääntävät ajan suunnan ja korvaavat jokaisen tilan vastakkaisella puolellaan [3] .

Muistiinpanot

1. ↑ 1 2 3 4 5 6 7 Margolus, Norman (1999), Crystalline Computation, julkaisussa Hey, Anthony JG, Feynman and Computation , Perseus Books, s. 267-305  .
2. ↑ 1 2 3 4 Marotta, Sebastian M. (2005), Living in Critters' world , Revista Ciências Exatas e Naturais osa 7 (1) , < http://web01.unicentro.br/revistas/index.php/RECEN /article/viewFile/385/537 > . Haettu 29. syyskuuta 2017. Arkistoitu 19. maaliskuuta 2012 Wayback Machinessa . 
3. ↑ 1 2 3 4 5 6 Toffoli, Tommaso & Margolus, Norman (1991), 12.8.2 Critters, Cellular Automata Machines , Moskova: Mir, s. 132–134, ISBN 5-03-001619-8  .
4. ↑ 1 2 Virgo, Nathaniel & Ikegami, Takashi (heinäkuu 2014), Voi olla vain yksi: Reversiibelit soluautomaatit ja genkin säilyttäminen , Keinotekoinen elämä 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems , The MIT Press , DOI 10.7551/978-0-262-32621-6-ch084  .