Codds celulární automat - Codds cellular automaton - Wikipedia

Jednoduchá konfigurace v Coddově celulárním automatu. Signály procházejí podél drátu vyrobeného z buněk ve stavu 1 (modrá), opláštěných buňkami ve stavu 2 (červená). Dva signální vlaky obíhají kolem smyčky a jsou duplikovány na křižovatce T na otevřenou část drátu. První (7-0) způsobí odhalení opláštěného konce drátu. Druhý (6-0) oplášťuje odkrytý konec a ponechává vodič o jeden článek delší než dříve.

Coddův buněčný automat je buněčný automat (CA) vytvořený britský počítačový vědec Edgar F. Codd v roce 1968. Byl navržen tak, aby znovu vytvořil výpočetní a konstrukční univerzálnost von Neumannova CA. ale s menším počtem stavů: 8 místo 29. Codd ukázal, že ve své CA je možné vyrobit samoreprodukční stroj, podobně jako von Neumannova univerzální konstruktor, ale nikdy nedal úplnou implementaci.

Dějiny

Ve 40. a 50. letech John von Neumann představoval následující problém:^[1]

Jaký druh logické organizace je dostačující, aby se automat dokázal reprodukovat?

Byl schopen postavit a buněčný automat s 29 státy as tím a univerzální konstruktor. Codd, navazující na práci von Neumanna, našel jednodušší stroj s osmi stavy.^[2] To upravilo von Neumannovu otázku:

Co je to za logickou organizaci nutné aby se automat dokázal sám reprodukovat?

Tři roky po Coddově práci ukázal Edwin Roger Banks ve své disertační práci čtyřstupňový CA, který byl také schopen univerzálního výpočtu a konstrukce, ale opět neimplementoval samoreprodukční stroj.^[3] John Devore ve své diplomové práci z roku 1973 upravil Coddova pravidla tak, aby výrazně zmenšil velikost Coddova designu, a to do té míry, že jej bylo možné implementovat do počítačů té doby. Datová páska pro vlastní replikaci však byla příliš dlouhá; Devoreův původní design byl později schopen dokončit replikaci pomocí Golly. Christopher Langton v roce 1984 provedl další vylepšení Coddova buněčného automatu Langtonovy smyčky, vykazující autoreplikaci s mnohem menším počtem buněk, než kolik potřebovalo pro vlastní reprodukci v předchozích pravidlech, za cenu odstranění možnosti univerzálního výpočtu a konstrukce.^[4]

Porovnání sad pravidel CA.

CA	počet států	symetrie	výpočetní a konstrukční - univerzální	velikost samoreprodukčního stroje
von Neumann	29	žádný	Ano	130 622 buněk
Codde	8	rotace	Ano	283 126 588 buněk^[5]
Devore	8	rotace	Ano	94 794 buněk
Banky IV (Mobilní automat Banks IV )	2 - 4 ^[6]^[7]	rotace a odrazy	Ano	Někde kolem 100 000 000 000 buněk
Langtonovy smyčky	8	rotace	Ne	86 buněk

Specifikace

Konstrukční rameno v Coddově CA lze přesunout do polohy pomocí příkazů uvedených v textu. Zde se rameno otočí doleva, pak doprava, pak napíše buňku, než se stáhne stejnou cestou.

Coddova CA má osm stavů určených a sousedství von Neumann s rotační symetrií.

Tabulka níže ukazuje návěstidla potřebná k provedení různých úkolů. Některé signální vlaky musí být na vodiči odděleny dvěma mezerami (stav 1), aby nedocházelo k rušení, takže signální řada „rozšířit“ použitá na obrázku nahoře se zde zobrazuje jako „70116011“.

účel	signální vlak
rozšířit	70116011
extend_left	4011401150116011
extend_right	5011501140116011
zatáhnout	4011501160116011
retract_left	5011601160116011
retract_right	4011601160116011
označit	701160114011501170116011
vymazat	601170114011501160116011
smysl	70117011
víčko	40116011
inject_sheath	701150116011
inject_trigger	60117011701160116011

Univerzální počítačový konstruktor

Na základě toho Codd navrhl počítač s automatickou replikací v celulárním automatu Wangův W-stroj. Návrh byl však tak kolosální, že se vyhnul implementaci až do roku 2009, kdy Tim Hutton vytvořil explicitní konfiguraci.^[5] V Coddově designu došlo k drobným chybám, takže Huttonova implementace se mírně liší, a to jak v konfiguraci, tak v sadě pravidel.

Viz také

Reference

^ von Neumann, John; Burks, Arthur W. (1966). "Teorie samoreprodukčních automatů.". www.walenz.org. Archivovány od originál dne 01.01.2008. Citováno 2012-01-28.
^ Codd, Edgar F. (1968). Mobilní automaty. Academic Press, New York.
^ Banks, Edwin (1971). Zpracování a přenos informací v celulárních automatech. Disertační práce, MIT, Katedra strojírenství.
^ Langton, C. G. (1984). „Vlastní reprodukce v celulárních automatech“ (PDF). Physica D: Nelineární jevy. 10 (1–2): 135–144. doi:10.1016/0167-2789(84)90256-2.
^ ^A ^b Hutton, Tim J. (2010). „Coddův samoreplikující se počítač“ (PDF). Umělý život. 16 (2): 99–117. doi:10.1162 / artl.2010.16.2.16200. PMID 20067401.
^ http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm
^ http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf

externí odkazy

The Repozitář tabulky pravidel má přechodová tabulka pro Coddovu CA.
Golly - podporuje Coddovu CA spolu s Hra o život a další sady pravidel.
Stáhněte si kompletní stroj (13 MB) a další podrobnosti.
[1] ukazuje více na Banks IV.

[vonNeumann66-1] von Neumann, John; Burks, Arthur W. (1966). "Teorie samoreprodukčních automatů.". www.walenz.org. Archivovány od originál dne 01.01.2008. Citováno 2012-01-28.

[Codd68-2] Codd, Edgar F. (1968). Mobilní automaty. Academic Press, New York.

[Banks1971-3] Banks, Edwin (1971). Zpracování a přenos informací v celulárních automatech. Disertační práce, MIT, Katedra strojírenství.

[Langton84-4] Langton, C. G. (1984). „Vlastní reprodukce v celulárních automatech“ (PDF). Physica D: Nelineární jevy. 10 (1–2): 135–144. doi:10.1016/0167-2789(84)90256-2.

[Hutton2010-5] A ^b Hutton, Tim J. (2010). „Coddův samoreplikující se počítač“ (PDF). Umělý život. 16 (2): 99–117. doi:10.1162 / artl.2010.16.2.16200. PMID 20067401.

[6] ttp://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm

[7] ttp://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]