|
Varje, Jari; Life-peli. Seepia 5 (2002):28-29 |
Life on John Conwayn vuonna 1970 kehittämä matemaattinen peli. Se on yksinkertainen esimerkki ns. soluautomaatista. Soluautomaatti on pienten yksiköiden muodostama hila, jossa jonkin systeemin toimintaa mallinnetaan soveltamalla tiettyjä sääntöjä yksiköihin, joita kutsutaan soluiksi. Jokainen solu on jossakin tilassa, joka on yksi kahdesta tai useammasta mahdollisesta. Säännöt määräävät, miten erilaiset naapurisolujen yhdistelmät vaikuttavat solun tilaan. Soluautomaatteja on käytetty mitä moninaisimpiin tarkoituksiin kaasumolekyylien mallintamisesta erilaisiin algoritmeihin.
Life-pelissä hila on yksinkertainen kaksiulotteinen ruudukko. Tähän ruudukkoon asetellaan pelin alkaessa jonkinlainen kuvio alkuasemaksi. Jokaisella solulla on kaksi tilaa: elossa ja kuollut. Alkuasemasta käydään jokainen solu yksitellen läpi käyttäen seuraavia sääntöjä: Jos kuolleella solulla on täsmälleen kolme elossa olevaa naapurisolua (vaaka- , pysty- tai viistosuunnassa yhden solun päässä), solu syntyy eli muuttuu eläväksi. Jos elävällä solulla on kaksi tai kolme naapuria, se jää henkiin. Muissa tapauksissa solu kuolee tai pysyy kuolleena (ks. kuva 1). On kuitenkin huomattava, että kaikki solut on käytävä läpi ennen tilojen muuttamista. Tällä tavalla peli jatkuu, ja jokaisella vuorolla eli sukupolvella kaikki solut käydään läpi.
R-pentomino on nimensä mukaisesti viidestä solusta koostuva r- kirjaimen muotoinen kuvio. Mielenkiintoisen tästä kuviosta tekee se, että se muuttuu vielä yli tuhannen sukupolven kuluttua, mikä on harvinaista pienten, alle kymmenen solun kuvioiden kohdalla. R- pentominon muuttuessa syntyy myös monia Life-pelissä yleisesti esiintyviä kuvioita. Ensimmäinen tällainen kuvio syntyy 43. sukupolvessa. Kyseessä on blokki, joka on yksinkertaisin pysyvä kuvio. Se ei siis muutu tai hajoa itsekseen. Sukupolvessa 51 nähdään ensimmäinen jaksollisesti muuttuva kuvio eli oskillaattori. Kyseessä on blinker, joka toistuu samanlaisena joka toinen sukupolvi, eli sen jakso on kaksi. Monet oskillaattorit levittävät ympärilleen ns. kipinöitä, jotka kuolevat seuraavassa sukupolvessa. Pian tämän jälkeen, sukupolvessa 69, esiintyy Life-universumissa hyvin mielenkiintoinen ilmiö: yksinkertainen liikkuva kuvio eli avaruusalus nimeltä glider. Se toistuu samanlaisena neljän sukupolven välein, mutta liikkuu aina yhden ruudun viistoon. Conway löysi myös avaruusaluksia, jotka liikkuvat vaaka- tai pystysuoraan. R-pentomino kasvaa vielä noin tuhat sukupolvea tuottaen lukuisia mielenkiintoisia kuvioita. Havaittavissa on useita pysyviä kuvioita sekä erilaisia oskillaattoreita. Kuvion tutkiminen käsipelillä on kuitenkin hankalaa, mistä syystä tehtävään on kehitetty lukuisia tietokoneohjelmia, joista joitakin on mainittu Seepian kotisivuilla.
1970-luvulla Conway lupasi 50$ palkinnon sille, joka osoittaisi, että Life-pelissä olisi äärettömästi kasvavia kuvioita, eli kuvioita, joiden elävien solujen lukumäärä kasvaa rajatta. Vastoin Conwayn odotuksia palkinto lunastettiin hyvin pian. Yksinkertaisin tällainen kuvio on nimittäin puffer train, joka koostuu kahdesta LWSS-avaruusaluksesta, joiden välissä on seuraavassa vuorossa b-heptominoksi muuttuva kuvio. Puffer train liikkuu eteenpäin ja jättää jälkeensä vanan sekalaisia pysyviä kuvioita. Toinen tapa luoda rajattomasti kasvavia kuvioita on glider gun, joka liikkuu edestakaisin lähettäen gliderin oikealle alaspäin aina 30 sukupolven välein. Kyseessä on siis oskillaattori, jonka jakso on 30. Näiden yhdistelmää kutsutaan nimellä rake, joka on siis eräänlainen liikkuva glider gun.
Life-maailmaan on kehitetty lukuisia enemmän tai vähemmän hyödyllisiä, mutta yhtäkaikki mielenkiintoisia kuvioita. Koska avaruusalukset kulkevat aina suoraviivaisesti, niitä voidaan käyttää tiedonsiirtoon. Esimerkiksi jono, jossa tietyin väliajoin kulkee glidereita, voi edustaa bittijonoa. Voidaan sopia, että aukko jonossa tarkoittaa nollaa, jolloin on mahdollista lähettää informaatiota. Suurin nopeus, jolla informaatio voi periaatteessa edetä Life-pelissä, on luonnollisesti yksi solu / sukupolvi. Conway nimesi tämän nopeuden valonnopeudeksi, jota merkitään kirjaimella c. Gliderin nopeus on siis c/4. On osoitettu, että suurin nopeus, jolla avaruusalus voi edetä diagonaalisesti, on juuri c/4 ja vaaka- tai pystysuoraan c/2. Valonnopeuden saavuttavia laitteita ei ole löydetty. Jotta informaatiojonot eivät jäisi vain silmäniloksi, voidaan Life-maailmaan luoda kuvioita, jotka toimivat loogisten porttien tavoin. Näiden avulla voidaan periaatteessa rakentaa erilaisia laskukoneita tai vaikkapa kokonaisia tietokoneita. Joitakin tällaisia koneita on rakennettukin. Voidaan mainita esimerkiksi alkulukugeneraattori, joka tuottaa LWSS- avaruusalusten jonon, josta ei-alkuluvut on poistettu.
Eräs mielenkiintoisimmista kysymyksistä Life-maailmassa on Turingin koneen ja edelleen universaalin konstruktorin mahdollisuus. Turingin kone on käsite, jolla tarkoitetaan laitetta, joka voisi ratkaista erilaisia ongelmia tietonauhan ja äärellisten muistipaikkojen avulla. Tietonauha voisi olla yksinkertainen informaatiojono, johon sovelletaan tehtävästä riippuvia sääntöjä muistipaikkojen tilojen mukaan. Voidaan osoittaa, että Life-peliin on mahdollista rakentaa Turingin kone; monimutkaisuuden vuoksi tällaista ei kuitenkaan ole vielä tehty. Universaali konstruktori taas on Turingin konetta hyväksi käyttävä laite, joka rakentaa kopion mistä tahansa sille syötetystä kuviosta. Tämä kuvio olisi kuitenkin äärimmäisen monimutkainen.
Life-peli on hyvin yksinkertainen soluautomaatti, mutta osoittaa silti tällaisten soluautomaattien kykenevän moniin erilaisiin tehtäviin. Tulevaisuudessa soluautomaattien merkitys matematiikassa ja mahdollisesti fysiikassakin voi olla arvaamattoman suuri.
[1] Gardner, Martin; Wheels, Life and Other Mathematical Amusements. W.H. Freeman & Co, New York 1983.
[2] Schatten, Alexander; Cellular Automata. http://www.ifs.tuwien.ac.at/~aschatt/info/ca/ca.html
[3] Callahan, Paul; Game of Life. http://www.math.com/stundents/wonders/life/life.html
[4] Berlekamp, Conway & Guy; Winning Ways, vol. 2. 1982.
[5] Dewdney, A. K.; The Armchair Uiverse. 1988.