El autómata celular Ulam-Warburton

El autómata celular Ulam-Warburton (UWCA) genera un patrón fractal bidimensional usando autómatas celulares con vecindad de von Neumann con dos estados: encendido y apagado. Comienzan con una celda encendida(generalmente el central) y los demás apagadas. La regla que genera el autómata es muy sencilla, si tienes un único vecino encendido cambias tu estado a encendido. Cuando una celda se enciende ya no se apaga.
Por motivos de visualización se puede añadir un nuevo estado que sería “recién encendido” ese estado lo tienen las céldas que acaban de cambiar de estado y solo dura un ciclo antes de cambiar a encendido.

En el ejemplo cada estado viene indicado con un color:

  • negro: apagado
  • blanco: encendido
  • rojo: recién encendido

Se puede probar en este simulador https://cubiwan.github.io/cellularAutomataExamples/UlamWarburton.html y el código puede verse aquí.

Veamos algo de teoría, a partir del segundo ciclo el número de celdas nuevas en cada ciclo sigue esta formula:

Donde wt corresponde a :

¿Cómo calculamos el sumatorio hasta infinito? Vamos a hacerlo de una forma matemáticamente poco elegante y burda pero fácil de entender. Como 2^k crece muy rápido vamos a calcular el sumatorio solo de los primeros 30 valores (y con menos también serviría).

Debajo dejo el código JS para calcular el valor de wt y de u:

function sumWt(n, k){
    if(k == 0) {
        return 0;
    } else {
        return sumWt(n, k-1)+Math.floor(n/Math.pow(2,k))
    }
}

function wt(n){
    return n - sumWt(n, 30) //calcular hasta k = 30;
}

function u(n){
    return 4/3 * Math.pow(3, wt(n-1));
}

Vamos a calcular unos cuantos resultados para wt

0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6

Podemos intuir una especie de patrón, para verlo claro vamos a quitar las comas y cada vez que veamos un 1 empezaremos una nueva línea:

1
12  
1223  
12232334
1223233423343445
12232334233434452334344534454556

Vemos que el patrón es sencillo, tomamos todos los resultados donde el último 1 y los repetimos dos veces, al segundo grupo le sumamos uno.

1 => 1
1 (1+1) => 12
12 (1+1)(2+1) => 1223
1223 (1+1)(2+1)(2+1)(3+1) => 12232334

Si wt tiene ciclos significa que el número de celdas nuevas (u()) también lo tiene.da igual lo que haya crecido al estructura de celdas activas, habrá un punto en que solo haya 4 y siempre se repetirán los mismo números: 4,4,12,4,12,12,36,4,12,….

En la gráfica de número de celdas nuevas se puede ver esta repetición de subidas y caídas:

Este numero de repeticiones esta ligado con su estructura fractal.

El autómata celular Ulam-Warburton original usa la vecindad de von Neumann pero presenta un comportamiento similar usando la vecindad de Moore, si bien cambia el patrón: