Ulam – Warburtonův automat - Ulam–Warburton automaton

The Ulam – Warburton buněčný automat (UWCA) je 2-dimenzionální fraktální vzor, ​​který roste na a pravidelná mřížka buněk sestávajících ze čtverců. Počínaje jedním čtvercem zpočátku zapnutým a všemi ostatními vypnutými, postupné iterace jsou generovány zapnutím všech čtverců, které sdílejí přesně jednu hranu se zapnutým čtvercem. To je sousedství von Neumann. Automat je pojmenován podle polsko-amerického matematika a vědce Stanislaw Ulam^[1] a skotský inženýr, vynálezce a amatérský matematik Mike Warburton.^[2][3]

Prvních dvacet iterací Ulam-Warburton buněčný automat

Vlastnosti a vztahy

UWCA je 2D 5-sousední vnější totalitní celulární automat využívající pravidlo 686.^[4]

Je označen počet buněk zapnutých v každé iteraci ${ displaystyle u (n),}$ s výslovným vzorcem:

${ displaystyle u (0) = 0, u (1) = 1,}$ a pro ${ displaystyle n geq 2}$

${ displaystyle u (n) = { frac {4} {3}} cdot 3 ^ {wt (n-1)}}$

kde ${ displaystyle wt (n)}$ je Hammingova hmotnost funkce, která počítá počet 1 v binární expanzi ${ displaystyle n}$^[5]

${ displaystyle wt (n) = n- součet _ {k = 1} ^ { infty} levý lfloor { frac {n} {2 ^ {k}}} pravý rfloor}$

Minimální horní hranice součtu pro ${ displaystyle k}$ je takový ${ displaystyle 2 ^ {k}> n}$

Celkový počet zapnutých buněk je označen ${ displaystyle U (n)}$

${ displaystyle U (n) = součet _ {i mathop {=} 0} ^ {n} u (i) = { frac {4} {3}} součet _ {i mathop {=} 0 } ^ {n-1} 3 ^ {wt (i)} - { frac {1} {3}}}$

Tabulka ${ displaystyle wt (n)}$, ${ displaystyle u (n)}$ a ${ displaystyle U (n)}$

Tabulka ukazuje, že různé vstupy do ${ displaystyle wt (n)}$ může vést ke stejnému výstupu.

Tento surjektivní vlastnost vychází z jednoduchého pravidla růstu - nová buňka se zrodí, pokud sdílí pouze jednu hranu s existující ON buňkou - proces vypadá neuspořádaně a je modelován funkcemi zahrnujícími ${ displaystyle wt (n)}$ ale v chaosu je pravidelnost.

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

${ displaystyle U (n)}$ je OEIS sekvence A147562 a ${ displaystyle u (n)}$ je OEIS sekvence A147582

Počítání buněk kvadratickými

Celkový počet zapnutých buněk ${ displaystyle U (n)}$ v Ulam – Warburton CA a kvadratičtí ${ displaystyle U_ {1}, U_ {3}}$ a ${ displaystyle U_ {17}}$

Pro všechny celočíselné sekvence formuláře ${ displaystyle n_ {m} = m cdot 2 ^ {k}}$ kde ${ displaystyle m geq 1}$ a ${ displaystyle k geq 0}$

Nechat

${ displaystyle a_ {m} = součet _ {i mathop {=} 0} ^ {m-1} 3 ^ {wt (i)}}$

(${ displaystyle a_ {m}}$ je OEIS sekvence A130665 )

Poté celkový počet ON buněk v celočíselné sekvenci ${ displaystyle n_ {m}}$ darováno^[6]

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

Nebo z hlediska ${ displaystyle k}$ my máme

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

Tabulka celočíselných sekvencí ${ displaystyle n_ {m}}$ a ${ displaystyle U_ {m}}$

