11.2: Ejemplos de reglas simples de autómatas celulares binarios

Última actualización
Guardar como PDF

Page ID: 115741

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Regla de mayoría Los dos ejercicios de la sección anterior eran en realidad ejemplos de CA con una función de transición de estado llamada regla de mayoría (también conocida como regla de votación). En esta regla, cada celda cambia su estado a una opción de mayoría local dentro de su vecindario. Esta regla es tan simple que puede generalizarse fácilmente a diversos ajustes, como el espacio multidimensional, estados múltiples, mayor tamaño de vecindad, etc. Tenga en cuenta que todos los estados son estados quiescentes en esta CA. Se sabe que este modelo de CA se autoorganiza en parches geográficamente separados hechos de distintos estados, dependiendo de las condiciones iniciales. La Figura 11.4 muestra un ejemplo de una CA 2-D basada en reglas mayoritarias con estados binarios (blanco y negro), cada uno de los cuales está presente con igual probabilidad en la condición inicial.

Fig. 11.4.PNG — Figura$\PageIndex{1}$*: Comportamiento típico de CA binaria con un vecindario Moore gobernado por la regla mayoritaria.*

Regla de paridad La regla de paridad, también llamada regla XOR (OR exclusiva), es otra función de transición de estado bien conocida para CA. Su función de transición de estado se define matemáticamente como
\[s_{t+1}(x) = \sum_{i=0}^{n-1} s_{t}(x+x_i) \qquad{(mod \ k),} \label{(11.2)} \]

donde$k$ es el número de estados ($k = 2$para CA binaria). Se sabe que, en esta CA, cualquier patrón arbitrario incrustado en la configuración inicial se replica y se propaga por el espacio indefinidamente. La Figura 11.2.2 muestra ejemplos de tales comportamientos. De hecho, esta característica autorreplicativa es universal para todos los CA con reglas de paridad, independientemente del número de estados ($k$) o el radio de vecindad ($r$). Esto se debe a que, bajo esta regla, el patrón de crecimiento creado a partir de una sola celda activa (Fig. 11.2.2, fila superior) no interactúa con otros patrones de crecimiento que se crean a partir de otras celdas activas (es decir, son “independientes” entre sí). Cualquier patrón futuro de cualquier configuración inicial puede predecirse mediante una simple superposición de tales patrones de crecimiento.

Game of Life El último ejemplo es el CA binario 2-D más popular, llamado el “Juego de la Vida”, creado por el matemático John Conway. Desde su popularización por Martin Gardner en Scientific American a principios de la década de 1970 [35, 36], Game of Life ha atraído mucho interés de investigadores y aficionados a las matemáticas/computadoras de todo el mundo, debido a sus comportamientos fascinantes, altamente no triviales. Su función de transición de estado utiliza el barrio Moore y se inspira en el nacimiento y muerte de organismos vivos y su dependencia de la densidad poblacional, de la siguiente manera:

Una célula muerta (quiescente) se convertirá en una célula viva (activa) si y sólo si está rodeada por exactamente tres células vivas.

$Fig. 11.5 Arriba Row.PNG$

Fig. 11.5 Abajo Row.PNG — Figura$\PageIndex{2}$*: Comportamientos típicos de CA binaria con un vecindario de von Neumann gobernado por la regla de paridad (XOR).*

Una célula viva permanecerá viva si y sólo si está rodeada por otras dos o tres células vivas. De lo contrario morirá.

El Juego de la Vida muestra comportamientos bastante dinámicos, casi reales (Fig. 11.3.1). Se han descubierto muchas características intrigantes sobre este juego, incluyendo sus propiedades estadísticas, universalidad computacional, la posibilidad de la aparición de criaturas autorreplicativas dentro de él, y así sucesivamente. A menudo se considera una de las raíces históricas de la Vida Artificial ¹, un área de investigación interdisciplinaria que tiene como objetivo sintetizar sistemas vivos utilizando materiales no vivos. La comunidad de vida artificial surgió en la década de 1980 y creció junto con la comunidad de sistemas complejos, y así estas dos comunidades están estrechamente relacionadas entre sí. Los autómatas celulares han sido un marco de modelado popular utilizado por investigadores de vida artificial para modelar dinámicas autorreplicativas y evolutivas de organismos artificiales [37, 38, 39, 40].

¹ http://alife.org/