Ulam-Warburton otomat - Ulam–Warburton automaton

Ulam-Warburton hücresel otomat (UWCA) 2 boyutlu bir fraktal üzerinde büyüyen desen normal ızgara karelerden oluşan hücreler. Başlangıçta bir kare ile başlayıp diğerlerinin tümü KAPALI ile başlayarak, ardışık yinelemeler, tam olarak bir kenarı paylaşan tüm kareler AÇIK kare ile AÇIK konuma getirilerek oluşturulur. Bu von Neumann mahallesi. Otomat, Polonyalı-Amerikalı matematikçi ve bilim adamının adını almıştır. Stanislaw Ulam^[1] ve İskoç mühendis, mucit ve amatör matematikçi Mike Warburton.^[2][3]

Ulam-Warburton'un ilk yirmi yinelemesi hücresel otomat

Özellikler ve ilişkiler

UWCA, kural 686'yı kullanan bir 2D 5-komşulu dış totalistik hücresel otomattır.^[4]

Her yinelemede AÇIK hale gelen hücre sayısı belirtilir ${ displaystyle u (n),}$ açık bir formülle:

${ displaystyle u (0) = 0, u (1) = 1,}$ ve için ${ displaystyle n geq 2}$

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

nerede ${ displaystyle wt (n)}$ ... Hamming ağırlığı ikili açılımında 1'lerin sayısını sayan fonksiyon ${ displaystyle n}$^[5]

${ displaystyle wt (n) = n- toplamı _ {k = 1} ^ { infty} sol lfloor { frac {n} {2 ^ {k}}} sağ rfloor}$

İçin minimum üst toplama sınırı ${ displaystyle k}$ şekildedir ${ displaystyle 2 ^ {k}> n}$

AÇIK hale getirilen toplam hücre sayısı gösterilir ${ displaystyle U (n)}$

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

Masası ${ displaystyle wt (n)}$, ${ displaystyle u (n)}$ ve ${ displaystyle U (n)}$

Tablo, farklı girdilerin ${ displaystyle wt (n)}$ aynı çıktıya yol açabilir.

Bu örten mülkiyet basit büyüme kuralından doğar - yeni bir hücre, mevcut bir ON hücresiyle yalnızca bir kenarı paylaşırsa doğar - süreç düzensiz görünür ve aşağıdakileri içeren işlevlerle modellenir ${ displaystyle wt (n)}$ ama kaosun içinde düzen vardır.

${ 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)}$ dır-dir OEIS sıra A147562 ve ${ displaystyle u (n)}$ dır-dir OEIS sıra A147582

Kuadratik ile hücreleri sayma

Toplam ON hücre sayısı ${ displaystyle U (n)}$ Ulam – Warburton CA ve ikinci dereceden ${ displaystyle U_ {1}, U_ {3}}$ ve ${ displaystyle U_ {17}}$

Formun tüm tamsayı dizileri için ${ displaystyle n_ {m} = m cdot 2 ^ {k}}$ nerede ${ displaystyle m geq 1}$ ve ${ displaystyle k geq 0}$

İzin Vermek

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

(${ displaystyle a_ {m}}$ dır-dir OEIS sıra A130665 )

Ardından tamsayı dizisindeki toplam ON hücre sayısı ${ displaystyle n_ {m}}$ tarafından verilir^[6]

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

Veya açısından ${ displaystyle k}$ sahibiz

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

