Autómatas celulares de una dimensión

De Bestiario del Hypogripho
Una animación de cómo se determina una evolución en la Regla 30, una de las 256 reglas posibles de los autómatas celulares elementales.

Este artículo tiene contenido abordado desde la perspectiva de la "vida real".   Este artículo tiene elementos que forman parte del Omniverso de los autómatas celulares.     Este artículo se compone de contenidos transcritos o recopilados por Avengium (Ángel Montero Lamas).  Este artículo está ilustrado con imágenes de Wikimedia Commons, ninguna otra persona, ningún autor adicional y nadie más. 

En matemáticas y teoría de la computabilidad, un autómata celular elemental es un autómata celular unidimensional donde hay dos estados posibles (etiquetados 0 y 1) y la regla para determinar el estado de una celda en la próxima generación depende solo del estado actual de la celda y sus dos vecinos inmediatos. Existe un autómata celular elemental (regla 110, definida a continuación) que es capaz de computación universal ya que es Turing Completo y, como tal, es uno de los modelos de computación más simples posibles.

El sistema de numeración[editar]

Hay 8 = 23 configuraciones posibles para una celda y sus dos vecinos inmediatos. La regla que define el autómata celular debe especificar el estado resultante para cada una de estas posibilidades de modo que haya 256 = 223 posibles autómatas celulares elementales. Stephen Wolfram propuso un esquema, conocido como el código Wolfram, para asignar a cada regla un número del 0 al 255 que se ha convertido en estándar. Cada posible configuración actual se escribe en orden, 111, 110, ..., 001, 000, y el estado resultante para cada una de estas configuraciones se escribe en el mismo orden y se interpreta como la representación binaria de un número entero. Este número se toma como el número de regla del autómata. Por ejemplo, 110d=011011102. Así que la regla 110 está definida por la regla de transición:

111 110 101 100 011 010 001 000 patrón actual P=(L,C,R)
0 1 1 0 1 1 1 0 nuevo estado para la célula del centro N110d=(C+R+C*R+L*C*R)%2

Reflexiones y complementos[editar]

Aunque hay 256 reglas posibles, muchas de ellas son trivialmente equivalentes entre sí hasta una simple transformación de la geometría subyacente. La primera de estas transformaciones es la reflexión a través de un eje vertical. El resultado de aplicar esta transformación a una regla determinada se denomina regla reflejada. Estas reglas exhibirán el mismo comportamiento hasta la reflexión a través de un eje vertical, por lo que son equivalentes en un sentido computacional.

Por ejemplo, si la definición de la regla 110 se refleja a través de una línea vertical, se obtiene la siguiente regla (regla 124):

111 110 101 100 011 010 001 000 patrón actual P=(L,C,R)
0 1 1 1 1 1 0 0 nuevo estado para la célula del centro N112d+12d=124d=(L+C+L*C+L*C*R)%2

Las reglas que son iguales a su regla reflejada se denominan anfiquirales. De los 256 autómatas celulares elementales, 64 son anfiquirales.

La segunda transformación de este tipo es intercambiar los roles de 0 y 1 en la definición. El resultado de aplicar esta transformación a una regla dada se denomina regla complementaria. Por ejemplo, si esta transformación se aplica a la regla 110, obtenemos la siguiente regla:

patrón actual 000 001 010 011 100 101 110 111
nuevo estado para la célula del centro 1 0 0 1 0 0 0 1

y, después de reordenar, descubrimos que esta es la regla 137:

patrón actual 111 110 101 100 011 010 001 000
nuevo estado para la célula del centro 1 0 0 0 1 0 0 1

Hay 16 reglas que son iguales a sus reglas complementarias.

Finalmente, las dos transformaciones anteriores se pueden aplicar sucesivamente a una regla para obtener la regla complementaria reflejada. Por ejemplo, la regla complementaria reflejada de la regla 110 es la regla 193. Hay 16 reglas que son iguales a sus reglas complementarias reflejadas.

De los 256 autómatas celulares elementales, hay 88 que no son equivalentes bajo estas transformaciones.

Historia con un solo 1[editar]

Un método utilizado para estudiar estos autómatas es seguir su historia con un estado inicial de todos los 0, excepto una sola celda con un 1. Cuando el número de regla es par (de modo que una entrada de 000 no se computa como 1) hace tiene sentido interpretar el estado en cada momento, t, como un número entero expresado en binario, produciendo una secuencia a(t) de números enteros. En muchos casos, estas sucesiones tienen expresiones simples de forma cerrada o tienen una función generadora con una forma simple.

Para una galeria de las 256 reglas con una sola célula activada en la configuración inicial, ver: c:Elementary cellular automata.

Configuración inicial aleatoria[editar]

Una segunda forma de investigar el comportamiento de estos autómatas es examinar su historia a partir de un estado aleatorio. Este comportamiento se puede entender mejor en términos de clases de Wolfram. Wolfram da los siguientes ejemplos como reglas típicas de cada clase.[r 1]

  • Clase 1: Autómatas celulares que convergen rápidamente a un estado uniforme. Ejemplos son las reglas 0, 32, 160 y 232.
  • Clase 2: Autómatas celulares que convergen rápidamente a un estado repetitivo o estable. Ejemplos son las reglas 4, 108, 218 y 250.
  • Clase 3: Autómatas celulares que parecen permanecer en un estado aleatorio. Ejemplos son las reglas 22, 30, 126, 150, 182.
  • Clase 4: autómatas celulares que forman áreas de estados repetitivos o estables, pero también forman estructuras que interactúan entre sí de formas complicadas. Un ejemplo es la regla 110. Se ha demostrado que la regla 110 es capaz de cómputo universal.[r 2]

Cada resultado calculado se coloca debajo de la fuente de ese resultado creando una representación bidimensional de la evolución del sistema.

En esta galería (click para viajar a wikimedia commons), se muestra esta evolución a partir de condiciones iniciales aleatorias para cada regla. Debajo de cada imagen se encuentra el número de regla utilizado para producir la imagen.[r 3] La regla reflejada produciría una imagen reflejada, mientras que la regla complementaria produciría una imagen con blanco y negro intercambiados.

Véase también[editar]

Referencias[editar]

Las Referencias aluden a las relaciones de un artículo con la "vida real".

⚜️[editar]

0
Avatar creador genérico W240.png
Este artículo utiliza contenido de Wikipedia que se publica bajo una licencia CC BY-SA, CC-BY-SA.svg.
Ver contribuidores de Elementary cellular automaton (en inglés)
 Avatar Avengium.png  Artículo transcrito por Avengium
Por favor, consulta rigurosamente las fuentes antes de cambiar o añadir algo a las transcripciones.
Icon libro 1.png