Regla 184
La regla 184 és una regla d'autómata celular binari unidimensional, notable per resoldre el problema de la majoria, aixina com per la seua capacitat per a descriure simultàneament varis sistemes de partícules, aparentment molt diferents:
- La regla 184 pot utilisar-se com a model senzill del fluix de tràfic en un únic carril d'una autopista, i constituïx la base de molts models d'autómates celulars de fluix de tràfic en major sofisticació. En este model, les partícules (que representen als vehículs) es mouen en una única direcció, parant i arrancant en funció dels coches que tenen davant. El número de partícules permaneix invariable durant tota la simulació. Per esta aplicació, la regla 184 es denomina a voltes "regla del tràfic".[1]
- La regla 184 també modela una forma de deposición de partícules sobre una superfície irregular, en la que cada mínim local de la superfície s'ompli en una partícula en cada pas. En cada pas de la simulació, el número de partícules aumenta. Una volta colocada, una partícula mai es mou.
- La regla 184 pot entendre's en térmens d'aniquilació balística, un sistema de partícules que es mouen tant cap a l'esquerra com cap a la dreta a través d'un mig unidimensional. Quan dos partícules d'este tipo choquen, s'aniquilen mútuament, de modo que en cada pas el número de partícules permaneix invariable o disminuïx.
L'aparent contradicció entre estes descripcions es resol per mig de distintes formes d'associar característiques de l'estat de l'autómata en partícules.
El nom de la Regla 184 és un còdic Wolfram que definix l'evolució dels seus estats. Les primeres investigacions sobre la Regla 184 són de Li (1987)[2] i Krug & Spohn (1988).[3] En particular, Krug i Spohn ya descriuen els tres tipos de sistema de partícules modelats per la Regla 184.[4]
Definició
Un estat de l'autómata Regla 184 consistix en una matriu unidimensional de celes, cada una de les quals conté un valor binari (0 o 1). En cada pas de la seua evolució, l'autómata de la Regla 184 aplica la següent regla a cada una de les celes de la matriu, simultàneament per a totes les celes, per a determinar el nou estat de la cela:[5]
| Patró actual | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Nou estat per a la cela central | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Una entrada d'esta taula definix el nou estat de cada cela en funció de l'estat anterior i dels valors anteriors de les celes veïnes a abdós costats. El nom d'esta regla, Regla 184, és el còdic Wolfram que descriu la taula d'estats anterior: la fila inferior de la taula, 10111000, vista com un número binari, és igual al número decimal 184.[6]
El conjunt de regles de la norma 184 també pot descriure's intuitivament, de vàries maneres diferents:
- En cada pas, sempre que existixca en l'estat actual un 1 immediatament seguit d'un 0, estos dos símbols intercanvien els seus llocs. Basant-se en esta descripció, Krug i Spohn (1988) criden a la Regla 184 una versió determinista d'un « model cinètic de Ising en dinàmica asimètrica d'intercanvi d'espin».
- En cada pas, si una cela en valor 1 té una cela en valor 0 immediatament a la seua dreta, l'1 es mou cap a la dreta deixant un 0 darrere. Un 1 en un atre 1 a la seua dreta permaneix en el seu lloc, mentres que un 0 que no té un 1 a la seua esquerra seguix sent un 0. Esta descripció és molt adequada per a l'aplicació a la modelisació del fluix de tràfic.[7]
- Si una cela té estat 0, el seu nou estat es pren de la cela a la seua esquerra. En cas contrari, el seu nou estat es pren de la cela situada a la seua dreta. És dir, cada cela pot implementar-se per mig d'un demultiplexor bidireccional en el que les dos celes adjacents són entrades i la pròpia cela actua com a llínea selectora. El següent estat de cada cèlula ve determinat per l'eixida del demultiplexor. Esta operació està estretament relacionada en una porta Fredkin.[8]
Dinàmica i classificació majoritària
De les descripcions de les regles anteriors es desprenen immediatament dos propietats importants de la seua dinàmica. En primer lloc, en la regla 184, per a qualsevol conjunt finit de celes en condicions de frontera periòdiques, el número de 1s i el número de 0s en un patró permaneix invariante a lo llarc de l'evolució del patró. La Regla 184 i el seu reflex són els únics autómates celulars elementals no trivials[9] que tenen esta propietat de conservació del número.[10] De forma similar, si la densitat de 1s està ben definida per a un conjunt infinit de celes, permaneix invariante a mida que l'autómata porta a terme els seus passos.[11] I en segon lloc, encara que la regla 184 no és simètrica baix inversió esquerra-dreta, té una simetria diferent: invertint esquerra i dreta i intercanviant al mateix temps els papers dels símbols 0 i 1 es produïx un autómata celular en la mateixa regla d'actualisació.
Els patrons de la regla 184 solen estabilisar-se ràpidament, ya siga en un patró en el que els estats de les cèlules es mouen una posició cap a l'esquerra en cada pas, o en un patró que es mou una posició cap a la dreta en cada pas. Específicament, si la densitat inicial de cèlules en estat 1 és inferior al 50%, el patró s'estabilisa en grups de cèlules en estat 1, separades dos unitats, en els grups separats per blocs de cèlules en estat 0. Els patrons d'este tipo es mouen cap a la dreta. Els patrons d'este tipo es desplacen cap a la dreta. Si, pel contrari, la densitat inicial és superior al 50%, el patró s'estabilisa en agrupacions de cèlules en l'estat 0, separades dos unitats, en les agrupacions separades per blocs de cèlules en l'estat 1, i els patrons d'este tipo es mouen cap a l'esquerra. Si la densitat és exactament del 50%, el patró inicial s'estabilisa (més llentament) en un patró que pot considerar-se que es desplaça cap a l'esquerra o cap a la dreta a cada pas: una seqüència alterna de 0 i 1.[2]
El problema de la majoria és el problema de construir un autómata celular que, quan s'eixecuta en qualsevol conjunt finit de celes, puga calcular el valor que té la majoria de les seues celes. En cert sentit, la Regla 184 resol este problema de la següent manera: si la Regla 184 s'eixecuta en un conjunt finit de celes en condicions de contorn periòdiques, en un número desigual de 0s i 1s, llavors cada cela vorà dos estats consecutius del valor de la majoria infinitament a sovint, pero vorà dos estats consecutius del valor de la minoria només finitamente moltes voltes.[12] El problema de la majoria no pot resoldre's perfectament si es requerix que totes les cèlules s'estabilisen finalment en l'estat majoritari,[13] pero la solució de la Regla 184 evita este resultat d'impossibilitat relaixant el criteri pel qual l'autómata reconeix una majoria.
Referències
- ↑ Fukś, Henryk(1997).«"Solution of the density classification problem with two similar cellular automata rules"».Physical Review I.doi:10.1103/PhysRevE.55.R2081.
- ↑ 2,0 2,1 Li, Wentian(1987).«"Power spectra of regular languages and cellular automata"».Complex Systems.
- ↑ Krug, J.; Spohn, H.(1988).«"Universality classes for deterministic surface growth"».Physical Review A.doi:10.1103/PhysRevA.38.4271.
- ↑ Es poden trobar molts treballs posteriors que, en mencionar la Regla 184, citen els primers treballs de Stephen Wolfram. No obstant, els treballs de Wolfram només consideren autómates que són simètrics baix inversió esquerra-dreta, i per lo tant no descriuen la Regla 184.
- ↑ Esta taula de regles ya apareix de forma abreviada en el nom de «Regla 184», pero pot trobar-se explícitament, per eixemple, en Fukś (1997).
- ↑ Per a la definició d'este còdic, vore Wolfram (2002), p.53. Per al càlcul d'este còdic per a la regla 184, vore, per eixemple, Boccara & Fukś (1998).
- ↑ Boccara, Nino; Fukś, Henryk(1998).«"Cellular automaton rules conserving the number of active sites"».Journal of Physics A: Mathematical and General..doi:10.1088/0305-4470/31/28/014.
- ↑ Li, Wentian(1992).«"Phenomenology of nonlocal cellular automata"».Journal of Statistical Physics.doi:10.1007/BF01048877.
- ↑ Les regles 170, 204 i 240 exhibixen trivialmente esta propietat, ya que en cada una d'estes regles, cada cela és simplement copiada d'una de les tres celes per damunt d'ella en cada pas.
- ↑ Alonso-Sanz, Ramon (2011). Discrete Systems with Memory (en en), World Scientific. ISBN 978-981-4343-63-3. Consultat el 2024-11-16.
- ↑ Moreira, Andres(2003).«"Universality and decidability of number-conserving cellular automata".».Theoretical Computer Science.doi:10.1016/S0304-3975(02)00065-8.
- ↑ Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marque(1996).«"Two-state, r = 1 cellular automaton that classifies density"».Physical Review Letters..doi:10.1103/PhysRevLett.77.4969.
- ↑ Land, Mark; Belew, Richard(1995).«"No perfect two-state cellular automata for density classification exists".».Physical Review Letters.doi:10.1103/PhysRevLett.74.5148.
- Este artícul conté una traducció derivada de «Regla 184» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.