Autòmat d'Ulam–Warburton

Primeres iteracions de la seqüència *UWCA*.

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]

Propietats

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

$u(n)={\begin{cases}n,&{\text{si }}n<2\\{\frac {4}{3}}\cdot 3^{wt(n-1)},&{\text{si }}n\geq 2\end{cases}}$

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

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

El mínim límit superior de sumació per $k$ és aquell al qual $2^{k}>n$ .

El nombre total de cel·les activades $U(n)$ segueix la fórmula següent:

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

U(n)

és la seqüència OEIS A147562 i

u(n)

és la seqüència OEIS A147582

La següent taula de $wt(n)$ , $u(n)$ i $U(n)$ mostra que diferents entrades de $wt(n)$ 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.

$n$	$wt(n)$	$u(n)$	$U(n)$	$n$	$wt(n)$	$u(n)$	$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

Per totes les seqüències d'enters de la forma $n_{m}=m\cdot 2^{k}$ on $m\geq 1$ i $k\geq 0$ es pot definir la fórmula:

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

a_{m}

és la seqüència OEIS A130665, on

wt(n)

correspon a l'OEIS A000120

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

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

O en termes de $k$ tenim que

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

A partir d'aquí s'obté la següent taula de seqüències d'enters $n_{m}$ i $U_{m}$ .

$k$	$n_{1}$	$U_{1}$	$n_{3}$	$U_{3}$	$n_{5}$	$U_{5}$	$n_{7}$	$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	1621	56	3157
4	16	341	48	2389	80	6485	112	12629
5	32	1365	96	9557	160	25941	224	50517

Fites superiors i inferiors

$U(n)$ té un comportament fractal amb una fita superior robusta per valors de $n\geq 1$ donada per

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

La fita superior arriba a $U(n)$ quan $n=2^{k}$ . 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 inferior

Tenim que:

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

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 ${\frac {T(n)}{n^{2}}}$ on $T(n)$ és el nombre d'escuradents total en la generació $n$ de la seqüència d'escuradents.^[7]

Variants

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

UWCA hexagonal

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 $n=2^{k}$ .

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ó externa

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.

U(n)

és la seqüència OEIS A160720 i

u(n)

é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é

Referències

↑ David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 Arxivat 2022-07-06 a Wayback Machine. (2003), 2–7
↑ Stanislaw Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in BiologicalSciences, 14 (1962), 215–224.
↑ M. Warburton, One-edge connections, M500 Magazine of The Open University, 188 Arxivat 2021-10-21 a Wayback Machine. (2002), 11
↑ 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.
↑ Mike Warburton, "Ulam-Warburton Automaton - Counting Cells with Quadratics ", arXiv:1901.10565
↑ ^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.
↑ Steven R. Finch, Mathematical Constants II, 364-365

Enllaços externs

OEIS A1319250 Animations - Versions animades de UMCA, Hex-UMCA, Outward-UWCA i altres seqüències relacionades

[1] David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 Arxivat 2022-07-06 a Wayback Machine. (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 Arxivat 2021-10-21 a Wayback Machine. (2002), 11

[Applegate-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

[sierpinski-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]