Prírodou inšpirované algoritmy

Zoznam štruktúr v aplete

Popis kategórií apletu

• Oscilátory – štruktúry opakujúce sa po určitej generácii, ktoré sa nikdy neustália. Oscilátory je možné rozdeliť na dve skupiny : stator a rotor. Rotor sú štruktúry meniace sa konštantne, každý rotor musí susediť s nejakým iným rotorom. Stator pozostáva zo vždy živých štruktúr.
• Stabilné štruktúry – štruktúry, ktoré nikdy nemenia svoj vzhľad počas generácii. Ak štruktúra môže byt rozdelená na 2 a viac stabilných štruktúr tieto štruktúry sa označujú ako ostrovy.
• Matuzalem – Do tejto skupiny patri akákoľvek malá štruktúra, ktorá je nestabilná po dlhý čas. Nezahrňujú sa tu štruktúry, ktoré rastu do nekonečna. Pôvodne matuzalem zahŕňal štruktúry s maximálne 10 buniek s dobou života (Life-span) aspoň 100. Najznámejšou je štruktúra R pentomino.
• Lode – Medzi lode patria pohybujúce sa štruktúry nezanechávajúce za sebou žiaden odpad. Pojem glider (klzák) sa niekedy používa ako synonymum lode, ako najmenšia loď. Ďalej tu patria lightweight spaceship, middleweight spaceship, heavyweight spaceship. Zvyšné lode sa označujú ako neštandardné.
• Bafkač – Akákoľvek štruktúra pohybujúca sa ako loď s tým rozdielom, že za sebou zanecháva odpad.
• Generátor – Štruktúry patriace k oscilátorom, ktoré po nejakej generácii vždy vygenerujú štruktúru.
• Rozbuška a knôt – Štruktúry "horiace" z jednej strany. Ide o stabilné štruktúry, ktoré po inicializácii začnú horieť z jedného konca. Zmena štruktúry sa deje iba z jedného konca, pripomína to horenie.
• Požierač – Štruktúra schopná interagovať s inou štruktúrou bez spôsobenia veľkých škôd na samej sebe. Po príchode inej štruktúry túto štruktúru „zožerie“ a vráti sa do pôvodného stavu, ale bo sa ustáli v inej podobe. Niektoré je možné označiť aj ako oscilátory.
• Čiara – Od dĺžky čiary závisí či sa z nej vyvinie nejaká iná štruktúra, zanikne alebo sa bude čiara množiť do „nekonečna.“.
• Rôzne – Akákoľvek štruktúra nezaraditeľná do predchádzajúcich kategórii.

Oscilátor

• Perióda 2
  • Návestidlo (Beacon) - Oscilátor s periódou 2, pozostávajúci z dvoch ostrovčekov
  • Blinker - Oscilátor s periódou 2 pozostávajúci z 3 buniek kmitajúcich okolo prostrednej bunky.
  • Hodiny (Clock) - Oscilátor s periódou 2, pozostávajúci zo 6tich buniek.
  • Žiarovka (Light Bulb) - Oscilátor s periódou 2 pripomínajúci svietiacu žiarovku.
• Perióda 3
  • Kríž (Cross) - Oscilátor s periódou 3. Je najmenší oscilátor s periódou 3.
  • Hustler (Hustler) - Oscilátor s periódou 3. Jednotlivé generácie majú postupne 30,34 a 32 živých buniek.
  • Kľúč (Key) - Oscilátor s periodóu 3. Jednotlivé generácie majú postupne 16,22 a 18 živých buniek.
  • Hviezda (Star) - Oscilátor s periódou 3. Jednotlivé generácie majú postupne 36,24 a 28 živých buniek.
  • Dva požierače (Two eaters) - Oscilátor s periódou 3. Ako samostatné štruktúry požierače môžeme zaradiť medzi oscilátory.
