Prírodou inšpirované algoritmy

Ďalšie samoreprodukujúce sa slučky

V tejto časti sa budeme venovať zapuzdreným a nezapuzdreným samoreprodukujúcim sa slučkám. Budú spomenuté niektoré fakty týkajúce sa rotačnej symetrie tychto slučiek a ich zložitosti z pohľadu počtu pravidiel potrebných k reprodukcii. Vzhľadom k rozdielnemu označovania samoreprodukujúcich sa štruktúr v literatúre, bude v nasledujúcom texte použité označovanie, ktoré zaviedol pán James A. Reggia a kolektív (Reggia et al., 1993). Označovanie slučiek teda bude nasledovné: SL = sheated loop (zapuzdrená slučka), UL = unsheated loop (nezapuzdrená slučka). Po tomto označení nasleduje počet buniek z ktorých sa slučka skladá, typ rotačnej symetrie: S = strong (silná rotačná symetria), W = weak (slabá rotačná symetria). Počet stavov v ktorých sa môžu bunky nachádzať a typ použitého okolia: V = Von Neumman neighborhood (5 susedstvo), M = Moore neighborhood (8 susedstvo). Ako príklad nám poslúži nasledujúca slučka. Jej označenie je SL86S8V, pretože ide o zapuzdrenú slučku, obsahujúcu 86 aktívnych buniek, má silnú rotačnú symetriu, pričom každá z buniek môže nadobúdať jeden z ôsmich možných stavov a používa von Neummanovo okolie.

Zapuzdrené slučky

Jednoduchú samoreprodukujúcu sa štruktúru, založenú na 8 stavových bunkách, v 80. rokoch vyvinul Langton. Langtonova Q-slučka s označením SL86S8V predstavuje samoreprodukujúcu sa zapuzdrenú slučku. Výraz "zapuzdrená" poukazuje na to, že táto štruktúra je obklopená obalom alebo puzdrom (bunky v stave X). Na nasledujúcom obrázku (časť a), je zobrazená nereprodukujúca sa slučka s ramenom (vysunutá časť v pravej dolnej časti slučky). Slučka sa skladá z jadra, ktoré obsahuje bunky v stave O a puzdra, pozostávajúceho z buniek v stave X. V tomto prípade sa signál + nasledovaný medzerou (bunka v pokojovom stave) pohybuje po signálovej ceste, ktorá vytvára slučku. Vždy, keď signál príde po pravý dolný roh (miesto vetvenia), kde sa rameno vysúva zo slučky, vyjde z neho jeho kópia. Nereprodukujúce sa slučky, ako je táto, slúžili ako skladovacie prvky v univerzálnych počítačoch - konštruktoroch navrhnutých von Neumannom a Coddom.

Na predchádzajúcom obrázku (časť b) ukazuje počiatočný stav samoreprodukujúcej sa zapuzdrenej slučky (Langton, 1984). Signál alebo postupnosť inštrukcií 0+ 0+ 0+ 0+ 0+ 0+ 0L 0L, ktorá je umiestnená v jadre slučky riadi reprodukciu. Tieto inštrukcie tvoria podobnú slučku ako na obrázku - časť a (pričom čítame v smere hodinových ručičiek a začíname v pravom dolnom rohu). Ako postupne kópie tohto obiehajúceho signálu pravidelne dosahujú koniec ramena, spúšťajú rast ramena a jeho otáčanie, čím vytvoria v bunkovom priestore hneď vedľa seba rovnakú slučku. Inštrukcie sú použité na riadenie konštrukcie kópie, ako aj údaje kopírované na kópiu (Langton, 1984). Samoreprodukujúce sa slučky sú teda v skutočnosti "sústavy reprodukujúce informáciu", v zmysle, v ktorom tento výraz používajú organickí chemici (Orgel, 1992).

"Program" reprodukujúcej sa zapuzdrenej slučky, zobrazenej na hornom obrázku (časť b), sa skladá z inštrukcií 0+, ktoré znamenajú "rozšír súčasnú signálovú cestu o jednu bunku“, a inštrukcií 0L 0L, ktoré znamenajú "zatoč doľava a rozšír signálovú cestu". Inštrukciu 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0L 0L môžeme teda vysvetliť ako "rozšír údajovú dráhu o sedem buniek a potom zatoč doľava". Postupnosť inštrukcií prechádza ramenom slučky a keď dosiahne jeho koniec, "vykoná" sa. S každým vykonaním týchto inštrukcií sa vytvorí jedna strana novej slučky. Čiže keď spustíme tieto inštrukcie štyrikrát za sebou, rameno sa opakovane rozšíri a natočí, až sa vytvorí nová slučka, ktorá sa oddelí a tiež sa začína reprodukovať, takže nakoniec sa objaví rastúca "kolónia" samoreprodukujúcich sa slučiek.

Nezapuzdrené slučky

