2015. április 16., csütörtök

Életjáték

A hackerek logója
"A 70-es évek elején az életjáték valósággal "szenvedélybetegséggé" vált, és a TIME 
becslése szerint több millió dolláros anyagi kárt okozott a mamutgépeket üzemeltető biztosítótársaságoknak és bankoknak - elvesztegetett gépidő formájában. Sok kutatóintézetben pedig gyakorlatilag megbénult az élet, mert mindenki a komputermonitorokon egymást követő generációkat figyelte. Egyesek szerint az életjáték ártalmasabb volt bármilyen ismert vírusnál, mások szerint hozzásegített minket ahhoz, hogy jobban megértsük a minket körülvevő valóságot."



A hetvenes évek elején, amikor a számítógépes vírusok feltűnése még nem volt mindennapos jelenség, volt egy másik, a számítógépek tulajdonosait fenyegető járvány. A számítógépes életjáték, amelyet széles körben először Martin Gardner ismertetett legendás hírű rovatában a Scientific America című folyóiratban, és gyorsabban terjedt, mit a spanyolnátha. A bankok és biztosító társaságok azt vették észre, hogy számítógépidejük nagy részével nem tudnak elszámolni. Sok programozó a játék rabja lett és ezzel töltötte munkaideje nagy részét, állandó készenlétben arra, hogy – ha a főnök netán arra sétálna – az ESC gombot megnyomva, kitörölje az életjáték árulkodó jeleit. John Horton Conway, egy kiemelkedően termékeny cambridge-i matematikus alkotta életjáték valami különleges dolog volt. Nem kétszemélyes, mint a dáma, vagy a sakk, és nem is pasziánsz. Egy személytelen játék. Egyetlen számítógép elég hozzá. Életjáték a szemlélődők sportja. Az emberi résztvevőnek a játék megfigyelésén kívül csak egyetlen dolgot kell tennie: meghatározni a kiindulási pozíciót. A többi már magától következik be: a káoszból rend lesz, a rendből káosz, meg viszont.

Döbbenetes élmény a „teremtés”! Megalkotod a születés és a halálozás szabályait, megadod az induló populációt, majd hátradőlve foteledben szemléled hogyan folyik le az általad teremtett világ „történelme”. Vajon sikerült-e örökéletű és folyton változó világot teremtened, vagy néhány generáció után leáll a fejlődése, netán kihal, vagy születnek-e belőle új világok, saját szabályokkal és ezek túlélik-e az őket szülő világot, egymással versenyezve lesznek-e túlélők, vagy néhányukból egy újabb világ születik?

Az egyik legérdekesebb sejtautomata rendszert készí­tette el Conway 1970-ben. Conway a játékát „Élet”-nek nevezte el, mivel viselkedése nagyon hasonlít élő szervezetek változásaihoz (születés, kihalás, fejlődés, visszafejlődés, stb.). A Conway-féle sejtautomata szabályai zseniálisan egyszerűek. Az élettér egy végtelennek feltételezett négyzetháló. Minden cellában egy sejt élhet. Minden sejtet nyolc szomszédos cella vesz körül, négy keresztben négy pedig átlósan.

Conway a sejtautomata-tervét a minimumig igyekezett egyszerűsíteni, amikor ezeket a „genetikai szabályokat” igen átgondoltan, hosszú kísérletezés után kiválasztotta. Röviden: a szabályok olyanok legyenek, hogy a népesség viselkedése lehetőleg ne legyen előre megjósolható.
szemléltetés


  1. Túlélés: minden sejt, amelynek kettő vagy három szomszédja van, életben marad a következő generációra.
  2. Halál: minden sejt, amelynek négy vagy több szomszédja van, meghal a túl-népesedéstől! Ugyancsak minden sejt meghal a következő generációra, amelynek kevesebb mint két egy szomszédja van – a halál oka: elszigetelő-dés.
  3. Születés: ha egy üres cellának pontosan három élő sejt van a szomszédjá-ban, akkor ott új sejt születik.
Ilyen módon változik az élő cellák populációja nemzedékről nemzedékre. A cellák sorsa lépésről lépésre pontosan meghatározott, a végtelenségig. Jövőjüket a kiindulási állapot teljes egészében tartalmazza, ettől semmiféle eltérés nem lehetséges. Nagyon fontos, hogy az összes születés és halál egyidejűleg következik be. Együtt alkotnak egy „generációt”, vagy másképpen nevezve egy „lépést” a kezdeti elrendezés „élet-történetében”.