• Perióda 4
  • Zmätený požierač (Confused eaters) - Oscilátor s periódou 4. Dva požierače si oproti sebe pohadzujú potravu.
  • Binárny kód (Gray counter) - Oscilátor s periódou 4. Jednotlivé generácie majú postupne 26,28,30 a 28 živých buniek. Vertikálne, alebo horizontálne bunky sú živé, alebo mŕtve. Generácie oscilátora predstavujú postupne 0 (0), 01 (1), 10 (2) a 11 (3) v binárnom kóde.
• Perióda 5
  • Siesta (Siesta)- Oscilátor s periódou 5. Jednotlivé generácie pozostávajú z 50,52,54,56 a 56 živých buniek.
  • Pseudo-barberpole - Oscilátor s periódou 5. Je oscilátorom s najmenším počtom buniek pre periódu 5.
• Perióda 6
  • Zovšadiaľ (A for All) - Oscilátor s periódou 6. Jednotlivé generácie pozostávajú z 28,28,32,28,28 a 32 živých buniek. V každom smere sa vytvára písmeno A.
• Perióda 9
  • Snacker - V strede je požierač, ktorý má samostatnú periódu 15. Štyri stabilizátory (ďalšie požierače) v rohoch znižujú periódu oscilátora na 9.
• Perióda 30
  • Klzákové delo - Keď chcel Conway dokázať, že jeho jednoduchý CA je schopný emulovať Turingov stroj, bolo potrebné preukázať možnosti zostrojenia počítača z jeho jednoduchých prvkov. Z tohto hľadiska bolo kľúčove dokázať existenciu obrazca, ktorý by sa premiestňoval (nosič informácie) a tiež existenciu iného obrazca, ktorý by sa neustálil v jednom z uvedených spôsobov, ale generoval by spomínané pohyblivé obrazce. William Gosper z MIT našiel tzv. klzákové delo, produkujúce v každej 30-tej generácii jeden klzák a klzákové delo, vpravo dole zasa cyklická štruktúra s periódou 15, "požierajúca " prichádzajúce klzáky.

Lode

• c 2
  • Škorpión (Scorpion) - Posuvná štruktúra opakujúca sa s periódou 8 pohybujúca s periódou 12.
  • Pushalong - Posuvná štruktúra s periódou 4.
  • Lode c/2 - Posuvná štruktúra s periódou 4. Postupne od najkratšej po najdlhšiu možnú ľoď.
• Ortogonálne
  • Orion - Štrúktura pohybujúca sa rýchlosťou c/4, pričom c je rýchlosť svetla. Je to najmenšia známa diagonálne sa pohybujúca loď okrem klzáku (glidru).
  • Iskry (Sparks) - Štruktúra pohybujúca sa rýchlosťou c/4, pričom c je rýchlosť svetla pohybujúce sa v horizontálnom smere.
  • Mozog (Brain) - Štruktúra pohybujúca sa rýchlosťou c/3, pričom c je rýchlosť svetla, pohybujúce sa vo vertikálnom smere.

Bafkač

