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 y todos los demás APAGADOS, se generan iteraciones sucesivas activando todos los cuadrados que comparten precisamente un borde con un cuadrado ENCENDIDO. Este es el barrio 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]
Propiedades y relaciones
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
dónde 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
Mesa de , y
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 pero dentro del caos hay regularidad.
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 | dieciséis | 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 yes la secuencia OEIS A147582
Contando celdas con cuadráticas
Para todas las secuencias enteras de la forma dónde y
Dejar
(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
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 | dieciséis | 341 | 48 | 2,389 | 80 | 6.485 | 112 | 12,629 |
5 | 32 | 1365 | 96 | 9.557 | 160 | 25,941 | 224 | 50,517 |
Límites superior e inferior
tiene un comportamiento similar al fractal con un límite superior agudo para dada 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ímite superior y límite inferior
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 dónde es el número total de palillos en la secuencia de palillos hasta la generación[8]
Relación con
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 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.
El patrón Hex-UWCA se puede explorar aquí .
Triángulo de Sierpinski
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 dientes
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, coloque 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 gráfico y cuando se consideran como un subgráfico de la cuadrícula infinita, la estructura es un árbol .
La secuencia de mondadientes vuelve a su base en forma de 'H' rotada en generaciones dónde
La secuencia de palillo de dientes y diversas secuencias de palillo de dientes-como pueden ser explorados aquí .
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 agregando la misma cantidad a la tercera pila, tiene un conjunto de posiciones ganadoras que se pueden describir usando el Autómata de Ulam-Warburton. [9] [10]
Historia
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. [11] 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 los patrones biológicos y 'cristalinos' 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 en Edimburgo. El trabajo del curso de matemáticas GCSE de su hijo involucró 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 solo un 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.
Referencias
- ^ 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.
- ↑ M. Warburton, One-edge connections, M500 Magazine of The Open University , 188 (2002), 11
- ^ D. Singmaster , Sobre el autómata celular de Ulam y Warburton, Revista M500 de The Open University , 195 (2003), 2-7
- ^ OEIS - Índice de autómatas celulares 2D de 5 vecinos, [1] ,
- ^ Applegate , David; Pol, Omar E .; Sloane , NJA (2010). "La secuencia del palillo de dientes y otras secuencias de autómatas celulares". Congressus Numerant . 206 : 157-191. arXiv : 1004.3036 .
- ^ Mike Warburton, "Autómata de Ulam-Warburton: recuento de celdas con cuadráticas", arXiv : 1901.10565
- ^ Tanya Khovanova, Eric Nie, Alok Puranik, "El triángulo de Sierpinski y el autómata de Ulam-Warburton", arXiv : 1408.5937
- ^ Steven R. Finch, Constantes matemáticas II, 364-365
- ^ 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
- ^ Khovanova, Tanya ; Xiong, Joshua (2014), "Nim fractals", Journal of Integer Sequences , 17 (7): Artículo 14.7.8, 17, arXiv : 1405.5942 , MR 3238125
- ^ SM Ulam, Aventuras de un matemático, p32
enlaces externos
- Explore las animaciones de secuencia de enteros UWCA, Hex-UWCA y relacionadas
- Neil Sloane: Patrones de palillo de dientes fabulosos - Numberphile. (El UWCA comienza a las 8:20)