Könnyen nyomon tudjuk követni az egysejtűeket, ha a számítógépes szimuláció során őket fekete, az üres mezőket fehér négyzettel jelöljük.

Ha a szimuláció elég gyors, és elég nagy területet figyelünk egyszerre, már nem tudjuk megkülönböztetni az egyes egysejtűeket, csak csoportjaikat tudjuk nyomon követni. Leginkább gyorsan, és látszólag össze-vissza változó csoportokat látunk a szimuláció során, de észrevehetünk érdekes csoportokat is. Ezentúl ezeket az egysejtű csoportokat alakzatnak nevezzük. Az alakzat egysejtűi nem feltétlenül érintkeznek fizikailag, de vizuálisan együvé tartozónak érezzük őket.

A kialakuló formák általában érdekesek lesznek, furcsák, szokatlanok, néhányszor akár szépnek is látjuk, de a változás az ember számára mindig váratlan. Néhány esetben a csoportok kihalnak (minden sejt eltűnik), bár ez többször csak jó néhány generáció után történik meg. A legtöbb kezdeti forma egy olyan stabil figurává alakul – Conway ezeket „csendéletnek” nevezte – amelyik többé nem változik, vagy egy olyan alakzattá, amely örökké, ismétlődően lüktet – oszcillál. Kezdeti szimmetria nélküli alakzatok szimmetrikussá válhatnak, azonban fordítva ez nem történhet meg: szimmetrikus alakzat örökké szimmetrikus marad, bármekkorára növekszik is. A kiindulási állapottól függően lesznek kihaló, oszcilláló, pulzáló, alakjukat időnként visszanyerő, vándorló, a végtelenségig növekedő formációk.

A legegyszerűbbek a mozdulatlan alakzatok (csendéletek), vagyis azok az alakzatok, melyek nem változnak meg az idő múlásával, hacsak egy másik, hozzájuk közel kerülő alakzat meg nem változtatja őket. A gyorsan változó játéktéren könnyen észrevehetőek, úgy tűnik, mintha nem vonatkoznának rájuk a szabályok.
blokk, méhsejt, hajó, zabáló, cipó
A blokk alakzatnál az összes egysejtűnek 3 egysejtű-szomszédja van, így ők a szabályok alapján nem halnak meg. Az alakzattal szomszédos üres mezőknek 1 vagy 2 egysejtű-szomszédjuk van, így új egysejtű sem születhet.


villogó
Könnyen felismerhetőek az oszcilláló alakzatok is, melyek változnak ugyan az idő múlásával, de egy megadott periódusid elteltével az eredeti alakzatot kapjuk vissza. A periódusid nagysága a különféle alakzatoknál eltérő lehet, a legegyszerűbb ilyen alakzatnál, a villogónál például 2. A villogó 3 darab, sorban elhelyezkedő egysejtűből áll.



sikló
Az egyik legérdekesebb alakzat, amit könnyen felfedezhetünk, az a sikló. A sikló egy olyan alakzat, amelyik az oszcilláló alakzatokhoz hasonlóan, egy adott periódusidő elteltével visszanyeri az alakját. 4 időegységenként egy egységgel átlósan mozdul el a játéktéren. Ha a szimuláció elég gyors, úgy tűnik mintha egy kis állat siklana át a képernyőn. Ez az alakzat lett a hackerek hivatalos emblémája is.



könnyű űrhajó
Találhatunk olyan alakzatot is, mely a siklóhoz hasonlóan mozog a játéktéren, de a mozgás nem átlós irányban történik, hanem függőlegesen vagy vízszintesen. A legkisebb ilyen alakzat az LWSS (Light Weight SpaceShip = Könnyű űrhajó). Az alakzat a nevét onnan kapta, hogy egy űrhajó repüléséhez hasonlít a mozgása.


könnyű, közepes, nehéz űrhajó
Találunk még úgynevezett zabálót, amely négy generáció alatt meg tud enni egy siklót. Bármit is fo­gyaszt azonban, az alapvető folyamat ugyanaz. Egy híd alakul ki a zabáló és zsákmánya között. A következő generációban a híd régiója kipusztul a túlnépesedéstől, magával ragadva egy darabot mind a zabálóból, mind a prédából. A zabáló ezután helyreállítja magát. A préda rendszerint nem. Ha az áldozat maradéka magától kihal, mint például a sikló esetében, a zsákmány már el is lett fogyasztva.