• Bafkač (Puffer) - Štruktúra, ktorá má na okrajoch dve lode, posúvajúce sa nahor rýchlosťou c/2 zanechávajúc za sebou štruktúry: dve dvojice blinkrov a jednu stabilnú štruktúru. Opakuje sa to s periódou cca 32.
• Noahova (Noemova) archa (Noah's ark) - Bafkač pozostávajúci z dvoch prepínačov (switch engine-ov). Periodu má 96 a posúva smerom vľavo hore s rychlosťou. Pomenovanie dostal podľa množstva štruktúr, ktoré za sebou zanecháva: bloky, blinkre, beehives, loaves, klzáky, lode, člny, dlhé člny, návestidlo a "blok na stole".
• Backrak (Backrake) - je modifikácia rake - spätný rake generujúci klzáky.

Generátor

• Metamorfózis 2(Methamorphosis II) - Štruktúra pozostávajúca z klzáku a LWSS-convertora. Na začiatku je vygenerovaná loď a zvyšná časť sa opakuje s periódou 30. Ak by sa na danom mieste klzáka umiestnil generátor klzákov, boli by generované lode do nekonečna.
• Klzák-Blok (Glider-Block) - Štruktúra pozostávajúca z bloku a dvoch klzákov, po spojení vytvoria dva klzáky a jeden blok.
• Dvoj hlavňová zbraň(Double barrelled gun) - Štruktúra používajúca B-heptomino, ktorá po vyprodukovaní prvého klzáku produkuje každú 52 generáciu klzák. Stred sa opakuje s periódou 104.
• Bočná streľba (Edge shooter) - Štruktúra odpaľujúca klzák z pravej strany. Používa sa na vytvorenie zložitejších štruktúr.

Rozbuška a Knôt

• Mravce (Edge shooter) - je to knôt, "horiaci" na oboch koncoch s rýchlosťou c . Na konci štruktúry vznikne stabilná štruktúra blok.
• Tvorca návestidiel (Beacon maker) - štruktúra s periódou 8. V 16stej generácii sa vytvorí prvé návestidlo. Pohybuje sa rýchlosťou svetla c, za sebou zanecháva štruktúru návestidlo. Blinker sa vytvorí na konci štruktúry.
• Vznik člnu(Boat maker) - štruktúra sa pohybuje rýchlosťou svetla c a za sebou zanecháva páry štruktúr čln.
• Krava (Cow) - štruktúra pohybujúca sa rýchlosťou svetla s periódou 8.
• Spätná rozbuška (Reverse fuse) -rozbuška produkujúca odpad, ktorý neskôr celkom zanikne.
• Kombajn (Harvester) - rozbuška pohybujúca sa smerom nahor zanechávajúca za sebou bloky s periódou 4. Názov je odvodený od toho , že produkuje odpad vo forme blokov, ktoré obsahujú taký istý počet buniek ako rozbuška spálila. Odpad pripomína zviazané snopy obilia resp. niekomu moze pripomínať aj trus :) z dinosaura pohybujúceho sa nahor.
• Ľahké vlákno (Lightspeed wire) - knôt spaľujúci sa nedeštruktívne pri rýchlosti svetla, ktorý môže byť použitý na posielanie signálu. Doteraz sa však nepodarilo nájsť spôsob posielania signálu späť.
• Umývajúca sa žena(Washerwoman) - štruktúra 2c/3 s periódou 18. Z pôvodného počtu buniek postupne vznikne 1/2 štvorice blinkrov.

Matuzalem

• B-hepto (B-hepto) - štruktúra, ktorá sa ustáli v 148 generácii na 3 blokoch, 2 klzákoch a 1 lodi. V generácii 20 sa vytvorí Hesel a jeden blok.
• Králik (Rabbit) - štruktúra, ktorá sa po 17 331 generácii ustáli s 39 klzákmi putujúcimi do nekonečná.
• R pentomino (R pentomino)- štruktúra pozostávajúca z 5tich buniek , ktoré sa ustália po 1103 generácii na 6 klzákoch, 8 blokoch, 4 blinkroch, 4 beehives, 1 člne, 1 lodi a 1 loaf. Je to najznámejšie aktívne polyomino s menej než šiestimi bunkami. Ostatné polyomina sa ustália po maximálne 10 generáciach.

Požierač

• Požierač (Eater)- štruktúra ustálená po desiatej generácii.
• Požierač (Eater1) - štruktúra nazývaná aj eater, schopná pohltiť akúkoľvek štruktúru.
• Požierač (Block eater) - požierač požierajúci stabilnú štruktúru blok. Počet živých buniek sa mení postupne 20, 24, 22. Celá štruktúra sa opakuje s periódou 4.

Čiara