${ displaystyle k}$	${ displaystyle n_ {1}}$	${ displaystyle U_ {1}}$	${ displaystyle n_ {3}}$	${ displaystyle U_ {3}}$	${ displaystyle n_ {5}}$	${ displaystyle U_ {5}}$	${ displaystyle n_ {7}}$	${ displaystyle 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	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

Horní a dolní mez

Celkový počet ON buněk v Ulam – Warburton buněčný automat

${ displaystyle U (n)}$ má fraktální -jako chování s a ostrá horní mez pro ${ displaystyle n geq 1}$ dána

${ displaystyle U _ { text {sub}} (n) = { frac {4} {3}} n ^ {2} - { frac {1} {3}}}$

Horní hranice pouze kontakty ${ displaystyle U (n)}$ v bodech „vysoké vody“, když ${ displaystyle n = 2 ^ {k}}$.

To jsou také generace, ve kterých UWCA založené na čtvercích, Hex – UWCA založené na šestiúhelnících a Sierpinského trojúhelník vrátit se do základního tvaru.^[7]

Horní a dolní mez ${ displaystyle U (n) / n ^ {2}}$

Limit superior a limit inferior

My máme

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

Spodní limit získal Robert Price (OEIS sekvence A261313 ) a výpočet trvalo několik týdnů a předpokládá se, že je dvojnásobkem dolní hranice ${ displaystyle { frac {T (n)} {n ^ {2}}}}$ kde ${ displaystyle T (n)}$ je celkový počet párátků v sekvence párátka až do generace ${ displaystyle n}$^[8]

Vztah k

Hex-Ulam-Warburton buněčný automat - generace 11

Šestihranný UWCA

Hexagonal-Ulam – Warburton buněčný automat (Hex-UWCA) je 2-dimenzionální fraktální vzor, ​​který roste na a pravidelná mřížka buněk sestávajících z šestiúhelníků. Platí stejné pravidlo růstu pro UWCA a vzor se vrací do šestiúhelníku po generace ${ displaystyle n = 2 ^ {k}}$, když je první šestiúhelník považován za generaci ${ displaystyle 1}$UWCA má dvě reflexní čáry, které procházejí rohy počáteční buňky rozdělující čtverec na čtyři kvadranty, podobně má Hex-UWCA tři reflexní čáry rozdělující šestiúhelník na šest částí a pravidlo růstu sleduje symetrie. Buňky, jejichž střed leží na linii reflexní symetrie, se nikdy nenarodí.

Vzor Hex-UWCA lze prozkoumat tady.

Sierpinského trojúhelník

Sierpinského trojúhelník - generace 16

Sierpinského trojúhelník se objevuje v italských podlahových mozaikách ze 13. století. Wacław Sierpiński popsal trojúhelník v roce 1915.

Pokud vezmeme v úvahu růst trojúhelníku, přičemž každý řádek odpovídá generaci a generaci horního řádku ${ displaystyle 1}$ je jediný trojúhelník, poté se jako UWCA a Hex-UWCA vrací do své výchozí podoby, v generacích ${ displaystyle n = 2 ^ {k}.}$

Sekvence párátka

Sekvence párátka - generace 13

Vzor párátka je vytvořen umístěním jediného párátka o jednotkové délce na čtvercovou mřížku, zarovnanou se svislou osou. V každé další fázi umístěte na každý odkrytý konec párátka kolmé párátko se středem na tomto konci. Výsledná struktura má fraktální vzhled.

Párátko a struktury UWCA jsou příklady celulárních automatů definovaných v a graf a když je považován za podgraf nekonečné čtvercové mřížky, struktura je a strom.

Sekvence párátka se po generace vrací do svého základního rotovaného tvaru „H“ ${ displaystyle n = 2 ^ {k}}$ kde ${ displaystyle k geq 1}$

The sekvence párátka a lze prozkoumat různé sekvence podobné párátku tady.

Kombinatorická teorie her

A odečítací hra s názvem LIM, ve kterém dva hráči střídavě upravují tři hromádky žetonů tím, že vezmou stejné množství žetonů ze dvou hromádek a přidají stejnou částku na třetí hromádku, má sadu výherních pozic, které lze popsat pomocí Ulam – Warburton automat.^[9][10]

Dějiny

Počátky automatů sahají do rozhovoru, který Ulam vedl se Stanislawem Mazurem v kavárně v polském Lvově, když bylo Ulamovi v roce 1929 dvacet.^[11] Ulam pracoval s John von Neumann během válečných let, kdy se stali dobrými přáteli a diskutovali o celulárním automatu. Von Neumann použil tyto myšlenky ve své koncepci univerzálního konstruktoru a digitálního počítače. Ulam se zaměřil na biologické a „krystalové“ vzory a publikoval náčrt růstu čtvercové buněčné struktury pomocí jednoduchého pravidla v roce 1962. Mike Warburton je amatérský matematik pracující v pravděpodobnostní teorii čísel, který získal vzdělání na Škola George Heriota v Edinburghu. Matematika jeho syna Maturita Kurz zahrnoval zkoumání růstu rovnostranných trojúhelníků nebo čtverců v euklidovské rovině s pravidlem - nová generace se rodí právě tehdy, je-li spojena s poslední pouze jednou hranou. Tato práce byla zakončena rekurzivním vzorcem pro počet ON buněk narozených v každé generaci. Později Warburton našel ostrý vzorec horní hranice, který napsal jako poznámku v časopise M500 Open University v roce 2002. David Singmaster si přečetl článek, analyzoval strukturu a ve svém článku z roku 2003 objekt pojmenoval Ulam-Warburtonův buněčný automat. Od té doby vzniklo mnoho celočíselných sekvencí.

Reference

externí odkazy

• Prozkoumejte UWCA, Hex-UWCA a související celočíselné sekvence animace
• Neil Sloane: Skvělé vzory párátka - Numberphile. (UWCA začíná v čase 8:20)