Autómata celular elemental que muestra un comportamiento eventualmente periódico tras un gran número de iteraciones.

Question

En este vídeo:

Autómatas celulares y regla 30

Stephen Wolfram habla de ese autómata celular elemental en el minuto 17:01. Alguien tiene idea de cuál es exactamente el que podría estar hablando?

Answer 1

Hay más detalles -bastantes más detalles- en el original Anuncio de los premios de la Regla 30 en el blog de Stephen Wolfram. En particular, la regla específica se nombra allí:

He aquí un ejemplo un tanto curioso -encontrado mediante una búsqueda- de una regla con 4 colores posibles (código totalista 150898). Ejecútalo durante 200 pasos, y la columna central parece bastante aleatoria:
[Imagen 1]
Después de 500 pasos, todo el patrón sigue pareciendo bastante aleatorio:
[Imagen 2]
Pero si uno se acerca a la columna central, hay algo sorprendente: después de 251 pasos, la columna central parece evolucionar hacia un valor fijo (o al menos se mantiene fijo durante más de un millón de pasos):
[Imagen 3]

Resulta que el código de Mathematica para generar las imágenes (y así simular la regla) también está oculto en la entrada del blog; seleccionando y copiando la primera imagen de la página, por ejemplo, se obtiene el siguiente fragmento de código:

ArrayPlot[
 CellularAutomaton[{150898, {4, 1}, 1}, {{1}, 0}, {200, 150 {-1, 1}}],
  ColorRules -> {0 -> Hue[0.12, 1, 1], 1 -> Hue[0, 0.73, 0.92], 
   2 -> Hue[0.13, 0.5, 1], 3 -> Hue[0.17, 0, 1]}, 
 PixelConstrained -> 2, Frame -> False]

Si prefieres no intentar averiguar qué hace ese código, creo que ANKOS página 60 (molesta, la entrada del blog enlaza con la página 61) describe la convención de Wolfram para la numeración de las reglas de CA totalistas 1D y cómo decodificarlas y simularlas. En concreto:

1. Escribe el número de la regla en base $n$ con $w(n-1)+1$ dígitos, donde $n$ es el número de estados y $w$ es la anchura del barrio (aquí aparentemente se toma 3 por defecto). Por ejemplo, 150898 escrito en base 4 con 10 dígitos es 0210311302 ₄ .
2. Para aplicar la regla CA, sustituya el estado de cada celda (numerada de 0 a $n-1$ ) con el $k$ -ésima cifra por la derecha en la base $n$ número de la regla (contando desde cero, es decir, el dígito más a la derecha se numera como 0 y el más a la izquierda como $w(n-1)$ ), donde $k$ es la suma de los estados de todos los $w$ células en la vecindad de esta célula (incluida la propia célula).

Sólo para confirmar que la decodificación y la aplicación de la regla de esta manera realmente produce una salida que coincide con las imágenes de la entrada del blog, aquí hay un simple programa de Python para simular esta regla en una red envolvente finita:

rule = 150898
states = 4
width = 3

# decode rule number
table = tuple((rule // states**k) % states for k in range(width*(states-1)+1))

# initial cell states
cells = ((0,) * 20) + (1,) + ((0,) * 20)

# transition function
def new_state(i):
    neighbors = (cells[(i + j - width // 2) % len(cells)] for j in range(width))
    return table[sum(neighbors)]

for t in range(20):
    print("".join(str(s) for s in cells))
    cells = tuple(new_state(i) for i in range(len(cells)))

Pruébelo en línea.

Simulando esta regla en un entramado lo suficientemente amplio, partiendo de una única celda 1 sobre un fondo de celdas 0, se puede observar que la celda central acaba por quedarse atascada en el estado 1 mientras que sus vecinas alternan de forma casi aleatoria entre los estados 1 y 3. De hecho, examinando el código de la regla base-4, no es demasiado difícil ver por qué esta configuración particular en el centro de un patrón simétrico es invariante bajo la regla:

• Como regla totalista, la función de transición de estado es necesariamente simétrica a la izquierda/derecha. Por lo tanto, la evolución temporal de cualquier patrón inicial simétrico en el espejo necesariamente permanece simétrica. En particular, esto implica que los dos vecinos de la célula central siempre tendrán el mismo estado.
• Si la célula central está en el estado 1 y sus dos vecinas en el estado 1 o 3, la suma de los estados de las vecinas de la célula central es 1+1+1 = 3 o 3+1+3 = 7. Mirando el código de la regla de base 4, podemos ver que los dígitos 3 y 7 (contando de derecha a izquierda desde cero) son ambos 1.
• Además, si una célula está en el estado 1 o 3, y una de sus vecinas está en el estado 1, entonces la suma de los estados de sus vecinas debe estar entre 1+1+0 = 2 y 1+3+3 = 7 inclusive. Volviendo a mirar el código de la regla de base 4, podemos ver que, de los dígitos 2-7, casi todos son o bien 1 o bien 3. La única excepción es el dígito 6, que es 0; la única forma en que esta suma puede surgir bajo estas restricciones es como 1+3+2 = 6, es decir, si la propia célula está en el estado 3 y su otro vecino está en el estado 2.
• Sin embargo, un poco más de examen de la cadena de reglas muestra que no hay ninguna configuración posible de cuatro celdas de la forma " $1xyz$ ", donde $x \in \{1,3\}$ que podría dar lugar a la configuración " $32$ " para sus dos celdas centrales en el siguiente paso de tiempo. En concreto, para que la celda central izquierda se convierta en 3, $1+x+y$ debe ser 2 o 5. Por lo tanto, o bien $x = 1$ y $y = 0$ , $x = 1$ y $y = 3$ o $x = 3$ y $y = 1$ . En el primer caso, $1 \le x+y+z \le 4$ en los dos últimos, $4 \le x+y+z \le 7$ . Pero para que la célula central derecha se convierta en 2, $x+y+z$ debe ser 0 u 8, lo cual es imposible.

Así, una vez que las cinco columnas centrales de un patrón centralmente simétrico bajo esta regla terminan en la configuración " $a111a$ " o " $b313b$ ", donde $a$ es cualquier estado y $b$ es cualquier estado distinto de 2, no pueden volver a entrar en ninguna configuración que no sea de este tipo.