Soluautomaatti

Wikipedia
Loikkaa: valikkoon, hakuun
Conwayn "Elämän peli", eli Game of Life: Kulkuritykki (Gosper's Glider Gun).

Soluautomaatti on tietojenkäsittelytieteessä tutkittu malli, jossa tietokoneen sisään rakennetaan yksinkertainen soluista koostuva maailma. Se voi olla suorakulmainen ruudukko, mutta yhtä hyvin munkkirinkilä tai moniulotteinen. Solut voivat olla eri tiloissa, joita kuvataan numeroilla. Esimerkiksi elävä solu voi olla ykkönen ja kuollut nolla. Solun tiloja voi olla suurempikin määrä. Solun tilojen vaihdokset riippuvat solun aikaisemmasta tilasta ja naapurisolujen tilasta.

Monesti muutaman solun tilan ja muutaman vuorovaikutuksen pohjalta syntyy soluautomaattimaailmaa kuvaaviin ruudukoihin tai avaruuksiin hyvinkin mutkikkaita kuvioita, joilla on joskus joitain elävälle solulle ominaisia piirteitä, esimerkiksi kuvio saattaa jakautua kahtia.

Tunnettu esimerkki soluautomaateista on John Conwayn ”The Game of Life” vuodelta 1970[1]. Life-pelin perusajatus on se, että yksinkertaisten naapurisolujen välisten vuorovaikutusten pohjalta syntyy melko monimutkaisia, muuttuvia kuvioita. Life-pelissä syntyy muutaman yksinkertaisen säännön pohjalta monen pisteen muodostamia mutkikkaita kuvioita, joista käytetään eri nimityksiä, muun muassa "kulkuritykki". Life-pelistä on kehitelty lukuisia versioita.

Myöhemmin soluautomaatteja on tehnyt tunnetuksi Stephen Wolfram muun muassa kirjassaan A New Kind of Science (2002).

Jotkut soluautomaatit muistuttavat eläviä soluja, koska niissä on geeni ja ne jakautuvat. Näitä ovat Langtonin silmukat ja niistä johdetut evoloopit.

Soluautomaatin toimintaperiaate[muokkaa | muokkaa wikitekstiä]

Life-pelin tuottama sykkijä, "Pulsator", joka toistaa samaa kuviosarjaa loputtomiin.

Soluautomaatin ajatus on se, että se koostuu monista soluista, jotka vaihtavat tilaansa valittujan sääntöjen mukaan. Ne ovat pistety useimmiten säännöllisen muotoiseen hilaan, joka on monesti 2-ulotteinen suorakulmainen ruudukko. Usein solun tilanvaihdos rippuu naapureista, mutta voi riippua myös solun menneisyydestäkin. Soluautomaateissa syntyy kohtalaisen mutkikkaita, uusien liikkuvia, muuttuvia ja toistuvia ja itseään toistavia kuvioita.

Esimerkiksi Conwayn Life-peli eli "elämän peli" muistuttaa iseään automaattisesti pelaavaa jätkänshakkia. Mutta peli on nollan pelaajan peli, jota tavallismmin tietokone pelaa itsekseen. Life-pelin pohjana on tavallisesti suorakulmainen ruudukko, hila, jonka ruudut ovat soluja, jotka voivat olla joko eläviä tai kuolleita.

Monesti elävää solua merkitään mustalla, kuollutta valkealla. Värit valitaan usein siten, että näytön tai tetokonetulusteen normaalia taustaväriä lähellä oleva väri on kuollut.

Soluautomaattia jäljittelevälle systeemille voidaan syöttää alussa vaikkapa satunnaista kohinaa, jossa kuolleita ja eläviä on vieri vieressä satunnaisesti arvottuna. Silloin lähtökohta on mustavalkea sekamelska.

Life-pelissä oleva solu muuttuu ajan mukana seuraavasti

  • Elävä solu, jolla on alle 2 elävää naapuria, kuolee yksinäisyyteen
  • Elävä solu, jolla on yli 3 naapuria, kuolee liikakansoitukseen
  • Elävä solu, jolla on 2-3 naapuria, säilyy hengissä
  • Kuollut solu, jolla on tarkoin kolme elävää solua, alkaa elää.

Tällöin sanotaan, että Conwayn Lifellä on 23/3 sääntö. 23 tarkoittaa, että 2 tai 3 naapurisolua pitää solun hengissä, ja 3 naapurisolua synnyttää uuden solun. Kun tietokone pelaa Life-peliä, mustavalkea sekamelska häviää, ja ilmestyy monenlaisia muutaman pisteen, muutaman kymmenen pisteen kokoisia, ajan mukana muuttuvia kuvioita. Life-pelin tyyppisiä soluautomaatteja on laadittu monia. Melko monimutkainen 012345678/3-sääntö tuottaa tikapuumaisia, virtapiiriä muistuttavia kuvioita.

Kehitys yksinkertaisen soluautomaatin sisällä[muokkaa | muokkaa wikitekstiä]

Soluautomaattien on joskus katsottu kuvastavan mutkikkaitten elämän tyyppisten rakenteiden syntymistä yksinkertaisten vuorovaikutusten pohjalta, vaikka luonnon elävät eliöt ovatkin yksinkertaisia soluautomaattia huomattavasti mutkikkaampia. Stephen Wolframin vuonna 1984 tekemän tutkimuksen Universality and Complexity in Cellular Automata, suomeksi suunnilleen soluautomaatteissa oleva toistuvuus ja monimutkaisuus [2] mukaan soluautomaatti voi kehittyä tilanteesta riippuen molella eri tavalla. Soluautomaateille tuotetut kuvioit muistuttavat monesti kaaosteorian mukaisia kuvia.

Soluautomaatti voi tuottaa syöttöarvoista riippuen[3]

  1. Jatkuvan tilan
  2. Jaksollisesti vaihtuvia tiloja/säännöllisen kuvion
  3. Kaoottisen kuvion
  4. Mutkikkaita, paikallisia, ajan mukana muuttuvia kuvioita, jotka ovat joskus pitkäikäisiä, joka näyttää sivulta katsoen esimerkiksi haarautuvalta puulta.

Yleensä soluautomaattilaskelmissa annetaan alkuarvoksi satunnainen soluryhmä, jossa on eläviä ja kuolleita soluja sikin sokin. Jatkuvan tilan synnyttäneessä tapauksessa alussa voi esiintyä "eläviä soluja", mutta ne kuolevat muutamassa sukupolvessa pois. Toisessa tapauksessa alun kaoottinen soluryhmä muuttuu säännökllisiksi mustien ja valkoisten solujen kuvioksi. Kolmennessa tapauksessa kaaos säilyy, vaikka yksittäisten solujen tilat muuttelevetkin. Kolmannessa tapauksessa syntyy ajan mukana muotoaan muuttavia soluryhmiä, jotka "elävät" jonkun aikaa, mutta häviävät.

Soluautomaatin tarkka määritelmä[muokkaa | muokkaa wikitekstiä]

48 askeleen värähtelijä, joka syntyy 2-ulotteisessa 6-kulmioista koostuvan hilan soluautomaatissa säännöllä 34/2. Jos solulla on 2 naapuria, uusi solu syntyy, ja solu elää, jos sillä on 3 tai 4 naapuria.

Tarkoin tieteellisesti kuvattuna soluautomaatti on laskettavuusteoriassa, matematiikassa ja teoreettisessa biologiassa tutkittu diskreetti malli. Se on ääretön ja säännöllinen soluista koostuva verkko, jossa jokainen solu on missä tahansa äärellisestä määrästä mahdollisia tiloja. Verkko voi olla n-ulotteinen, kun n on äärellinen kokonaisluku. Soluautomaatin aika kuluu diskreeteissä (ei-jatkuvissa) askelissa, ja solun tila aikana t määräytyy jonkin äärellisen solujoukon (sen ”naapurisolujen”) edellisen aika-askeleen (t-1) tilan funktiona. Solun naapurit pysyvät samoina koko ajan. Jokaisen solun tila muuttuu synkronisesti ja saman muutossäännön mukaan. Joka kerran kun verkon kaikki solut (muutossäännön mukaisesti) muuttuvat syntyy uusi sukupolvi.

Conwayn Lifeä muistuttavia soluautomaatteja[muokkaa | muokkaa wikitekstiä]

Life-pelin muunnelman 245/6:n tuottama medusa. Solu syntyy, jos sillä on 6 naapuria (jakajaksi merkitty 6), ja pysyy hengissä, jos sillä on 2, 4 tai 5 naapuria (245). Muut naapurimäärät tuhoavat solun.

Sääntö 5/345 "Long life", "pitkä elämä", tuottaa hyvin pitkäjaksoisesti muuttuvia kuvioita. Coral 45678/3 tuottaa korallimaisia kuvioita. 1358/357 on hyvin tasapainosa elämän ja kuoleman välillä. 2345/45678 tuottaa kuin linnoitetuja kaupunkeja. "Day & Night" 34678/3678 tuottaa peilikuvasymmetrisiä, melko suuria kuvioita.

Eräs tunnettu Conwayn pelin muunnelma "HighLife" tuottaa vinon kuusikulmion muotoisen 12 solusta koostuvan "Replicatorin", "kopioitujan", joka jäljentää itsensä niin kuin elävä solu. Replicatorin Life-sääntö on 6/23 tai B36/S23, eli solu suntyy, jos sillä on 3 tai 6 naapuria, ja säilyy, jos sillä on 2 tai 3 naapuria.

"3D Life":ä pelataan kolmessa ulottuvuudessa, ja solut ovat silloin kuutiomaisia.

Jakautuvia soluja muistuttavia automaatteja[muokkaa | muokkaa wikitekstiä]

Kasvava Langhtonin silmukka. Silmukka on alkanut jakautua.
Pääartikkeli: Langtonin silmukka

On kokeiltu mutkikkaampia soluautomaatteja, jotka tuovat enemmän esille keinoelämän piirteitä. Silti nämäkin automaatit ovat hyvin yksinkertaisia, eivätkä näin ollen täysin jäljittele luonnossa olevaa elämää. Lisäksi Langtonin silmukat eivät synny tyhjästä, vaan monistuvat vasta sitten, kun mallikappale, hieman 9:ää muistuttava geenijärjestykseltään tietynlainen silmukka on luotu. Myöskään Langtonin silmukka ei tuota elämän tavoin osiaan itse mutkikkaiden geneettisten säätelymekanismien avulla. Langtonin silmukoita on silti onnistuttu tuottamaan hieman alkeellisemmista silmukoista, jotka törmäilevät toisiinsa.

Amerikkalainen biologi Christopher Langton on kehittänyt Langtonin silmukoiksi kutsuttuja soluautomaatteja, joissa on pieni määrä geneettistä informaatiota muistuttavaa koodia.

Langtonin työ perustui alun perin John von Neumann ja Edgar F. Coddin esittämien ajatusten yksinkertaistamisiin.

Langtonin silmukassa on silmukan muotoinen geeni ikään kuin suojakuoren ympäröimänä. Kun aika kuluu, Langtonin silmukka tuottaa itsestään automaattisesti, ilman ohjausta kopioita jakautumalla. Tämä muistuttaa elävien solujen jakautumista. Syntyy korallimainen eliöyhteisö, jossa elävät, jakautuvat eliöt ympäröivät kuolleita eliöitä, samaan tapaan kuin koralliyhdyskunnassa. Silti Langtonin silmukka on eläviä olioita yksinkertaisempi. langtonin silmukoista on kehitety eteenpäin kehittyneempiä, paremmin kuvaavia versioita, joita muun muassa japanilaiset ahkerasti tutkivat.

Langtonin silmukan muunnelma "evoloop" kykenee vuorovaikuttamaan ympäristön kanssa ja kehittymään evoluution kautta. Monesti evoloopeja ajava kone luo tilanteen, jossa kilpaillaan elintilasta, ja useimmiten pienimmät evoloopit menestyvät parhaiten, koska kuluttavat vähiten ympäristöä. Joskus evoloopit törmäävät toisiinsa, ja tapahtuu geenien vaihtoa niin kuin bakteerien konjugaatiossa.

SDSR (engl. Structurally Dissolvable Self-Reproducing) eli rakenteisesti hajautuva itsejäljentävä soluautomaattisilmukka kuolee eli hajoaa joissain tilanteissa, mikä vastaa enemmän luonnollista tilannetta.

SDSR Evoloop muistuttaa vielä enemmän luonnollista ekosysteemiä, koska sen eliöt voivat kuolla, vuorovaikutata ympäristönsä jkanssa ja kehittyä evoluution kautta. Tällä systeemillä on onnistuttu tuottamaan alkaallisemmista silmukoista varsinaisia Langtonin silmukoita.

Langtonin soluautomaateista tunnetaan myös Langhtonin muurahaiset, jotka muistuttavat hieman Life-pelin olioita.

Johtomaailma[muokkaa | muokkaa wikitekstiä]

2 kellogeneraattoria ja XOR-portti.

Johtomaailma, enganniksi Wireworld on soluautomaattijärjestelmä, jossa voidaan jäljitellä joitain elektronisia piirejä. Siinä on neljä tilaa, tyhjä, johde, elektronin pää ja elektronin häntä. Nämä muuttuvat toisikseen muutaman säännön mukaisesti.

Syklinen soluautomaatti[muokkaa | muokkaa wikitekstiä]

Syklinen soluautomaatti tuottaa 2-ulotteisena monesti spiraalimaisia, säännöllisiä kuvioita.

David Griffeathin syklisessä soluautomaatissa kohdesolun arvo pysyy vakiiona, kunnes naapurisolun arvo kasvaa yhden askeleen suuremmaksi. Tällöin naapurisolun arvo kopioituu kohdesoluun.

Patersonin madot[muokkaa | muokkaa wikitekstiä]

Patersonin madot ovat keinotekoisia yksinkertaisia soluautomaatteja, jotka elävät kuusikulmion muotoisessa hilassa. Madot tuottavat erilaisia kuvioita sen mukaan, minkä säännön mukaan elävät. Osa matojen elinsäännöistä on mahdottomia, ja tappaa madot. Säännöt kuvataan numeroilla niin että 0 on suoraan eteenpäin, 1 1 askel 60 astetta oikealle, 2 120 astetta oikealla ja niin edelleen.

Toisen asteen soluautomaatti[muokkaa | muokkaa wikitekstiä]

Toisen asteen soluautomaatin periaate.

Toisen asteen soluautomaatti muistaa oman tilansa vielä kahden sukupolven kuluttua. Jos nykyhetki on t, edellinen sukupolvi oli t-1 ja sitä edellinen t-2. Seuraavaa automaatin tilaa luotaessa otetaan huomioon myös edeltävien sukupolvien tila

Näin voidaan johtaa vaikka kuinka monenen asteen soluautomaattaja.

Kolmiulotteisia soluautomaatteja[muokkaa | muokkaa wikitekstiä]

Soluautomaattia muistuttavia järjestelmiä[muokkaa | muokkaa wikitekstiä]

Soluautomaattia muistuttavat hyvin paljon niitä vähemmän tutkitut verkostoautomaatit (network automaton) ja sumeat automaatit.

Katso myös[muokkaa | muokkaa wikitekstiä]

Commons
Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Soluautomaatti.

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. Claus Emmeche, Tekoelämä, Art House, isbn 951-884-162-4, 1994, sivu 92
  2. http://www.stephenwolfram.com/publications/articles/ca/84-universality/4/text.html
  3. Claus Emmeche, Tekoelämä, ISBN 951-884-162-4, Neljäs luku: keinotekoinen kasvu ja evoluutio, Aliluku hahmokoneet ja mallit, sivu 89, Kuva 4.5 ja sivu 92

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]