# 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. 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 i l'enginyer Mike Warburton.

## 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$.
$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)$
$u(n)$
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}$
$wt(n)$
Llavors el nombre total de cel·les actives en la seqüència d'enters $n_{m}$ és donada per:
    $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.

### 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}}$
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.

## Variants
### 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)$
$u(n)$
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.

## Vegeu també

* Autòmat cel·lular
* Seqüència d'escuradents

## 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
* 1 2 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