Langtonovy smyčky - Langtons loops - Wikipedia
Langtonovy smyčky jsou konkrétním "druhem" umělý život v buněčný automat vytvořil v roce 1984 Christopher Langton. Skládají se ze smyčky buněk obsahujících genetickou informaci, která nepřetržitě proudí kolem smyčky a ven podél „paže“ (nebo pseudopod ), která se stane dceřinou smyčkou. „Geny“ ho instruují, aby provedl tři otočení doleva a dokončil smyčku, která se poté odpojí od svého rodiče.
Dějiny
V roce 1952 John von Neumann vytvořil první celulární automat (CA) s cílem vytvořit a samoreplikační stroj.[1] Tento automat byl nutně velmi složitý díky své výpočetní a konstrukční univerzálnosti. V roce 1968 Edgar F. Codd snížil počet států z 29 v roce von Neumannova CA. do 8 palců jeho.[2] Když Christopher Langton odstranil podmínku univerzálnosti, dokázal výrazně snížit složitost automatu. Jeho samy se replikující smyčky jsou založeny na jednom z nejjednodušších prvků v Coddově automatu, periodickém emitoru.
Specifikace
Langtonovy smyčky běží v CA, která má 8 stavů a používá sousedství von Neumann s rotační symetrií. The přechodová tabulka naleznete zde: [1].
Stejně jako u Coddova CA „Langtonovy smyčky se skládají z opláštěných drátů. Signály cestují pasivně podél vodičů, dokud nedosáhnou otevřených konců, když je proveden povel, který nesou.
Kolonie
Kvůli zvláštní vlastnosti „pseudopodií“ smyček nejsou schopny reprodukovat se do prostoru obsazeného jinou smyčkou. Jakmile je tedy smyčka obklopena, není schopna reprodukce, což má za následek a korál - jako kolonie s tenkou vrstvou reprodukujících se organismů obklopujících jádro neaktivních „mrtvých“ organismů. Pokud nebude poskytnut neomezený prostor, bude velikost kolonie omezena. Maximální počet obyvatel bude asymptotické na , kde A je celková plocha prostoru v buňkách.
Kódování genomu
Genetický kód smyček je uložen jako řada párů nenulových stavů. Genom standardní smyčky je znázorněn na obrázku nahoře a lze jej označit jako řadu očíslovaných stavů, počínaje křižovatkou T a běžících ve směru hodinových ručiček: 70-70-70-70-70-70-40-40. Příkaz '70' posune konec drátu o jednu buňku, zatímco sekvence '40 -40 'způsobí odbočení vlevo. Stav 3 se používá jako dočasný marker pro několik fází.
Zatímco role států 0,1,2,3,4 a 7 jsou podobné Coddově CA, zbývající stavy 5 a 6 se místo toho používají ke zprostředkování procesu replikace smyčky. Po dokončení smyčky se stav 5 pohybuje proti směru hodinových ručiček podél pláště nadřazené smyčky do dalšího rohu, což způsobí, že další rameno bude vytvořeno jiným směrem. Stav 6 se dočasně připojí k genomu dceřiné smyčky a inicializuje rostoucí paži v dalším rohu, kam dosáhne.
Genom se používá celkem šestkrát: jednou k rozšíření pseudopodu na požadované místo, čtyřikrát k dokončení smyčky a znovu k převod genom do dceřiné smyčky. Je zřejmé, že to závisí na čtyřnásobku rotační symetrie smyčky; bez ní by smyčka nebyla schopna obsahovat informace potřebné k jejímu popisu. Stejné použití symetrie pro kompresi genomu se používá v mnoha biologických viry, tak jako icosahedral adenovirus.
| CA | počet států | sousedství | počet buněk (typický) | doba replikace (typická) | miniatura |
|---|---|---|---|---|---|
| Langtonovy smyčky[3] (1984): Původní samoreprodukující se smyčka. | 8 | von Neumann | 86 | 151 |  |
| Byl smyčka[4] (1989): Byl odstraněn vnitřní plášť a Byl zmenšen velikost smyčky. | 6 | von Neumann | 12 | 25 |  |
| Smyčka Chou-Reggia[5] (1993): Další redukce smyčky odstraněním všech obalů. | 8 | von Neumann | 5 | 15 |  |
| Smyčka Tempesti[6] (1995): Tempesti přidal do své smyčky konstrukční schopnosti, což umožnilo po reprodukci psát vzory do smyčky. | 10 | Moore | 148 | 304 |  |
| Perrierova smyčka[7] (1996): Perrier přidal do Langtonovy smyčky programový zásobník a rozšiřitelnou datovou pásku, což mu umožnilo vypočítat cokoli vypočitatelný. | 64 | von Neumann | 158 | 235 |  |
| Smyčka SDSR[8] (1998): S přidaným stavem rozpouštějícím strukturu do Langtonových smyček má smyčka SDSR omezenou životnost a rozpouští se na konci svého životního cyklu. To umožňuje neustálý růst a předávání generací. | 9 | von Neumann | 86 | 151 |  |
| Evoloop[9] (1999): Rozšíření smyčky SDSR, Evoloop je schopen interakce se sousedními smyčkami i vývoj. Největším selekčním tlakem v kolonii Evoloops je často soutěž o vesmír a přírodní výběr upřednostňuje nejmenší přítomnou funkční smyčku. Další studie prokázaly větší složitost, než se původně myslelo v systému Evoloop.[10] | 9 | von Neumann | 149 | 363 |  |
| Sexyloop[11] (2007): Sexyloop je modifikace Evoloopu, kde mají samoreprodukující se smyčky sex. Díky této schopnosti jsou smyčky schopné přenášet genetický materiál do dalších smyček. To zvyšuje rozmanitost ve vývoji nových druhů smyček. | 10 | von Neumann | 149 | 363 |  |
Viz také
- Umělý život - Studijní obor, ve kterém vědci pomocí simulací zkoumají systémy spojené s přírodním životem, jeho procesy a jeho vývojem
- Buněčný automat - Diskrétní model studovaný v informatice
- Christopher Langton - americký počítačový vědec
- Coddův buněčný automat - 2D buněčný automat navržený Edgarem F. Coddem v roce 1968
- Conwayova hra o život - Dvourozměrný buněčný automat navržený J. H. Conwayem v roce 1970
- Langtonův mravenec - Dvourozměrný Turingův stroj se vznikajícím chováním
- buněčný automat von Neumann - Mobilní model používaný k modelování univerzální konstrukce
Reference
- ^ von Neumann, John; Burks, Arthur W. (1966). "Teorie samoreprodukčních automatů.". www.walenz.org. Archivovány od originál (Naskenovaná kniha online) dne 01.01.2008. Citováno 2008-02-29.
- ^ Codd, Edgar F. (1968). Mobilní automaty. Academic Press, New York.
- ^ C. G. Langton (1984). „Vlastní reprodukce v celulárních automatech“ (PDF). Physica D. 10 (1–2): 135–144. doi:10.1016/0167-2789(84)90256-2. hdl:2027.42/24968.
- ^ J. Byl (1989). "Vlastní reprodukce v malých celulárních automatech". Physica D. 34 (1–2): 295–299. doi:10.1016 / 0167-2789 (89) 90242-X.
- ^ J. A. Reggia; S. L. Armentrout; H.-H. Chou; Y. Peng (1993). "Jednoduché systémy, které vykazují replikaci s vlastním zaměřením". Věda. 259 (5099): 1282–1287. doi:10.1126 / science.259.5099.1282. PMID 17732248.
- ^ G. Tempesti (1995). "Nový samoreprodukující se buněčný automat schopný konstrukce a výpočtu". Pokroky v umělém životě, Proc. 3. evropská konference o umělém životě. Granada, Španělsko: Přednášky v umělé inteligenci, 929, Springer Verlag, Berlín. str. 555–563. CiteSeerX 10.1.1.48.7578.
- ^ J.-Y. Perrier; M. Sipper; J. Zahnd (1996). "Směrem k životaschopnému, samoreprodukujícímu se univerzálnímu počítači". Physica D. 97 (4): 335–352. CiteSeerX 10.1.1.21.3200. doi:10.1016/0167-2789(96)00091-7.
- ^ Sayama, Hiroki (1998). „Zavedení strukturálního rozpuštění do Langtonovy samoreprodukující se smyčky“. Umělý život VI: Sborník ze šesté mezinárodní konference o umělém životě. Los Angeles, Kalifornie: MIT Press. str. 114–122.
- ^ Sayama, Hiroki (1999). "Směrem k realizaci vyvíjejícího se ekosystému na celulárních automatech". Sborník ze čtvrtého mezinárodního sympozia o umělém životě a robotice (AROB 4. '99). Beppu, Oita, Japonsko. str. 254–257. CiteSeerX 10.1.1.40.391.
- ^ Chris Salzberg; Hiroki Sayama (2004). „Složitá genetická evoluce umělých samoreplikátorů v celulárních automatech“. Složitost. 10 (2): 33–39. doi:10.1002 / cplx.20060. Archivovány od originál dne 05.01.2013.
- ^ Nicolas Oros; C. L. Nehaniv (2007). „Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata“. První IEEE sympozium o umělém životě (1. – 5. Dubna 2007, Havaj, USA). str. 130–138. hdl:2299/6711.
externí odkazy
- Video Chrise Langtona předvádějícího samoreprodukující se smyčky.
- vizuální reprezentace několika samoreplikujících se smyček v a Applet Java
- The Repozitář tabulky pravidel má přechodové tabulky pro mnoho výše uvedených CA.
- Golly - podporuje Langtonovy smyčky spolu s Hra o život a další sady pravidel.