Autómata Ulam-Warburton

El autómata celular Ulam-Warburton (UWCA) es un patrón fractal bidimensional que crece en una cuadrícula regular de celdas que consta de cuadrados. Comenzando con un cuadrado inicialmente encendido (ON) y todos los demás apagados (OFF), se generan iteraciones sucesivas activando todos los cuadrados que comparten precisamente un borde con un cuadrado encendido. Esta es la vecindad de von Neumann. El autómata lleva el 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]

Primeras iteraciones de la secuencia UWCA.
Las primeras veinte iteraciones del autómata celular Ulam-Warburton

Propiedades y relacionesEditar

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   con una fórmula explícita:

  y para  

 

donde   es la función de peso de Hamming que cuenta el número de unos en la expansión binaria de  [5]

 

El límite superior mínimo de suma para   es tal que  

Se indica el número total de celdas encendidas  

 

Tabla de  ,   y  Editar

La tabla muestra que diferentes entradas para   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   but within the chaos there is regularity.

               
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

  es la secuencia OEIS A147562 y   es la secuencia OEIS A147582

Contar celdas con cuadráticasEditar

 
Número total de celdas ON   en el autómata celular Ulam–Warburton y cuadráticas   y  

Para todas las secuencias enteras de la forma   donde   y  

Sea

 

(  es la secuencia OEIS A130665)

Luego, el número total de celdas ON en la secuencia entera   viene dado por[6]

 

O en términos de   tenemos

 

Tabla de secuencias de enteros   y  Editar

                 
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

Límites superior e inferiorEditar

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

  tiene un comportamiento similar al fractal con un límite superior agudo para   dado por

 

El límite superior solo contacta   en los puntos de 'marea alta' cuando  .

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]

 
Límites superior e inferior de  

Límite superior y límite inferiorEditar

Tenemos

 

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]

Fractales relacionadosEditar

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

Hex-UWCAEditar

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  , cuando el primer hexágono se considera generación  .

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]

Versión externaEditar

 
Primeras iteraciones de la secuencia Outward-UWCA, versión con cuadrante único. La estructura que se forma es el triángulo de Sierpinski.

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.

  es la secuencia OEIS A160720 y   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]

Triángulo de SierpinskiEditar

 
Triángulo de Sierpinski - generación 16

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   es un solo triángulo, luego, como el UWCA y el Hex-UWCA, vuelve a su forma inicial, en generaciones  

Secuencia de palillos de dientesEditar

 
Secuencia de palillos de dientes - generación 13

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   donde  [9]

Teoría de juegos combinatoriosEditar

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]

HistoriaEditar

Los inicios de los autómatas se remontan a una conversación que Ulam tuvo con Stanislaw Mazur en una cafetería en Lwów, Polonia, cuando Ulam tenía veinte años en 1929.[12]​ Ulam trabajó con John von Neumann durante los años de guerra cuando se hicieron buenos amigos y discutieron sobre 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 de tipo cristal y publicó un bosquejo del crecimiento de una estructura celular basada en cuadrados usando una regla simple en 1962. Mike Warburton es un matemático aficionado que trabaja en teoría probabilística de números y se educó en la Escuela George Heriot de Edimburgo. El trabajo de curso GCSE de matemáticas de su hijo consistió en investigar el crecimiento de triángulos o cuadrados equiláteros en el plano euclidiano con la regla: nace una nueva generación si y solo si está conectada a la última por un solo borde. Ese 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 nítido que escribió como una nota en la revista M500 de la Open University en 2002. David Singmaster leyó el artículo, analizó la estructura y nombró al objeto el autómata celular Ulam-Warburton en su artículo de 2003. Desde entonces ha dado lugar a numerosas secuencias enteras.

ReferenciasEditar

  1. S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in BiologicalSciences, 14 (1962), 215–224.
  2. M. Warburton, One-edge connections, M500 Magazine of The Open University, 188 (2002), 11
  3. D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 (2003), 2–7
  4. OEIS - Index to 2D 5-Neighbor Cellular Automata,[1],
  5. Applegate, David; Pol, Omar E.; Sloane, N. J. A. (3 de octubre de 2010). «The Toothpick Sequence and Other Sequences from Cellular Automata». arXiv:1004.3036 [math]. Consultado el 11 de marzo de 2021. 
  6. Mike Warburton, "Ulam-Warburton Automaton - Counting Cells with Quadratics ", arXiv:1901.10565
  7. Khovanova, Tanya; Nie, Eric; Puranik, Alok (25 de agosto de 2014). «The Sierpinski Triangle and The Ulam-Warburton Automaton». arXiv:1408.5937 [math]. Consultado el 11 de marzo de 2021. 
  8. Steven R. Finch, Mathematical Constants II, 364-365
  9. a b «toothpick-like sequence exploration». oeis.org. Consultado el 11 de marzo de 2021. 
  10. a b Khovanova, Tanya; Xiong, Joshua (22 de mayo de 2014). «Nim Fractals». arXiv:1405.5942 [math]. Consultado el 11 de marzo de 2021. 
  11. Fink, Alex; Fraenkel, Aviezri S.; Santos, Carlos (1 de mayo de 2014). «LIM is not slim». International Journal of Game Theory (en inglés) 43 (2): 269-281. ISSN 1432-1270. doi:10.1007/s00182-013-0380-z. Consultado el 11 de marzo de 2021. 
  12. S. M. Ulam, Adventures of a Mathematician, p32

Enlaces externosEditar