Autòmat d'Ulam–Warburton

L'autòmat cel·lular d'Ulam–Warburton (UWCA), o simplement Autòmat d'Ulam–Warburton, és un patró fractal bidimensional que creix en una graella regular rectangular. El patró s'inicia amb una única cel·la activada, i a cada nova iteració s'activen les cel·les inactivades en què només un dels costats és adjacent ortogonalment a una d'activada, el que es coneix com a veïnatge de Von Neumann.[1] A diferència d'altres autòmats cel·lulars, l'activació de les cel·les és permanent, és a dir que no hi ha cap condició per la qual una cel·la activada s'inactivi. L'autòmat rep el nom en honor del matemàtic i científic Stanislaw Ulam[2] i l'enginyer Mike Warburton.[3]

Primeres iteracions de la seqüència UWCA.

PropietatsModifica

Per a cada iteració  , el nombre de cel·les que s'activen   segueix la següent fórmula:

 

on   és el pes de Hamming, el qual compta el nombre de 1 en l'expansió binària de  .[4]

 

El mínim límit superior de sumació per   és aquell al qual  .

El nombre total de cel·les activades   segueix la fórmula següent:

 

  és la seqüència OEIS A147562 i   és la seqüència OEIS A147582

La següent taula de  ,   i   mostra que diferents entrades de   poden conduir al mateix resultat. Aquesta propietat exhaustiva sorgeix de la norma simple de creixement de l'autòmat: una cel·la s'activa si comparteix alguna veïna activa, independentment de quines i quantes.

               
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

Per totes les seqüències d'enters de la forma   on   i   es pot definir la fórmula:

 
  és la seqüència OEIS A130665, on   correspon a l'OEIS A000120

Llavors el nombre total de cel·les actives en la seqüència d'enters   és donada per:[5]

 

O en termes de   tenim que

 

A partir d'aquí s'obté la següent taula de seqüències d'enters   i  .

                 
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 1621 56 3157
4 16 341 48 2389 80 6485 112 12629
5 32 1365 96 9557 160 25941 224 50517

Fites superiors i inferiorsModifica

 
Nombre total de cel·les activades en UWCA.
 
Fites superiors i inferiors de  

  té un comportament fractal amb una fita superior robusta per valors de   donada per

 

La fita superior arriba a   quan  . Això correspon a les generacions on les cel·les actives retornen a la seva forma base, en aquell cas és quan cobreixen una major extensió del pla.[6]

Límit superior i límit inferiorModifica

Tenim que:

 
La seqüència dels dígits coneguts del límit inferior es troba a l'OEIS A261313

El límit inferior va ser calculat per Robert Price l'any 2015, i es creu que és el doble del límit inferior de   on   és el nombre d'escuradents total en la generació   de la seqüència d'escuradents.[7]

VariantsModifica

 
Primeres iteracions de la seqüència Outward-UWCA, versió amb quadrant únic. L'estructura que es forma és el triangle de Sierpinski.

UWCA hexagonalModifica

L'autòmat hexagonal d'Ulam–Warburton (Hex-UWCA) és un patró fractal bidimensional que creix en una graella regular de cel·les hexagonals. S'hi aplica la mateixa norma de creixement que a UWCA, i el patró obtingut és un hexàgon en les generacions  .

UWCA té dues línies de reflexió que passen a través de les cantonades de la cel·la inicial, dividint el quadrat en quatre quadrants. De manera similar, Hex-UWCA té tres línies de reflexió que divideixen l'hexàgon en sis seccions, i la norma de creixement és simètrica en cadascuna d'elles. Les cel·les les quals el centre cau exactament a la línia de reflexió no s'activen mai.

Versió externaModifica

La versió externa (Outward-UWCA) funciona de la mateixa manera que la normal, però les cel·les activables que van contra corrent de creixement no s'activen.

  és la seqüència OEIS A160720 i   és la seqüència OEIS A160721

El resultat és similar al de UWCA però amb més espais buits en l'interior de la figura. Concretament, té la particularitat de que la figura formada en cadascun dels quadrants forma una estructura similar al triangle de Sierpinski.[6]

Vegeu tambéModifica

ReferènciesModifica

  1. David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 (2003), 2–7
  2. Stanislaw Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in BiologicalSciences, 14 (1962), 215–224.
  3. M. Warburton, One-edge connections, M500 Magazine of The Open University, 188 (2002), 11
  4. Applegate, David; Pol, Omar E.; Sloane, N. J. A. (2010). «The toothpick sequence and other sequences from cellular automata». Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium. 206. pp. 157–191. arXiv: 1004.3036. Bibcode: 2010arXiv1004.3036A. MR: 2762248.
  5. Mike Warburton, "Ulam-Warburton Automaton - Counting Cells with Quadratics ", arXiv:1901.10565
  6. 6,0 6,1 Khovanova, Tanya; Nie, Eric; Puranik, Alok «The Sierpinski Triangle and the Ulam-Warbuton Automaton». Math Horizons, 23, 1, 2014, pàg. 5-9. arXiv: 1408.5937.
  7. Steven R. Finch, Mathematical Constants II, 364-365

Enllaços externsModifica