Autómata celular elemental

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.

Imagen con las 256 reglas de autómata celular elemental​ (hacer click o tocar para ampliar).

El sistema de numeración

Existen 8 = 2³ 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 = 2²³ 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, 110_d=96_d+14_d escrito en binario es 01101110₂. 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

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

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

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:

${\frac {1+2x}{(1+x)(1-2x)}}$.

tiene la expresión de forma cerrada

$a(t)={\frac {4\cdot 2^{t}-(-1)^{t}}{3}}$

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

Regla 50

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

${\frac {1}{(1-x)(1-4x)}}$

Tiene la expresión de forma cerrada

$a(t)={\frac {4\cdot 4^{t}-1}{3}}$

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

Regla 54

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

${\frac {1+7x}{(1-x^{2})(1-16x^{2})}}$

Tiene la expresión de forma cerrada

$a(t)={\frac {22\cdot 4^{t}-6(-4)^{t}-4+3(-1)^{t}}{15}}$

Regla 60

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

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

${\displaystyle a(t)={\begin{cases}1,&{\mbox{if }}t=0\\[5px]7,&{\mbox{if }}t=1\\[7px]{\dfrac {1+5\cdot 4^{n}}{3}},&{\mbox{if }}t{\mbox{ is even otherwise}}\\[7px]{\dfrac {10+11\cdot 4^{n}}{6}},&{\mbox{if }}t{\mbox{ is odd otherwise}}\end{cases}}}$

Esta tiene función generadora

${\frac {(1+2x)(1+5x-16x^{4})}{(1-x^{2})(1-16x^{2})}}$

Regla 102

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

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.​

Regla 150

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

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

.${\frac {1+7x+12x^{2}-4x^{3}}{(1-x^{2})(1-16x^{2})}}$

Regla 188

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

${\frac {1+3x+4x^{2}+12x^{3}+8x^{4}-8x^{5}}{(1-x^{2})(1-16x^{4})}}$.

Regla 190

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

.${\frac {1+3x}{(1-x^{2})(1-4x)}}$

Regla 220

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

${\frac {1}{(1-x)(1-2x)}}$

Tiene la expresión de forma cerrada

$a(t)=2\cdot 2^{t}-1$

Notar que la regla 252 genera la misma secuencia.

Regla 222

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

${\frac {1+2x}{(1-x)(1-4x)}}$

Tiene la expresión de forma cerrada

$a(t)=2\cdot 4^{t}-1$

Notar que la regla 254 genera la misma secuencia.

Estado inicial aleatorio

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:

• 
  Regla 0
• 
  Regla 1
• 
  Regla 2
• 
  Regla 3
• 
  Regla 4
• 
  Regla 5
• 
  Regla 6
• 
  Regla 7
• 
  Regla 8
• 
  Regla 9
• 
  Regla 10
• 
  Regla 11
• 
  Regla 12
• 
  Regla 13
• 
  Regla 14
• 
  Regla 15
• 
  Regla 18
• 
  Regla 19
• 
  Regla 22
• 
  Regla 23
• 
  Regla 24
• 
  Regla 25
• 
  Regla 26
• 
  Regla 27
• 
  Regla 28
• 
  Regla 29
• 
  Regla 30
• 
  Regla 32
• 
  Regla 33
• 
  Regla 34
• 
  Regla 35
• 
  Regla 36
• 
  Regla 37
• 
  Regla 38
• 
  Regla 40
• 
  Regla 41
• 
  Regla 42
• 
  Regla 43
• 
  Regla 44
• 
  Regla 45
• 
  Regla 46
• 
  Regla 50
• 
  Regla 51
• 
  Regla 54
• 
  Regla 56
• 
  Regla 57
• 
  Regla 58
• 
  Regla 60
• 
  Regla 62
• 
  Regla 72
• 
  Regla 73
• 
  Regla 74
• 
  Regla 76
• 
  Regla 77
• 
  Regla 78
• 
  Regla 90
• 
  Regla 94
• 
  Regla 104
• 
  Regla 105
• 
  Regla 106
• 
  Regla 108
• 
  Regla 110
• 
  Regla 122
• 
  Regla 126
• 
  Regla 128
• 
  Regla 130
• 
  Regla 132
• 
  Regla 134
• 
  Regla 136
• 
  Regla 138
• 
  Regla 140
• 
  Regla 142
• 
  Regla 146
• 
  Regla 150
• 
  Regla 152
• 
  Regla 154
• 
  Regla 156
• 
  Regla 160
• 
  Regla 162
• 
  Regla 164
• 
  Regla 168
• 
  Regla 170
• 
  Regla 172
• 
  Regla 178
• 
  Regla 184
• 
  Regla 200
• 
  Regla 204
• 
  Regla 232

Casos inusuales

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.

Enlaces externos

• Weisstein, Eric W. «Elementary Cellular Automaton». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 30». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 50». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 54». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 60». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 62». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 90». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 94». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 102». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 110». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 126». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 150». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 158». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 182». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 188». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 190». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 220». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Rule 222». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q1875447
• Multimedia: Elementary cellular automata / Q1875447