Akik karácsonykor nem állítottak karácsonyfát környezettudatossági vagy egyéb szempontok miatt, azoknak ajánlom szeretettel az alábbi fraktális pszeudo-random végtelen karácsonyfa imitációt. Természetesen fraktál generátorokkal ennél sokkal élethűbb fenyőfák is generálhatók, azonban az alábbi mintázat egy különösen egyszerű szabállyal adható meg, amit ugyanis az ábrán látunk az nem más, mint egy egyetlen sejtből kiinduló egydimenziós bináris sejtautomata időfejlődése.
De mik is azok a sejtautomaták? Az 1940-es években Neumann Jánost az a kérdés foglalkoztatta, hogy miféle logikai szerkezet szükséges egy olyan automatikus géphez, amely önmagát képes reprodukálni. Ennek kapcsán sikerült megalkotnia az első sejtautomatákat, és példát mutatott síkbeli önreprodukáló automatákra. Általában véve a sejtautomaták diszkrét dinamikus rendszerek, a sejtautomatát alkotó sejtek ugyanis diszkrét térben helyezkednek el, véges sok különböző állapotuk lehet, tehát diszkretizált az állapotterük, és a sejtek diszkrét időlépésekben szinkron módon frissülnek, azaz egyszerre változtatják az állapotukat a rendszer időfejlődése során. A sejtek valamilyen mozaikszerű elrendezésben találhatók, általában egy szabályos rácson helyezkednek el, amely lehet akár több dimenziós is. Egy sejt következő állapota mindig csak a szomszédai és önmaga aktuális állapotától függhet, vagyis nincsen távolhatás. A következő állapotot leíró ún. generációs vagy átmeneti szabályok alap esetben determinisztikusak, azaz nincsen bennük véletlen elem, és így teljes mértékeben ezek határozzák meg a sejtautomata dinamikáját.
A legismertebb sejtautomata a sokak által jól ismert életjáték, a legegyszerűbbek azonban az ún. elemi sejtautomaták. Egy elemi sejtautomata nem más, mint egy egydimenziós vonalba rendezett sejtsor kétállapotú sejtekkel, mely állapotokat élő és holt jelzővel szokás illetni. Az elemi sejtautomatákat könnyű számba venni, mert megadhatók a szabállyal, ami meghatározza, hogy mi lesz egy sejt állapota annak függvényében, hogy mi volt a bal- és jobboldali szomszédjának illetve önmagának az állapota az előző lépésben. Mivel mindhárom sejt állapota kétféle lehet, ezért összesen nyolc kombináció van, amire meg kell adnunk, hogy mi lesz a következő lépésben a középső sejt új állapota. Az új állapot is csak kétféle lehet, így a lehetséges szabályok száma 2^8 = 256. Ennek megfelelően az elemi sejtautomata megadható egy a szabályt kódoló bináris számmal, amint az illusztráló ábrán is látható. Ezt a sorszámot nevezzük a szóban forgó elemi sejtautomata Wolfram kódjának. Eszerint beszélünk tehát a 30-as szabályról, arról az elemi egydimenziós sejtautomatáról, amelynek Wolfram kódja 30.
A sejtautomaták dinamikai fejlődését tehát megadják az átmeneti szabályok, azonban a mintázatok kialakulásához egy kezdeti állapotot megadása is szükséges. A fenti karácsonyfa szerű ábrán a kezdeti állapot egyetlen élő sejt (fekete színnel jelölve) a sejtsorban, a fenyőfa csúcsa, és lefelé telik az idő, azaz minden egyes sor a sejtautomata következő állapotát mutatja. A legtöbb szabályról kiderül, hogy egészen egyszerű viselkedést mutatnak, akármilyen kezdő állapotból indítjuk a rendszert, rövid időn belül kialakul egy stabil konfiguráció, ami nem változik tovább, vagy valamilyen időben periódikusan ismétlődő mintázat alakul ki. A 30-as szabály sorszám szerint az első, ahol valami igazán meglepő viselkedést találunk. Ez a sejtautomata a Wolfram-féle osztályozás szerint 3-as osztályú, ami azt jelenti, hogy aperiodikus, kaotikus viselkedést mutat, mégpedig majdnem minden kezdeti állapotra, nem csak a fenti kezdőfeltétel esetén. Bár vannak benne struktúrák, de azok előfordulása látszólag véletlenszerűnek tűnik, aminek az az oka, hogy a mintákat szétzilálja a környező pszeudo-random zaj.
Ez az igen egyszerű sejtautomata megdöbbentő példa arra, hogy komplex, látszólag véletlenszerű mintázatokat egészen egyszerű és determinisztikus szabályok elő tudnak állítani. A természetben is megfigyelhetünk hasonló mintázatképződést, ahogyan az a Conus textile tengeri csiga faj házán is látható. A szabály igen egyszerű volta miatt gyakorlati haszna is van, meg lehet mutatni ugyanis, hogy a "karácsonyfa" középső oszlopa teljesíti az alapvető véletlenszám teszteket, ezért véletlenszám generátornak is használják, például a Wolfram által kifejlesztett Mathematica programcsomagban, és ebből kifolyólag kriptográfiai alkalmazásai is vannak.
Ui.: A pentagram táblás türelemjáték beküldési határideje karácsony volt. Két rendszeres olvasómtól is kaptam megoldásokat, mindketten számítógépes programmal oldották meg a feladatot, ugyanis rendelkezésükre állt olyan általuk már korábban kifejlesztett algoritmus, amellyel tetszőleges türelemjáték megoldható. Azt nagyon sajnálom, hogy mások nem foglalkoztak vele, mert számítógép nélkül is hamar lehetett volna megoldást találni. Már csak azért is, mert rengeteg megoldás van. Gál Péter az Ördöglakat blog szerkesztője az összes megoldást megadta, szimmetriáktól eltekintve közel 72 ezer megoldást. Az eredményekről később még részletesen írok, az új fejtörő feladvány pedig szilveszterkor kerül kitűzésre.
Nincsenek megjegyzések:
Megjegyzés küldése