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 como 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 , que se define a continuación) que es capaz de realizar cálculos universales y, como tal, es uno de los modelos de cálculo más simples posibles.
El sistema de numeración
Hay 8 = 2 3 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, por lo que hay 256 = 2 2 3 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 configuración actual posible 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, 110 d = 01101110 2 . Entonces, 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 celda central | N 110 días = (C + R + C * R + L * C * R)% 2 |
Reflexiones y complementos
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 transformación de este tipo es la reflexión a través de un eje vertical y 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 celda central | N 112 días +12 días = 124 días = (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 consiste en intercambiar los roles 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 |
---|---|---|---|---|---|---|---|---|
nuevo estado para la celda 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 |
---|---|---|---|---|---|---|---|---|
nuevo estado para la celda central | 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.
Historias individuales 1
Un método utilizado para estudiar estos autómatas es seguir su historial con un estado inicial de todos los ceros excepto una celda con un 1. Cuando el número de la regla es par (de modo que una entrada de 000 no se calcula en un 1) hace sentido para interpretar el estado en cada tiempo, 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 simples y cerradas o tienen una función generadora 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 la OEIS ). Esta es la secuencia de números de Jacobsthal y tiene función generadora
- .
Tiene la expresión de forma cerrada
La regla 156 genera la misma secuencia.
Regla 50
La secuencia generada es 1, 5, 21, 85, 341, 1365, 5461, 21845, ... (secuencia A002450 en la OEIS ). Esto tiene función generadora
- .
Tiene la expresión de forma cerrada
- .
Tenga en cuenta que las 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, ... (secuencia A118108 en la OEIS ). Esto tiene función generadora
- .
Tiene la expresión de forma cerrada
- .
Regla 60
La secuencia generada es 1, 3, 5, 15, 17, 51, 85, 255, ... (secuencia A001317 en la OEIS ). Esto se puede obtener tomando filas sucesivas del triángulo de Pascal módulo 2 e interpretándolas como números enteros en binario, que se pueden representar gráficamente mediante un triángulo de Sierpinski .
Regla 90
La secuencia generada es 1, 5, 17, 85, 257, 1285, 4369, 21845, ... (secuencia A038183 en la OEIS ). Esto se puede obtener tomando filas sucesivas del triángulo módulo 2 de Pascal e interpretándolas como números enteros en base 4. Tenga en cuenta que las reglas 18, 26, 82, 146, 154, 210 y 218 generan la misma secuencia.
Regla 94
La secuencia generada es 1, 7, 27, 119, 427, 1879, 6827, 30039, ... (secuencia A118101 en la OEIS ). Esto se puede expresar como
- .
Esto tiene función generadora
- .
Regla 102
La secuencia generada es 1, 6, 20, 120, 272, 1632, 5440, 32640, ... (secuencia A117998 en la OEIS ). Esta es simplemente la secuencia generada por la regla 60 (que es su regla del espejo) multiplicada por potencias sucesivas de 2.
Regla 110
La secuencia generada es 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, ... (secuencia A117999 en la OEIS ). La regla 110 tiene la propiedad quizás sorprendente de que es Turing completa y, por lo tanto, capaz de computación universal . [1]
Regla 150
La secuencia generada es 1, 7, 21, 107, 273, 1911, 5189, 28123, ... (secuencia A038184 en la OEIS ). Esto se puede obtener tomando los coeficientes de las potencias sucesivas de (1+ x + x 2 ) módulo 2 e interpretándolos como números enteros en binario.
Regla 158
La secuencia generada es 1, 7, 29, 115, 477, 1843, 7645, 29491, ... (secuencia A118171 en la OEIS ). Esto tiene función generadora
- .
Regla 188
La secuencia generada es 1, 3, 5, 15, 29, 55, 93, 247, ... (secuencia A118173 en la OEIS ). Esto tiene función generadora
- .
Regla 190
La secuencia generada es 1, 7, 29, 119, 477, 1911, 7645, 30583, ... (secuencia A037576 en la OEIS ). Esto tiene función generadora
- .
Regla 220
La secuencia generada es 1, 3, 7, 15, 31, 63, 127, 255, ... (secuencia A000225 en la OEIS ). Esta es la secuencia de números de Mersenne y tiene función generadora
- .
Tiene la expresión de forma cerrada
- .
Tenga en cuenta 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 la OEIS ). Esta es cualquier otra entrada en la secuencia de números de Mersenne y tiene función generadora
- .
Tiene la expresión de forma cerrada
- .
Tenga en cuenta que la regla 254 genera la misma secuencia.
Imágenes para las reglas 0-99
Estos comienzan con un solo píxel.
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 16
Regla 17
Regla 18
Regla 19
Regla 20
Regla 21
Regla 22
Regla 23
Regla 24
Regla 25
Regla 26
Regla 27
Regla 28
Regla 29
Regla 30
Regla 31
Regla 32
Regla 33
Regla 34
Regla 35
Regla 36
Regla 37
Regla 38
Regla 39
Regla 40
Regla 41
Regla 42
Regla 43
Regla 44
Regla 45
Regla 46
Regla 47
Regla 48
Regla 49
Regla 50
Regla 51
Regla 52
Regla 53
Regla 54
Regla 55
Regla 56
Regla 57
Regla 58
Regla 59
Regla 60
Regla 61
Regla 62
Regla 63
Regla 64
Regla 65
Regla 66
Regla 67
Regla 68
Regla 69
Regla 70
Regla 71
Regla 72
Regla 73
Regla 74
Regla 75
Regla 76
Regla 77
Regla 78
Regla 79
Regla 80
Regla 81
Regla 82
Regla 83
Regla 84
Regla 85
Regla 86
Regla 87
Regla 88
Regla 89
Regla 90
Regla 91
Regla 92
Regla 93
Regla 94
Regla 95
Regla 96
Regla 97
Regla 98
Regla 99
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. [2]
- Clase 1: Autómatas celulares que convergen rápidamente a un estado uniforme. Algunos ejemplos son las reglas 0, 32, 160 y 232.
- Clase 2: Autómatas celulares que convergen rápidamente a un estado repetitivo o estable. Algunos ejemplos son las reglas 4, 108, 218 y 250.
- Clase 3: Autómatas celulares que parecen permanecer en un estado aleatorio. Algunos 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 realizar cálculos universales . [3]
Cada resultado calculado se coloca bajo la fuente de ese resultado creando una representación bidimensional de la evolución del sistema. Las 88 reglas desiguales son las siguientes, desarrolladas 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 una Clase 4. Pero en estas interacciones, al menos una de las estructuras se aniquila, por lo que el autómata finalmente entra en un estado repetitivo y el autómata celular es de Clase 2. [4]
La regla 73 es de clase 2 [5] porque cada vez que hay dos unos consecutivos rodeados de ceros, esta característica se conserva en las generaciones sucesivas. Esto crea efectivamente muros que bloquean el flujo de información entre diferentes partes de la matriz. Hay un número finito de configuraciones posibles en la sección entre dos paredes, por lo que el autómata debe comenzar a repetirse dentro de cada sección, aunque el período puede ser muy largo si la sección es lo suficientemente ancha. Estos muros se formarán con probabilidad 1 para condiciones iniciales completamente aleatorias. Sin embargo, si se agrega la condición de que las longitudes de las corridas de 0 o 1 consecutivos siempre deben ser impares, entonces el autómata muestra un comportamiento de Clase 3 ya que las paredes nunca se pueden formar.
La regla 54 es de clase 4 [6] y también parece ser capaz de realizar cálculos universales, pero no se ha estudiado tan a fondo como la regla 110. Se han catalogado muchas estructuras que interactúan y que, en conjunto, se espera que sean suficientes para la universalidad. [7]
Referencias
- Weisstein, Eric W. "Autómata celular elemental" . MathWorld .
- Weisstein, Eric W. "Regla 30" . MathWorld .
- Weisstein, Eric W. "Regla 50" . MathWorld .
- Weisstein, Eric W. "Regla 54" . MathWorld .
- Weisstein, Eric W. "Regla 60" . MathWorld .
- Weisstein, Eric W. "Regla 62" . MathWorld .
- Weisstein, Eric W. "Regla 90" . MathWorld .
- Weisstein, Eric W. "Regla 94" . MathWorld .
- Weisstein, Eric W. "Regla 102" . MathWorld .
- Weisstein, Eric W. "Regla 110" . MathWorld .
- Weisstein, Eric W. "Regla 126" . MathWorld .
- Weisstein, Eric W. "Regla 150" . MathWorld .
- Weisstein, Eric W. "Regla 158" . MathWorld .
- Weisstein, Eric W. "Regla 182" . MathWorld .
- Weisstein, Eric W. "Regla 188" . MathWorld .
- Weisstein, Eric W. "Regla 190" . MathWorld .
- Weisstein, Eric W. "Regla 220" . MathWorld .
- Weisstein, Eric W. "Regla 222" . MathWorld .
- ^ Cook, Matthew (25 de junio de 2009). "Una visión concreta del cálculo de la regla 110" . Procedimientos electrónicos en informática teórica . 1 : 31–55. doi : 10.4204 / EPTCS.1.4 . ISSN 2075-2180 .
- ^ Stephen Wolfram, Un nuevo tipo de ciencia p223 ff.
- ^ Regla 110 - Wolfram | Alpha
- ^ Regla 62 - Wolfram | Alpha
- ^ Regla 73 - Wolfram | Alpha
- ^ Regla 54 - Wolfram | Alpha
- ^ Martínez, Genaro Juárez; Adamatzky, Andrew; McIntosh, Harold V. (1 de abril de 2006). "Fenomenología de colisiones de planeadores en autómatas celulares Regla 54 y puertas lógicas asociadas" (PDF) . Caos, solitones y fractales . 28 (1): 100-111. doi : 10.1016 / j.chaos.2005.05.013 . ISSN 0960-0779 .
enlaces externos
- "Autómatas celulares elementales" en el Atlas de programas simples de Wolfram
- Dibujo ejecutable MS-DOS de 32 bytes de largo por autómata celular ( Regla 110 por defecto)
- Un escaparate de todas las reglas elegidas al azar.
- Emulación de CA mínima con analizador de reglas Wolfram en línea en Javascript vanilla