Existuje hypotéza, že zapuzdrené slučky sa dajú upraviť tak, aby vytvárali ešte jednoduchšie a menšie samoreprodukujúce sa štruktúry (Reggia et al., 1993). Nezapuzdrená podoba pôvodnej zapuzdrenej slučky je na hornom obrázku (časť e). Postupnosť signálu 0+-0+-0+-0+-0+-0+-0+-0L-0L-, ktorá riadi samoreprodukciu tejto slučky, je presne tým istým programom ako u predošlej slučky, len sú použité iné inštrukčné predpisy (bunka v pokojovom stave " " je nahradená bunkou v stave "-"). Ako ukazuje ďalší obrázok, prvky postupnosti inštrukcií, keď dosiahnu koniec ramena, spôsobia opakovane jeho rozšírenie a natáčanie, až kým sa nevytvorí nová slučka. "Vytváracia hlavica" z X na špičke konštrukčného ramena umožňuje priamy rast a rozlišovanie medzi "vľavo a vpravo" na mieste rastu (nasledujúci obrázok - časť b, d). Ako ukazuje ten istý obrázok (časť e), po 250 opakovaniach alebo jednotkách času, pôvodná štruktúra (naľavo, s ramenom smerujúcim nahor) vytvorila svoju kópiu (napravo). Po niekoľkých generáciách sa jediná počiatočná nezapuzdrená slučka rozmnoží na "kolóniu", kde činne reprodukujúce sa štruktúry nájdeme len pri okraji.

Úspešné odstránenie puzdra umožní vytvorenie celej rodiny nezapuzdrených slučiek použitím 8 stavových buniek so stavmi so silnou rotačnou symetriou (strongly rotation - symmetric cell states). Príklady takýchto samoreprodukujúcich sa štruktúr sú na prvom obrázku (časť d, g). Každá z týchto štruktúr je implementovaná s tými istými predpokladmi o počte stavov buniek (8), rotačnej symetrii stavov buniek, okolí, izotropnom a homogénnom bunkovom priestore atď., podobne ako zapuzdrené slučky v Coddovej štruktúre (Codd, 1968). Najmenšia nezapuzdrená slučka v tejto zvláštnej skupine (prvý obrázok - časť g) je viac ako o jeden rozmer menšia ako pôvodná slučka s obalom a vyžaduje len 174 pravidiel zmien (transition rules).

V minulosti bol nesúhlas v požiadavkách vhodnej rotačnej symetrie pre jednotlivé stavy buniek, popísaných v prechodovej funkcii. Najstaršie modely celulárnych automatov ako sú von Neumannove, mali funkciu zmien spĺňajúcu len slabú rotačnú symetriu: niektoré bunky boli smerovo orientované. Tieto orientované stavy buniek boli také, že sa premieňali z nejakého iného stále po 90° otočeniach základnej 2D súradnicovej sústavy. Napríklad, stav označený ^ vo von Neumannovej staršej práci, je orientovaný a teda na iné stavy >, v a < sa mení postupne po 90° otočeniach; predstavuje jeden orientovaný prvok, ktorý môže byť v 4 rôznych stavoch alebo orientáciách. Ale Coddova zjednodušená verzia von Neumannovho samoreprodukujúceho sa počítača - konštruktéra (Codd, 1968) a spomenuté jednoduchšie reprodukujúce sa slučky (Langton, 1984) a prvý obrázok (časť d,g) sú založené na prísnejších kritériách nazývaných silná rotačná symetria. So silnou rotačnou symetriou sa na všetky stavy buniek pozeráme ako na neorientované alebo rotačne symetrické.

Ako ukazuje prvý obrázok (časť h,k), bola vyvinutá druhá rodina nezapuzdrených samoreprodukujúcich sa slučiek, ktorých počiatočný stav a postupnosť inštrukcií je podobná ako u skôr popísaných slučiek na tom istom obrázku (časť d, g). Avšak pre štruktúry na rovnakom obrázku (časť h,k) bola predpokladaná slabá symetria, a posledné štyri z ôsmich možných stavov (. O # L ^ > v < ) sa berú ako orientované. Inými slovami, hoci existuje stále osem stavov, stav ^ je reprezentovaný ako jeden prvok, ktorý má orientáciu a preto môže existovať buď ako ukazujúci nahor alebo v troch ostatných smeroch >, v, <. Ostatné štyri stavy (. O # L) sú neorientované. Napríklad na prvom obrázku (časť i) stavy >, v a < sa objavujú na dolnej, ľavej a hornej vetve slučky a predstavujú postupnosť inštrukcií <OO<OO<OO<OO<OO<LL. Hoci bunky v takomto modeli majú osem možných stavov a sú teda porovnateľné v tomto zmysle s vyššie uvedenými prácami o zapuzdrených a nezapuzdrených slučkách (prvý obrázok - časť a, g), môžeme sa na ne pozerať ako na jednoduchšie, tak že majú len päť rôznych možných prvkov. Upustenie od požiadavky silnej súmernosti otáčania viedlo následne k funkciám zmien vyžadujúcim menej pravidiel ako u príslušnej verzie so silnou súmernosťou (Reggia et al., 1993). Táto jednoduchosť a rýchlosť reprodukcie umožnená slabou súmernosťou otáčania je zobrazená na nasledujúcom obrázku, kde je celý prvý reprodukčný cyklus malej nezapuzdrenej slučky. Len 31 pravidiel je potrebných na riadenie reprodukcie.

V našom tutoriáli sú applety, v ktorých si môžete vyskúšať dynamiku Bylovej slučky a a dvoch typov slučiek Chou-Reggia.