Autómata Ulam-Warburton

Summarize Timeline Top Qs Fact Check

El UWCA es un autómata celular totalista externo 2D de 5 vecinos que usa la regla 686.^[4]

El número de celdas activadas en cada iteración se indica ${\displaystyle u(n),}$ con una fórmula explícita:

${\displaystyle u(0)=0,u(1)=1,}$ y para ${\displaystyle n\geq 2}$

${\displaystyle u(n)={\frac {4}{3}}\cdot 3^{wt(n-1)}}$

donde ${\displaystyle wt(n)}$ es la función de peso de Hamming que cuenta el número de unos en la expansión binaria de ${\displaystyle n}$^[5]

${\displaystyle wt(n)=n-\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{2^{k}}}\right\rfloor }$

El límite superior mínimo de suma para ${\displaystyle k}$ es tal que ${\displaystyle 2^{k}>n}$

Se indica el número total de celdas encendidas ${\displaystyle U(n)}$

${\displaystyle U(n)=\sum _{i\mathop {=} 0}^{n}u(i)={\frac {4}{3}}\sum _{i\mathop {=} 0}^{n-1}3^{wt(i)}-{\frac {1}{3}}}$

La tabla muestra que diferentes entradas para ${\displaystyle wt(n)}$ puede conducir a la misma salida.

Esta propiedad sobreyectiva surge de la regla simple de crecimiento: nace una nueva celda si comparte solo un borde con una celda ON existente; el proceso parece desordenado y está modelado por funciones que involucran ${\displaystyle wt(n)}$ but within the chaos there is regularity.

${\displaystyle n}$	${\displaystyle wt(n)}$	${\displaystyle u(n)}$	${\displaystyle U(n)}$	${\displaystyle n}$	${\displaystyle wt(n)}$	${\displaystyle u(n)}$	${\displaystyle U(n)}$
0	0	0	0	10	2	12	101
1	1	1	1	11	3	12	113
2	1	4	5	12	2	36	149
3	2	4	9	13	3	12	161
4	1	12	21	14	3	36	197
5	2	4	25	15	4	36	233
6	2	12	37	16	1	108	341
7	3	12	49	17	2	4	345
8	1	36	85	18	2	12	357
9	2	4	89	19	3	12	369

${\displaystyle U(n)}$ es la secuencia OEIS A147562 y ${\displaystyle u(n)}$ es la secuencia OEIS A147582

Para todas las secuencias enteras de la forma ${\displaystyle n_{m}=m\cdot 2^{k}}$ donde ${\displaystyle m\geq 1}$ y ${\displaystyle k\geq 0}$

Sea

${\displaystyle a_{m}=\sum _{i\mathop {=} 0}^{m-1}3^{wt(i)}}$

(${\displaystyle a_{m}}$ es la secuencia OEIS A130665)

Luego, el número total de celdas ON en la secuencia entera ${\displaystyle n_{m}}$ viene dado por^[6]

${\displaystyle U_{m}(n_{m})={\frac {a_{m}}{m^{2}}}{\frac {4}{3}}n_{m}^{2}-{\frac {1}{3}}}$

O en términos de ${\displaystyle k}$ tenemos

${\displaystyle U_{m}(k)=a_{m}{\frac {4}{3}}2^{2k}-{\frac {1}{3}}}$

${\displaystyle k}$	${\displaystyle n_{1}}$	${\displaystyle U_{1}}$	${\displaystyle n_{3}}$	${\displaystyle U_{3}}$	${\displaystyle n_{5}}$	${\displaystyle U_{5}}$	${\displaystyle n_{7}}$	${\displaystyle U_{7}}$
0	1	1	3	9	5	25	7	49
1	2	5	6	37	10	101	14	197
2	4	21	12	149	20	405	28	789
3	8	85	24	597	40	1,621	56	3,157
4	16	341	48	2,389	80	6,485	112	12,629
5	32	1,365	96	9,557	160	25,941	224	50,517

Summarize Timeline Fact Check