• Čiara 4 (Line 4) - štruktúra je stabilná po tretej generácii na štruktúre Beehive so šiestimi živými bunkami.
• Čiara 5 (Line 5) - ustálenie štruktúry po siedmej generácii. Vytvoria sa 4 stabilné blinkre.
• Čiara 6 (Line 6) - štruktúra úplne zanikne po 12stej generácii.
• Čiara 7 (Line 7) - štruktúra je stabilná po 14stej generácii. Vytvorí štyri oproti sebe stojace Beehive.
• Čiara 8 (Line 8) - štruktúra je stabilná po 14stej generácii. Vytvorí štyry oprotisebe stojace Beehive.
• Čiara 9 (Line 9) - štruktúra po 20tej generácii vytvorí dva štvorité blinkre, ktoré sa opakujú s periódou 2.
• Čiara 10 (Line 10) - v 15stej generácii vznikne nová štruktúra, ktorá sa opakuje s periódou 15.
• Čiara 11 (Line 11) - v 15stej generácii vzniknú 2 blinkre, ktoré sa opakujú s periódou 2.
• Čiara 12 (Line 12) - v 15stej generácii vzniknú 2 stabilné beehive.
• Čiara 13 (Line 13) - v 24tej generácii vzniknú 2 blinkre, ktoré sa opakujú s periódou 2.
• Čiara 14 (Line 14) - v 28 generácii zanikne celá štruktúra.
• Čiara 15 (Line 15) - v 40tej generácii zanikne celá štruktúra.
• Čiara 16 (Line 16) - v 33tej generácii vznikne osmica blinkrov, ktoré sa opakujú s periódou 2.
• Čiara 17 (Line 17) - v 24tej generácii vzniknú 4 stabilné bloky.
• Čiara 18 (Line 18) - v 20tej generácii zanikne celá štruktúra.
• Čiara 19 (Line 19) - v 24tej generácii zanikne celá štruktúra.
• Čiara 20 (Line 20) - v 20tej generácii vzniknú dva stabilné bloky.
• Čiara ∞ (Line ∞) - nekonečne dlhá vodorovná čiara postupne vytvára svoje kópie navzájom vzdialené na štyri políčka v generácii 2^(m - 2) existuje 2^(m-1) čiar pre m=2, 3, 4, ...

Stabilné

• 4 bunky
  • Blok (Block) - stabilná štruktúra so 4 živými bunkami.
• 5 buniek
  • Čln (Boat)
• 6 buniek
  • Lietadlo (Aircraft carrier) - stabilná štruktúra pozostávajúca zo 6tich buniek.
• 11 buniek
  • Jedenástnik(Elevener)
• 15 buniek
  • Moose antlers (Moose antlers)
• 40 buniek
  • Požierač 4(Eator 4)

Rôzne

• Ohnivý prstenec (Ring fire) - prstenec po obvode ktorého sa s pravidelnými intervalmi pohybujú bunky v jednom smere vytvárajúc ilúziu horenia.
• Titanik (Titanic) - super reťazec s opakovaním sa segmentov. Štruktúra sa ustáli po 18 generácii na dvojici beehive.
• Tenisti (Relay) - dva požierače (pentadecathlony 15) s periódou 15, ktoré si odrážajú navzájom jeden klzák. Relay je vlastne oscilátor s periódou 60.
• Tkanivo (mesh) - zaujímavý je proces narušenia pravidelnej štruktúry "tkaniva" lokálnou "nákazou". "Tkanivo" je tvorené pravidelnou mriežkou stabilných blokov - štvoríc buniek. Tá tvorí stabilný obrazec. Keď "nákazu" vložíme do stredu štruktúry, potom si s ňou pôvodná štruktúra v priebehu dvoch generácií poradí. V prípade vloženia "nákazy" na iné miesto vo voľnom vnútornom riadku (stĺpci) štruktúry, dochádza postupne k úplnej deštrukcii pôvodného obrazca.
• Vznik lode (Boat genesis) - Trojica klzákov vytvorí v 14stej generácii jednu loď.
• Vznik klzákov (Glider genesis) - dvojica lodí vytvorí v 10 tej generácii dva klzáky.
• Filter (Filter) - slúži na zničenie niektorých, nie všetkých lodí pohybujúcich sa za sebou.