Az eddig vizsgált alakzatok oszcillálnak, mozognak, de nem képesek elszaporodni. Eleinte nem tudták megválaszolni azt a kérdést, van-e olyan alakzat, mely korlátlanul növekszik, vagyis az általa lefoglalt mezők száma minden határon túl növekszik.

Conway 50 dollár jutalmat tűzött ki a feladatra, és rögtön adott egy tippet is: Egy siklóágyút kell alkotni, vagyis egy olyan alakzatot, mely végtelen számú siklót bocsájt ki magából. Ekkor az egyetemeken, bankokban, hivatalokban beindult a formációgyártás. Az alakzatot végül a MIT diákjai találták meg. Az alakzat nevét megértjük, ha működés közben figyeljük meg. Olyan, mintha egy hatalmas ágyú időnként kilőne egy-egy siklót, melyek a kilövés után gyorsan repülnének, minél messzebb az ágyútól.
Ha megnézzük a siklóágyút, akkor egy olyan bonyolult alakzatot látunk, melyről fel sem tételezzük, hogy véletlenül is létrejöhet. Az siklóágyú vezette a csoportot a további bámulatos felfedezésekhez. Találtak egy elrendezést 13 siklóból, amelyek egymásnak ütközve siklóágyúvá alakulnak. Az ábrán egy egyszerűbb változatot látunk, itt elég 8 sikló ütköztetése a siklóágyú születéséhez. Tehát, ha az ábrán látható módon elhelyezünk 8 siklót, akkor a siklók összeütköznek, és az összeütközésekből létrejön egy siklóágyú, ami rögtön el is kezd siklókat kibocsátani magából.

siklók ütköztetése amelynek eredménye egy siklóágyú

Közben találtak egy rókát (pentadekatlon), ez egy 15 periódusú oszcillátor, amely megeszik minden siklót, amely belecsapódik. A rókáról azonban vissza is tud pattanni egy sikló úgy, hogy két róka folyamatosan dobálózhat vele örökké. Egymás útvonalát metsző siklók összeütközése fantasztikus eredményt hozhat. Meglepő alakzat képződhet, amelyik megfordítja a siklók irányát. Néhány ütközéses alakzat addig növekedhet, amíg elfogyasztja az összes siklóágyút. A csoport virtuozitásának utolsó nagy kirobbanása volt siklóágyúk elrendezése oly módon, hogy a kilőtt siklók áradata felépít egy gyárat, amely összeszerel és kilő egy könnyű űrhajót.

Az siklóágyú létezése veti fel azt az izgalmas lehetőséget, hogy Conway játéka alkalmas lehet egy Turing-gép, egy univerzális kalkulátor szimulálására. Elvben képes bármire, amit egy nagyteljesítményű számítógép megtehet. A siklók használhatók lehetnének az egység-impulzusok tárolására és továbbítására, végrehajtva a szükséges logikai műveleteket. Ha Conway játéka alkalmas az univerzális kalkulátor megvalósítására, a következő kérdés, hogy vajon alkalmas-e az univerzális konstruktőr megvalósítására.

Épp ez az a feladat, amire Conway és diákjai vállalkoztak, és fenséges sikerrel jártak. Megterveztek egy önreprodukáló rendszert, amely kizárólag az élet­játék celláiból áll, és ugyanakkor univerzális Turing-gépként képes viselkedni, továbbá bebizonyították ennek életképességét – egy kétdimenziós számítógép ez, amely elvileg bármely kiszámítható függvényt képes kiszámítani? Mi a cso­da vezette Conwayt és diákjait, hogy először is ezt a világot létrehozzák, és az­tán pedig megtervezzék annak szóbanforgó csodálatos lakóját? Az, hogy nagyon absztrakt szinten megpróbálták megválaszolni az egyik központi kérdés; melyekkel e fejezetben foglalkoztunk: mi az a minimális komplexitás, amel­lyel egy önreprodukáló dolognak rendelkeznie kell?

