Ir al contenido

Autómata celular elemental

De Wikipedia, la enciclopedia libre
Imagen con las 256 reglas de autómata celular elemental[1]​ (hacer click o tocar para ampliar).

En matemáticas y teoría de 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 célula en la próxima generación depende solo del estado actual de la célula y sus dos vecinos inmediatos. Este es uno de los modelos posibles más sencillos de computación. No obstante, hay un autómata celular elemental (regla 110, definido abajo) capaz de computación universal.

El sistema de numeración

[editar]

Existen 8 = 23 configuraciones posibles para una célula y sus dos vecinos inmediatos. La regla que define el autómata celular tiene que especificar el estado resultante para cada una de estas posibilidades, es decir, que hay 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 de 0 a 255. Cada configuración actual posible está escrita en orden, 111, 110, ..., 001, 000, y el estado resultante para cada una de estas configuraciones está escrito en el mismo orden e interpretado 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=96d+14d escrito en binario es 011011102. De modo que la regla 110 se define mediante 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 Estado nuevo para el centro de la célula N110d=(C+R+C*R+L*C*R)%2

Reflexiones y complementos

[editar]

A pesar de que hay 256 reglas posibles, muchas de estas son equivalentes a las demás a través de una transformación sencilla de la geometría subyacente. La primera transformación de este tipo es reflexión a través de un eje vertical y el resultado de aplicar esta transformación a una regla dada se denomina regla reflejada. Estas reglas exhibirán el mismo comportamiento hasta la reflexión a través de un eje vertical, y por lo tanto 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 Estado nuevo para la célula central N112d+12d=124d=(L+C+L*C+L*C*R)%2

Las reglas que son las mismas que su regla reflejada se llaman amphichiral . De los 256 autómatas celulares elementales, 64 son anfíquicos.

La segunda transformación de este tipo consiste en intercambiar las funciones de 0 y 1 en la definición. El resultado de aplicar esta transformación a una regla dada se llama 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
Estado nuevo para la célula central 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
Estado nuevo para la célula central 1 0 0 0 1 0 0 1

Hay 16 reglas que son las mismas que sus reglas complementarias.

Finalmente, las dos transformaciones anteriores pueden aplicarse 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 son desiguales bajo estas transformaciones.

Solo 1 historias

[editar]

Un método utilizado para estudiar estos autómatas es seguir su historia con un estado inicial de todos ceros (0) excepto para una sola célula con un 1. Cuando el número de regla es par (de modo que una entrada de 000 no computa 1) 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 secuencias tienen expresiones de forma cerrada o tienen una función de generación con una forma simple. Las siguientes reglas son notables:

Regla 28

[editar]

La secuencia generada es 1, 3, 5, 11, 21, 43, 85, 171, ... (secuencia A001045 en el OEIS). Esta es la secuencia de números Jacobsthal y tiene la función generadora:

.

tiene la expresión de forma cerrada

Tener en cuenta que la regla 156 genera la misma secuencia.

Regla 50

[editar]

La secuencia generada es 1, 5, 21, 85, 341, 1365, 5461, 21845, ... ( secuencia A002450 en el OEIS ). Esta tiene función generadora

Tiene la expresión de forma cerrada

Nota que reglas 58, 114, 122, 178, 186, 242 y 250 generan la misma secuencia.

Regla 54

[editar]

La secuencia generada es 1, 7, 17, 119, 273, 1911, 4369, 30583, ... ((sucesión A118108 en OEIS) A118108 OEIS). Esta tiene función generadora:

Tiene la expresión de forma cerrada

Regla 60

[editar]

La secuencia generada es 1, 3, 5, 15, 17, 51, 85, 255, ... ((sucesión A001317 en OEIS) A001317 OEIS). Esto puede ser obtenido de tomar filas sucesivas del triángulo de Pascal módulo 2 e interpretándolas como números enteros en binario, los cuales pueden ser representados gráficamente por un Triángulo de Sierpinski.

Regla 90

[editar]

La secuencia generada es 1, 5, 17, 85, 257, 1285, 4369, 21845, ... ((sucesión A038183 en OEIS) A038183 OEIS). Esto puede ser obtenido por tomar filas sucesivas del triángulo de Pascal módulo 2 e interpretándolas como enteros en base 4. Notar que las reglas 18, 26, 82, 146, 154, 210 y 218 generan la misma secuencia.

Regla 94

[editar]

Esta tiene función generadora

Regla 102

[editar]

