Autómata Ulam-Warburton

El autómata celular de Ulam-Warburton (UWCA) es un patrón fractal bidimensional que crece en una cuadrícula regular de celdas que consisten en cuadrados. Comenzando con un cuadrado inicialmente ENCENDIDO y todos los demás APAGADOS, se generan iteraciones sucesivas ENCENDIENDO todos los cuadrados que comparten precisamente un borde con un cuadrado ENCENDIDO. Este es el vecindario de von Neumann . El autómata recibe su nombre del matemático y científico polaco-estadounidense Stanislaw Ulam ^[1] y del ingeniero, inventor y matemático aficionado escocés Mike Warburton. ^{[2] [3]}

Las primeras veinte iteraciones del autómata celular Ulam-Warburton

Propiedades y relaciones

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

La cantidad de celdas activadas en cada iteración se denota con una fórmula explícita: ${\displaystyle u(n),}$

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

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

¿Dónde está la función de peso de Hamming que cuenta el número de 1 en la expansión binaria de ^[5]? ${\displaystyle wt(n)}$ ${\displaystyle n}$

${\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 es tal que ${\displaystyle k}$ ${\displaystyle 2^{k}\geq n}$

Se denota el número total de celdas activadas ${\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}}}$

Tabla depeso(n),Naciones Unidas)yNaciones Unidas)

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

Esta propiedad sobreyectiva surge de la simple regla de crecimiento: una nueva célula nace si comparte sólo un borde con una célula ON existente; el proceso parece desordenado y está modelado por funciones que lo involucran, pero dentro del caos hay regularidad. ${\displaystyle wt(n)}$

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

Contar células con ecuaciones cuadráticas

Número total de células ON en la CA de Ulam–Warburton y cuadráticas y ${\displaystyle U(n)}$ ${\displaystyle U_{1},U_{3}}$ ${\displaystyle U_{17}}$

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

Dejar

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

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

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

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

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

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

Tabla de sucesiones de números enterosnuevo​yYo soy

Límites superior e inferior

Número total de células ON en el autómata celular Ulam-Warburton

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

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

El límite superior sólo entra en contacto en los puntos de 'aguas altas' cuando . ${\displaystyle U(n)}$ ${\displaystyle n=2^{k}}$

Éstas 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]

Límites superior e inferior de ${\displaystyle U(n)/n^{2}}$

Límite superior y límite inferior

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 donde es el número total de palillos en la secuencia de palillos hasta la generación ^[8]. ${\displaystyle {\frac {T(n)}{n^{2}}}}$ ${\displaystyle T(n)}$ ${\displaystyle n}$

Relación con

Autómata celular Hex-Ulam-Warburton - generación 11

UWCA hexagonal

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 consisten en hexágonos. La misma regla de crecimiento para el UWCA se aplica y el patrón vuelve a ser un hexágono en generaciones , cuando el primer hexágono se considera como generación . El UWCA tiene dos líneas de reflexión que pasan por las esquinas de la celda inicial dividiendo 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. ${\displaystyle n=2^{k}}$ ${\displaystyle 1}$

El patrón Hex-UWCA se puede explorar aquí.

Triángulo de Sierpinski

Triángulo de Sierpinski : generación 16

El triángulo de Sierpinski aparece en mosaicos de suelo italianos del siglo XIII. Wacław Sierpinski lo describió 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 es un solo triángulo, entonces, al igual que el UWCA y el Hex-UWCA, vuelve a su forma inicial, en generaciones. ${\displaystyle 1}$ ${\displaystyle n=2^{k}.}$

Secuencia del palillo de dientes

Secuencia del palillo de dientes - Generación 13

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

Las estructuras de palillo de dientes y UWCA son ejemplos de autómatas celulares definidos en un gráfico y cuando se consideran como un subgráfico de la cuadrícula cuadrada infinita, la estructura es un árbol .

La secuencia del palillo vuelve a su forma básica de 'H' rotada en las generaciones donde ${\displaystyle n=2^{k}}$ ${\displaystyle k\geq 1}$

Aquí se pueden explorar la secuencia del palillo y varias secuencias similares a palillos.

Teoría de juegos combinatorios

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 añadiendo la misma cantidad a la tercera pila, tiene un conjunto de posiciones ganadoras que pueden describirse utilizando el autómata Ulam-Warburton. ^{[9] [10]}

Historia

Los orígenes de los autómatas se remontan a una conversación que Ulam tuvo con Stanislaw Mazur en una cafetería de Lwów, Polonia, cuando tenía veinte años en 1929. ^[11] Ulam trabajó con John von Neumann durante los años de la guerra, cuando se hicieron buenos amigos y hablaron sobre los autómatas celulares. Von Neumann utilizó estas ideas en su concepto de un constructor universal y la computadora digital. Ulam se centró en patrones biológicos y "similares a cristales" y publicó un boceto del crecimiento de una estructura celular basada en cuadrados utilizando una regla simple en 1962. Mike Warburton es un matemático aficionado que trabaja en teoría de números probabilísticos y que se educó en la Escuela George Heriot de Edimburgo. El trabajo de curso de matemáticas de GCSE de su hijo implicaba investigar el crecimiento de triángulos equiláteros o cuadrados en el plano euclidiano con la regla: una nueva generación nace si y solo si está conectada a la anterior por un solo borde. Ese trabajo de curso concluyó con una fórmula recursiva para el número de células ON nacidas en cada generación. Más tarde, Warburton encontró la fórmula del límite superior, que escribió como nota en la revista M500 de la Open University en 2002. David Singmaster leyó el artículo, analizó la estructura y denominó al objeto autómata celular de Ulam-Warburton en su artículo de 2003. Desde entonces, ha dado lugar a numerosas secuencias de números enteros.

Referencias

1. SM Ulam , Sobre algunos problemas matemáticos relacionados con patrones de crecimiento de figuras, Problemas matemáticos en ciencias biológicas, 14 (1962), 215–224.
2. M. Warburton, Conexiones de un solo borde, Revista M500 de The Open University, 188 (2002), 11
3. D. Singmaster , Sobre el autómata celular de Ulam y Warburton, M500 Magazine de The Open University, 195 (2003), 2–7
4. OEIS - Índice de autómatas celulares 2D de 5 vecinos,[1],
5. Applegate , David; Pol, Omar E.; Sloane , NJA (2010). "La secuencia del palillo y otras secuencias de autómatas celulares". Congressus Numerant . 206 : 157–191. arXiv : 1004.3036 .
6. Mike Warburton, "Autómata Ulam-Warburton: conteo de células con ecuaciones cuadráticas", arXiv :1901.10565
7. Tanya Khovanova, Eric Nie, Alok Puranik, "El triángulo de Sierpinski y el autómata Ulam-Warburton", arXiv :1408.5937
8. Steven R. Finch, Constantes matemáticas II, 364-365
9. Fink, Alex; Fraenkel, Aviezri S.; Santos, Carlos (mayo de 2013), "LIM no es delgado", International Journal of Game Theory , 43 (2): 269–281, doi :10.1007/s00182-013-0380-z
10. Khovanova, Tanya ; Xiong, Joshua (2014), "Fractales de Nim", Journal of Integer Sequences , 17 (7): Artículo 14.7.8, 17, arXiv : 1405.5942 , MR  3238125
11. SM Ulam, Aventuras de un matemático, pág. 32

Enlaces externos

• Explora las animaciones de secuencias enteras relacionadas con UWCA, Hex-UWCA
• Neil Sloane: Patrones fantásticos con palillos de dientes - Numberphile. (La UWCA comienza en el minuto 8:20)