Az önreprodukáló alakzat négyféle építőkockából áll össze: sikló, siklóágyú, blokk és mindenevő. A siklók megfelelnek a közönséges számítógépek elektromos impulzusainak. A huzaloknak megfelelő átlókon mozognak. A siklók ütközése nemcsak siklóágyút, hanem blokkot és mindenevőt is képes létrehozni. A mindenevő kis méretű, horog alakú, mozdulatlan életforma. Ha egy sikló megfelelő irányból beleütközik egy mindenevőbe, akkor megsemmisül, míg a mindenevő néhány böffentés után visszanyeri eredeti alakját. Ilyen módon meg lehet akadályozni, hogy a siklók elszabaduljanak. Ha már megtették feladatukat és feleslegessé válnak, akkor elnyelik őket a mindenevők. Nem engedhetjük meg, hogy siklók szökjenek ki a végtelenbe.

Két sikló ütközése más következményekkel is járhat, attól függően, hogyan történik. Kétfajta ütközés különleges szerepet játszik. Két, egymással derékszögben ütköző sikló egyszerűen megsemmisülhet: ezt eltüntető ütközésnek nevezik. A visszaverő ütközésben a siklók szintén derékszögben találkoznak, de csak az egyik tűnik el, a másik hátraarcot csinál és visszaindul átlós irányban egy cellával eltolt útvonalon oda, ahonnan érkezett.

Szükség lesz még az ütközések egy másik csoportjára is. Egy megfelelően irányított sikló el tud tüntetni egy blokkot. Ha két megfelelő távolságban lévő sikló beleütközik egy blokkba, azt átlós irányban három négyzetnyivel közelebb hozza. Végül egy harminc (igen, 30) siklóból álló flotta, mind ugyanabból az irányból érkezve, átlós irányban három négyzetnyivel távolabbra képes tolni egy blokkot. A blokkokkal való ilyen ütközésekben a siklók minden esetben eltűnnek, miután feladatukat elvégezték.

Ez tehát a szükséges elemi alakzatok és elemi események teljes listája. Négy alakzat, 10 elemi esemény. Ezekből épült fel az önreprodukáló automata.

Neumann János briliáns korai spekulációit követték, aki e kérdésen dolgozott 1957-ben bekövetkezett halála idején. Francis Crick és James Watson 1953-ban fedezték fel a DNS-t, de hogy az hogyan működött, évekig misztérium volt. Neumann bizonyos részletességgel kidolgozta egy lebegő robot elképzelését, amely a hányódó tör­melék darabjait fölszedi, és önmaga másolatának felépítéséhez felhasználja, hogy aztán e folyamatot megismételhesse. Neumann arról szóló leírása (me­lyet halála után tettek közzé, 1966-ban), hogy hogyan olvashatja egy automata a saját tervrajzát és hogyan másolhatja azt az általa létrehozott új termékre, le­nyűgöző részletességgel megjósolta a DNS kifejezési és replikációs mechaniz­musaira vonatkozó számos későbbi felfedezést. Ahhoz, hogy az önreprodukált automaták lehetőségére vonatkozó bizonyítást matematikailag szigorúvá és kezelhetővé tegye, Neumann kénytelen volt egyszerű kétdimenziós absztrak­ciókat választani, amelyeket ma sejtautomatának nevezünk. Conway életjáték cellái e sejtautomaták egy különösen kellemes példáját nyújtják.

Conway és diákjai meg akarták erősíteni Neumann bizonyítását azáltal, hogy ténylegesen létrehoznak egy kétdimenziós világot annak egyszerű fizikájával, amelyben egy ilyen önreplikáló szerkezet egy stabil működő struktúra lehet. Neumannhoz hasonlóan válaszukat olyan általánosan akarták megforgalmazni, ahogyan csak lehet, és ennélfogva a lehetőségekhez képest az aktuális fizikától és kémiától függetlenül. Valami halálosan egyszerűt akartak, amit könnyű vizualizálni, és könnyű kiszámítani, úgyhogy nemcsak visszavonultak a három dimenzióból kettőre; „digitalizálták” is a teret és az időt – minden időpont és távolság, mint láttuk, „pillanatok” és „cellák” egész számait jelenti. Neumann volt az, aki Alan Turingnak a mechanikus számítógépről kialakított absztrakt koncepcióját (amit ma „Turing gépnek” nevezünk) egy általános célú, tárolt programmal dolgozó, szekvenciális számítást végző komputer tervévé alakította (amelyet ma „Neumann-gépnek” neveznek).


Nincsenek megjegyzések:

Megjegyzés küldése