La secuencia generada es 1, 6, 20, 120, 272, 1632, 5440, 32640, ... ( secuencia A117998 en el OEIS ). Esta es la secuencia generada por la regla 60 (que es su regla espejo) multiplicada por potencias sucesivas de 2.

Regla 110

[editar]

La secuencia generada es 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, ... (sucesión A117999 en OEIS). La regla 110 tiene quizás la sorprendente propiedad de ser un Turing completo, y por ello ser capaz de ser una Máquina de Turing universal.[2]

Regla 150

[editar]

La secuencia generada es 1, 7, 21, 107, 273, 1911, 5189, 28123, ... ( secuencia A038184 en el OEIS ). Esta puede obtenerse tomando los coeficientes de las potencias sucesivas de (1+ x + x 2 ) módulo 2 e interpretándolas como números enteros en binario.

Regla 158

[editar]

La secuencia generada es 1, 7, 29, 115, 477, 1843, 7645, 29491, ... ( secuencia A118171 en el OEIS ). Esta tiene función generadora

.

Regla 188

[editar]

La secuencia generada es 1, 3, 5, 15, 29, 55, 93, 247, ... ( secuencia A118173 en el OEIS ). Esta tiene función generadora

.

Regla 190

[editar]

La secuencia generada es 1, 7, 29, 119, 477, 1911, 7645, 30583, ... ( secuencia A037576 en el OEIS ). Esta tiene función generadora

.

Regla 220

[editar]

La secuencia generada es 1, 3, 7, 15, 31, 63, 127, 255, ... ((sucesión A000225 en OEIS) A000225 OEIS). Esta es la secuencia de números de Mersenne y tiene función generadora

Tiene la expresión de forma cerrada

Notar que la regla 252 genera la misma secuencia.

Regla 222

[editar]

La secuencia generada es 1, 7, 31, 127, 511, 2047, 8191, 32767, ... ( secuencia A083420 en el OEIS ). Esta es cualquier otra entrada en la secuencia de números de Mersenne y tiene la función generadora

Tiene la expresión de forma cerrada

Notar que la regla 254 genera la misma secuencia.

Estado inicial aleatorio

[editar]

Una segunda forma de investigar el comportamiento de estos autómatas es examinar su historia comenzando con 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..

  • 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 maneras complicadas. Un ejemplo es la regla 110 . Se ha demostrado que la regla 110 es capaz de computación universal.

Cada resultado calculado se coloca bajo la fuente de resultados que crea una representación bidimensional de la evolución del sistema. Las 88 reglas inequitativas son las siguientes, evolucionadas a partir de condiciones iniciales aleatorias:

Casos inusuales

[editar]

En algunos casos el comportamiento de un autómata celular no es inmediatamente obvio. Por ejemplo, para la Regla 62, las estructuras que interactúan se desarrollan como en un Clase 4. Pero en estas interacciones al menos una de las estructuras es aniquilada por lo que el autómata eventualmente entra en un estado repetitivo y el autómata celular es Clase 2.

La regla 73 es clase 2 ya que en cualquier momento hay dos unos (1) consecutivos rodeados por ceros (0), esta característica se conserva en generaciones sucesivas. Esto crea efectivamente paredes que bloquean el flujo de información entre las diferentes partes de la matriz. Hay un número finito de posibles configuraciones en la sección entre dos paredes por lo que el autómata debe eventualmente empezar repitiendo dentro de cada sección, aunque el período puede ser muy largo si la sección es lo suficientemente ancha. Estas paredes se formarán con probabilidad 1 para las condiciones iniciales completamente aleatorias. Sin embargo, si se añade la condición de que las longitudes de ciclos consecutivos de ceros (0) o unos (1) deben ser siempre impares, entonces el autómata muestra un comportamiento de Clase 3 ya que las paredes nunca pueden formarse.

La regla 54 es la clase 4, pero sigue siendo desconocida si es capaz de computación universal. Se forman estructuras que interactúan, pero las estructuras que son útiles para la computación todavía no se han encontrado.

Referencias

[editar]
  1. R.Ugalde, Laurence. «Elementary cellular automaton in the Fōrmulæ programming language». Fōrmulæ. Consultado el 9 de junio de 2024. 
  2. Cook, Matthew (25 de junio de 2009). «A Concrete View of Rule 110 Computation». Electronic Proceedings in Theoretical Computer Science (1): 31-55. ISSN 2075-2180. arXiv:0906.3248. doi:10.4204/EPTCS.1.4. 

Enlaces externos

[editar]