${\displaystyle U(n)}$ tiene un comportamiento similar al fractal con un límite superior agudo para ${\displaystyle n\geq 1}$ dado por

${\displaystyle U_{\text{sub}}(n)={\frac {4}{3}}n^{2}-{\frac {1}{3}}}$

El límite superior solo contacta ${\displaystyle U(n)}$ en los puntos de 'marea alta' cuando ${\displaystyle n=2^{k}}$.

Estas son también las generaciones en las que el UWCA basado en cuadrados, el Hex-UWCA basado en hexágonos y el triángulo de Sierpinski vuelven a su forma base.^[7]

Tenemos

${\displaystyle 0.9026116569...=\liminf _{n\to \infty }{\frac {U(n)}{n^{2}}}<\limsup _{n\to \infty }{\frac {U(n)}{n^{2}}}={\frac {4}{3}}}$

El límite inferior fue obtenido por Robert Price ( secuencia OEIS A261313) y tardó varias semanas en calcularse y se cree que es el doble del límite inferior de${\displaystyle {\frac {T(n)}{n^{2}}}}$ donde ${\displaystyle T(n)}$ es el número total de palillos en la secuencia de palillos hasta la generación ${\displaystyle n}$^[8]

Summarize Timeline Fact Check

El autómata celular Hexagonal-Ulam-Warburton (Hex-UWCA) es un patrón fractal bidimensional que crece en una cuadrícula regular de celdas que consta de hexágonos. Se aplica la misma regla de crecimiento para el UWCA y el patrón vuelve a ser un hexágono en generaciones ${\displaystyle n=2^{k}}$, cuando el primer hexágono se considera generación ${\displaystyle 1}$.

El UWCA tiene dos líneas de reflexión que pasan por las esquinas de la celda inicial que divide el cuadrado en cuatro cuadrantes, de manera similar, el Hex-UWCA tiene tres líneas de reflexión que dividen el hexágono en seis secciones y la regla de crecimiento sigue las simetrías. Las células cuyos centros se encuentran en una línea de simetría de reflexión nunca nacen.^[9]

La versión externa (Outward-UWCA) funciona de la misma manera que la normal, pero las celdas activables que van contra corriente de crecimiento no se activan.

${\displaystyle U(n)}$ es la secuencia OEIS A160720 y ${\displaystyle u(n)}$ es la secuencia OEIS A160721.

El resultado es similar al de UWCA pero con más espacios vacíos en el interior de la figura. Concretamente, tiene la particularidad de que la figura formada en cada uno de los cuadrantes forma una estructura similar al triángulo de Sierpinski.^[10]

El triángulo de Sierpinski aparece en los mosaicos de suelo italianos del siglo XIII. Wacław Sierpiński describió el triángulo en 1915.

Si consideramos el crecimiento del triángulo, con cada fila correspondiente a una generación y la generación de la fila superior ${\displaystyle 1}$ es un solo triángulo, luego, como el UWCA y el Hex-UWCA, vuelve a su forma inicial, en generaciones ${\displaystyle n=2^{k}.}$

El patrón de mondadientes se construye colocando un solo mondadientes de longitud unitaria en una cuadrícula, alineada con el eje vertical. En cada etapa posterior, por cada extremo expuesto de un palillo, se coloca un palillo perpendicular centrado en ese extremo. La estructura resultante tiene una apariencia de fractal.

El palillo de dientes y las estructuras UWCA son ejemplos de autómatas celulares definidos en un grafo y cuando se consideran como un subgrafo de la cuadrícula de cuadrados infinitos, la estructura es un árbol.

La secuencia de mondadientes vuelve a su base en forma de 'H' rotada en generaciones ${\displaystyle n=2^{k}}$ donde ${\displaystyle k\geq 1}$^[9]

Un juego de resta llamado LIM, en el que dos jugadores modifican alternativamente tres pilas de fichas tomando una cantidad igual de fichas de dos de las pilas y sumando la misma cantidad a la tercera pila, tiene un conjunto de posiciones ganadoras que se pueden describir usando el autómata de Ulam-Warburton.^[11][10]