Tamsayı dizileri tablosu ${ displaystyle n_ {m}}$ ve ${ 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

Üst ve alt sınırlar

Ulam-Warburton'daki toplam ON hücre sayısı hücresel otomat

${ displaystyle U (n)}$ vardır fraktal ile benzer davranış keskin üst sınır için ${ displaystyle n geq 1}$ veren

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

Yalnızca üst sınırlar ${ displaystyle U (n)}$ 'yüksek su' noktalarında ${ displaystyle n = 2 ^ {k}}$.

Bunlar aynı zamanda UWCA'nın karelere dayandığı, Hex-UWCA'nın altıgenlere dayalı olduğu ve Sierpinski üçgeni temel şekillerine dönerler.^[7]

Üst ve alt sınırları ${ displaystyle U (n) / n ^ {2}}$

Üstünü sınırla ve altını sınırla

Sahibiz

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

Alt sınır Robert Price tarafından elde edildi (OEIS sıra A261313 ) ve hesaplanması birkaç hafta sürdü ve alt sınırın iki katı olduğuna inanılıyor ${ displaystyle { frac {T (n)} {n ^ {2}}}}$ nerede ${ displaystyle T (n)}$ içindeki toplam kürdan sayısı kürdan dizisi nesile kadar ${ displaystyle n}$^[8]

İle ilişkili

Hex-Ulam-Warburton hücresel otomat - nesil 11

Altıgen UWCA

Altıgen-Ulam-Warburton hücresel otomat (Hex-UWCA) 2 boyutlu bir fraktal üzerinde büyüyen desen normal ızgara altıgenlerden oluşan hücrelerin. UWCA için aynı büyüme kuralı geçerlidir ve model nesiller içinde bir altıgene geri döner. ${ displaystyle n = 2 ^ {k}}$, ilk altıgen nesil olarak kabul edildiğinde ${ displaystyle 1}$UWCA'nın kareyi dört çeyreğe bölen ilk hücrenin köşelerinden geçen iki yansıma çizgisi vardır, benzer şekilde Hex-UWCA altıgeni altı kısma bölen üç yansıma çizgisine sahiptir ve büyüme kuralı simetrileri izler. Merkezleri bir yansıma simetrisi çizgisinde uzanan hücreler asla doğmaz.

Hex-UWCA modeli keşfedilebilir İşte.

Sierpinski üçgeni

Sierpinski üçgeni - nesil 16

Sierpinski üçgeni, 13. yüzyıl İtalyan yer mozaiklerinde görülür. Wacław Sierpiński 1915'te üçgeni tanımladı.

Üçgenin büyümesini göz önünde bulundurursak, her satır bir nesle ve en üst sıradaki nesile karşılık gelir. ${ displaystyle 1}$ tek bir üçgendir, sonra UWCA ve Hex-UWCA gibi nesiller içinde başlangıç ​​şekline geri döner ${ displaystyle n = 2 ^ {k}.}$

Kürdan dizisi

Kürdan dizisi - nesil 13

Kürdan kalıbı, dikey eksenle hizalanmış bir kare ızgara üzerine birim uzunlukta tek bir kürdan yerleştirilerek oluşturulur. Sonraki her aşamada, her kürdan ucu için, o uca ortalanmış dikey bir kürdan yerleştirin. Ortaya çıkan yapı, fraktal benzeri bir görünüme sahiptir.

Kürdan ve UWCA yapıları, bir kürdan üzerinde tanımlanan hücresel otomata örnekleridir. grafik ve sonsuz kare ızgaranın bir alt grafiği olarak düşünüldüğünde, yapı bir ağaç.

Kürdan dizisi, nesiller içinde tabanı döndürülmüş "H" şekline geri dönüyor ${ displaystyle n = 2 ^ {k}}$ nerede ${ displaystyle k geq 1}$

kürdan dizisi ve çeşitli kürdan benzeri diziler keşfedilebilir İşte.

Kombinatoryal oyun teorisi

Bir çıkarma oyunu İki oyuncunun dönüşümlü olarak üç jeton yığınını ikisinden eşit miktarda jeton alıp üçüncü yığına ekleyerek değiştirdiği LIM adlı, Ulam-Warburton kullanılarak tanımlanabilen bir dizi kazanma pozisyonuna sahiptir. otomat.^[9][10]

Tarih

Otomatanın başlangıcı, Ulam 1929'da yirmi yaşındayken Ulam'ın Stanislaw Mazur ile Lwów Polonya'da bir kahvehanede yaptığı konuşmaya geri dönüyor.^[11] Ulam ile çalıştı John von Neumann Savaş yıllarında iyi arkadaş olduklarında ve hücresel otomatı tartıştıklarında. Von Neumann, bu fikirleri evrensel kurucu ve dijital bilgisayar konseptinde kullandı. Ulam, 1962'de basit bir kuralı kullanarak kare tabanlı bir hücre yapısının büyümesinin bir taslağını yayınlayarak biyolojik ve "kristal benzeri" kalıplara odaklandı. Mike Warburton, olasılıksal sayı teorisinde çalışan amatör bir matematikçidir ve bu konuda eğitim almıştır. George Heriot'un Okulu Edinburgh'da. Oğlunun matematiği GCSE kurs, kuralla Öklid düzleminde eşkenar üçgenlerin veya karelerin büyümesini araştırmayı içeriyordu - yeni bir nesil, ancak ve ancak sonuncuya yalnızca bir kenarla bağlanırsa doğar. Bu ders, her nesilde doğan ON hücrelerinin sayısı için yinelemeli bir formülle sona erdi. Daha sonra Warburton, 2002 yılında Open University’nin M500 dergisinde not olarak yazdığı keskin üst sınır formülü buldu. David Singmaster makaleyi okudu, yapıyı analiz etti ve nesneyi 2003 tarihli makalesinde Ulam-Warburton hücresel otomat olarak adlandırdı. O zamandan beri çok sayıda tamsayı dizisine yol açtı.

Referanslar

Dış bağlantılar

• UWCA, Hex-UWCA ve ilgili tam sayı dizisini keşfedin animasyonlar
• Neil Sloane: Müthiş Kürdan Desenleri - Numberphile. (UWCA 8: 20'de başlar)