Autòmat cel·lular: diferència entre les revisions
Contingut suprimit Contingut afegit
Nou exemple: Autòmat de Von Neumann i variants Nobili i Hutton |
Nous exemples: Autòmat de Codd i bucles de Langton |
||
Línia 53:
Les cèl·lules, és a dir els [[autòmats finits]], estan disposades sobre un [[pla cartesià]] i interfereixen amb les [[Veïnat de Von Neumann|quatre cèl·lules veïnes]], formant diferents estats de transmissió de senyals, el resultat del qual pot ser la construcció o destrucció de circuits. Cada cèl·lula pot tenir 29 estats diferents, ordenats en cinc grups: buit, transitori, confluent, transmissor ordinari i transmissor especial. Així doncs, els estats "excitats" transporten dades, a la velocitat d'un bit per pas de transició d'estat i aplicant canvis sobre la graella.
Existeixen diverses variants similars; l''''autòmat de Nobili''' incorpora la capacitat de les cèl·lules confluents de creuar senyals i emmagatzemar informació, i l''''autòmat de Hutton''' permet replicar un bucle de dades anàleg als
L''''autòmat de Codd''' va ser proposat per [[Edgar F. Codd]] al 1968 per recrear la universalitat de càlcul i construcció de l'autòmat de von Neumann però amb només 8 estats.<ref name=Codd68>{{cite book|author=Codd, Edgar F.|title=Cellular Automata|publisher=Academic Press, New York|year=1968}}</ref> De forma similar, [[Edwin Roger Banks]] en va fer un de només 4 estats, anomenat '''autòmat ''Banks IV''''' però que finalment no va implementar.<ref name=Banks1971>{{cite book|title=Information Processing and Transmission in Cellular Automata|year=1971| first=Edwin| last=Banks|publisher=PhD thesis, MIT, Department of Mechanical Engineering|url=http://www.bottomlayer.com/bottom/banks/banks_commentary.htm}}</ref> Al 1973, [[John Devore]] va optimitzar l'autòmat de Codd per reduir-ne la mida de la màquina autoreplicant. [[Christopher Langton]] va fer una modificació de l'autòmat de Codd per crear els '''bucles de Langton''', els quals són autoreplicants amb moltes menys cel·les però ja no tenen universalitat de càlcul i construcció.<ref name=Langton84>{{cite journal|doi=10.1016/0167-2789(84)90256-2|title=Self-Reproduction in Cellular Automata|author=Langton, C. G.|year=1984| journal=Physica D: Nonlinear Phenomena|volume=10|issue=1-2|pages=135–144|url=https://deepblue.lib.umich.edu/bitstream/2027.42/24968/1/0000395.pdf}}</ref>
=== Bucles de Langton ===
[[Imatge:Langtons Loop Colony.png|miniatura|Colònia de bucles de Langton. Els del centre estan "morts".]]
Els '''bucles de Langton''' són "espècies" amb vida artificial que consisteixen en un bucle de cèl·lules que contenen [[informació genètica]], que flueix contínuament al voltant del bucle i surten al llarg d'un "braç" ([[pseudòpode]]) que es convertirà en el bucle fill. Els "gens" li indiquen que faci tres girs a l'esquerra, completant el bucle, que després es desconnecta del seu pare. Els bucles són incapaços de reproduir-se a l'espai que ocupa un altre bucle, per això un cop estan envoltats pels bucles fills es consideren "morts". Igual que amb l'autòmat de Codd, els bucles de Langton consisteixen en senyals que viatgen passivament al llarg dels circuits, fins que arriben als extrems oberts, on s'executa l'ordre que porten.
Els bucles de Langton formen tota una familia d'autòmats cel·lulars amb característiques similars:
* '''Bucles de Langton''' originals (1984) creats per [[Christopher Langton]].<ref name=Langton84/>
* '''Bucles de Byl''' (1989), amb una reducció de la mida del bucle al treure'n l'espai interior.<ref name=Byl1989>{{cite journal|author=J. Byl|title=Self-Reproduction in small cellular automata|journal=Physica D|volume=34|issue=1–2|pages=295–299|year=1989|doi=10.1016/0167-2789(89)90242-X}}</ref>
* '''Bucles de Chou-Reggia''' (1993), amb reducció total de les parets del bucle.<ref name=Reggia1993>{{cite journal |author1=J. A. Reggia |author2=S. L. Armentrout |author3=H.-H. Chou |author4=Y. Peng |title=Simple systems that exhibit self-directed replication|journal=Science|volume=259|pages=1282–1287|year=1993|doi=10.1126/science.259.5099.1282|pmid=17732248|issue=5099}}</ref>
* '''Bucles de Tempesti''' (1995), amb noves capacitats de construcció, permetent escriure patrons dins del bucle després de la reproducció.<ref name=Tempesti1995>{{cite conference|author=G. Tempesti|title=A New Self-Reproducing Cellular Automaton Capable of Construction and Computation|booktitle=Advances in Artificial Life, Proc. 3rd European Conference on Artificial Life|location=Granada, Spain|year=1995|publisher=Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Berlin|pages=555–563|citeseerx = 10.1.1.48.7578}}</ref>
* '''Bucles de Perrier''' (1996), fent-lo universalment computable.<ref name=Perrier1996>{{cite journal|author1=J.-Y. Perrier |author2=M. Sipper |author3=J. Zahnd |title=Toward a viable, self-reproducing universal computer|journal=Physica D|volume=97|issue=4 |pages=335–352|year=1996|doi=10.1016/0167-2789(96)00091-7|citeseerx=10.1.1.21.3200 }}</ref>
* '''Bucle SDSR''' (1998), amb un estat addicional que permet la dissolució d’estructures; cada bucle té una [[vida útil]] limitada i es dissol al final del seu cicle de vida. Això permet un creixement continu al llarg de les generacions.<ref name=Sayama1998>{{cite conference |first=Hiroki |last=Sayama |title=Introduction of Structural Dissolution into Langton's Self-Reproducing Loop|booktitle=Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life|pages=114–122|location=Los Angeles, California|year=1998|publisher=MIT Press |url=http://cseweb.ucsd.edu/~rik/alife6/papers/IN79.html}}</ref>
* '''Evoloop''' (1999), extensió del bucle SDSR que és capaç d'interaccionar amb bucles veïns, així com d'[[evolucionar]] a causa de la competència per l'espai, on la [[selecció natural]] afavoreix els bucles funcionals més petits.<ref name=Sayama1999>{{cite conference |first=Hiroki |last=Sayama |title=Toward the Realization of an Evolving Ecosystem on Cellular Automata|booktitle=Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th '99)|pages=254–257|location=Beppu, Oita, Japan|year=1999|citeseerx=10.1.1.40.391}}</ref><ref name=Salzberg2004>{{cite journal|author1=Chris Salzberg |author2=Hiroki Sayama |title=Complex genetic evolution of artificial self-replicators in cellular automata|journal=Complexity|volume=10|issue=2 |pages=33–39|year=2004|url=http://www3.interscience.wiley.com/journal/109860047/abstract|archive-url=https://archive.today/20130105090737/http://www3.interscience.wiley.com/journal/109860047/abstract|url-status=dead|archive-date=2013-01-05|doi=10.1002/cplx.20060}}</ref>
* '''Sexyloop''' (2007), modificació de l'Evoloop on els bucles auto-reproduïbles tenen la capacitat de [[reproducció sexual]]. Amb aquesta capacitat, els bucles són capaços de transferir [[material genètic]] a altres bucles. Això augmenta la diversitat en l'evolució de noves espècies de bucles.<ref name=Oros2007>{{cite conference|author1=Nicolas Oros |author2=C. L. Nehaniv |title=Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata|booktitle=The First IEEE Symposium on Artificial Life (April 1–5, 2007, Hawaii, USA)|pages=130–138|year=2007|hdl=2299/6711 }}</ref>
=== Joc de la vida ===
| |||