Ulam–Warburton otomatı - Ulam–Warburton automaton

Ulam-Warburton hücresel otomat (UWCA) bir 2-boyutlu oransal bir yetişen desen düzenli bir ızgara kareler oluşan bir hücre. Başlangıçta bir kare AÇIK ve diğerleri KAPALI ile başlayarak, bir AÇIK kare ile tam olarak bir kenarı paylaşan tüm kareler AÇIK duruma getirilerek ardışık yinelemeler oluşturulur. Burası von Neumann mahallesi . Otomat, adını Polonyalı-Amerikalı matematikçi ve bilim adamı Stanislaw Ulam ile İskoç mühendis, mucit ve amatör matematikçi Mike Warburton'dan almıştır.

Ulam-Warburton hücresel otomatının ilk yirmi yinelemesi

Özellikler ve ilişkiler

UWCA, kural 686'yı kullanan 2B 5 komşulu bir dış totalistik hücresel otomattır.

Her yinelemede AÇIK duruma getirilen hücre sayısı, açık bir formülle belirtilir: ${\görüntüleme stili u(n),}$

${\görüntüleme stili u(0)=0,u(1)=1,}$ ve için ${\görüntüleme stili n\geq 2}$

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

nerede olduğu Hamming ağırlığı ikili genişleme 1'ler sayar fonksiyonu${\ Displaystyle wt(n)}$${\görüntüleme stili n}$

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

Toplamın minimum üst sınırı şu şekildedir:${\görüntüleme stili k}$${\ Displaystyle 2^{k}>n}$

AÇIK olan toplam hücre sayısı belirtilir ${\görüntüleme stili U(n)}$

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

Tablo , ve${\ Displaystyle wt(n)}$${\görüntüleme stili u(n)}$${\görüntüleme stili U(n)}$

Tablo, farklı girdilerin aynı çıktıya yol açabileceğini göstermektedir. ${\ Displaystyle wt(n)}$

Bu örtük özellik, büyümenin basit kuralından ortaya çıkar - yeni bir hücre, mevcut bir ON hücresiyle yalnızca bir kenarı paylaşıyorsa doğar - süreç düzensiz görünür ve içeren işlevler tarafından modellenir, ancak kaosun içinde düzenlilik vardır. ${\ Displaystyle wt(n)}$

${\görüntüleme stili n}$	${\ Displaystyle wt(n)}$	${\görüntüleme stili u(n)}$	${\görüntüleme stili U(n)}$	${\görüntüleme stili n}$	${\ Displaystyle wt(n)}$	${\görüntüleme stili u(n)}$	${\görüntüleme stili 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

${\görüntüleme stili U(n)}$olan OEIS dizisi A147562 ve bir OEIS dizisi A147582${\görüntüleme stili u(n)}$

İkinci dereceden hücrelerle sayma

Ulam–Warburton CA ve ikinci dereceden ifadelerdeki toplam ON hücrelerinin sayısı ve${\görüntüleme stili U(n)}$${\displaystyle U_{1},U_{3}}$${\ Displaystyle U_{17}}$

Formun tüm tamsayı dizileri için nerede ve${\displaystyle n_{m}=m\cdot 2^{k}}$${\displaystyle m\geq 1}$${\görüntüleme stili k\geq 0}$

İzin vermek

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

( Olup OEIS dizisi A130665 ) ${\ Displaystyle a_{m}}$

Daha sonra tamsayı dizisindeki toplam ON hücrelerinin sayısı şu şekilde verilir: ${\displaystyle n_{m}}$

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

Ya da sahip olduğumuz açısından${\görüntüleme stili k}$

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

Tamsayı dizileri tablosu ve${\displaystyle n_{m}}$${\ Displaystyle U_{m}}$

${\görüntüleme stili k}$	${\görüntüleme stili n_{1}}$	${\ Displaystyle U_{1}}$	${\ Displaystyle n_{3}}$	${\görüntüleme stili U_{3}}$	${\görüntüleme stili n_{5}}$	${\görüntüleme stili U_{5}}$	${\görüntüleme stili 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	3157
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 hücresel otomatındaki toplam AÇIK hücre sayısı

${\görüntüleme stili U(n)}$sahip fraktal bir ile benzeri davranış keskin üst sınırı için verilen ${\displaystyle n\geq 1}$

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

Üst sınır yalnızca 'yüksek su' noktalarında temas ettiğinde . ${\görüntüleme stili U(n)}$${\görüntüleme stili n=2^{k}}$

Bunlar aynı zamanda karelere dayalı UWCA'nın, altıgenlere dayalı Hex-UWCA'nın ve Sierpinski üçgeninin temel şekillerine geri döndüğü nesillerdir .

alt ve üst sınırları ${\ Displaystyle U(n)/n^{2}}$

Üstünü sınırla ve aşağıyı sınırla

Sahibiz

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

Alt sınır, Robert Fiyat (elde edilmiştir OEIS dizisi A261313 ) ve bilgi işlem için birkaç hafta sürdü ve iki kez alt sınır olduğuna inanılmaktadır burada kürdan toplam sayı olduğu kürdan dizisine jenerasyona kadar${\displaystyle {\frac {T(n)}{n^{2}}}}$${\görüntüleme stili T(n)}$${\görüntüleme stili n}$

İle ilişkili

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

Altıgen UWCA

Hexagonal-Ulam-Warburton hücresel otomat (Hex-UWCA), altıgenlerden oluşan düzenli bir hücre ızgarası üzerinde büyüyen 2 boyutlu bir fraktal modeldir . UWCA için aynı büyüme kuralı geçerlidir ve ilk altıgen nesil olarak kabul edildiğinde örüntü nesiller içinde bir altıgene döner . UWCA, kareyi dört çeyreğe bölen ilk hücrenin köşelerinden geçen iki yansıma çizgisine sahiptir, benzer şekilde Hex-UWCA'nın altıgeni altı bölüme ayıran üç yansıma çizgisi vardır ve büyüme kuralı simetrileri takip eder. Merkezleri bir yansıma simetrisi çizgisi üzerinde bulunan hücreler asla doğmazlar. ${\görüntüleme stili n=2^{k}}$${\görüntüleme stili 1}$

Hex-UWCA modeli burada incelenebilir .

Sierpinski üçgeni

Sierpinski üçgeni - 16. nesil

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

Üçgenin büyümesini göz önüne alırsak, her satır bir nesile karşılık gelir ve en üst sıra nesil tek bir üçgendir, o zaman UWCA ve Hex-UWCA gibi nesiller içinde başlangıç ​​şekline döner.${\görüntüleme stili 1}$${\görüntüleme stili n=2^{k}.}$

kürdan dizisi

Kürdan dizisi - nesil 13

Kürdan deseni, dikey eksenle hizalanmış kare bir ızgara üzerine birim uzunlukta tek bir kürdan yerleştirilerek oluşturulur. Sonraki her aşamada, açıkta kalan her kürdan ucu için, bu 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 grafikte tanımlanan hücresel otomatların örnekleridir ve sonsuz kare ızgaranın bir alt grafiği olarak düşünüldüğünde, yapı bir ağaçtır .

Kendi tabanına kürdan dizi döner kuşaklarda 'H' şeklini döndürülür burada${\görüntüleme stili n=2^{k}}$${\görüntüleme stili k\geq 1}$

Kürdan sekansı ve çeşitli kürdan benzeri diziler keşfedilebilir burada .

Kombinatoryal oyun teorisi

İki oyuncunun, iki yığından eşit miktarda jeton alarak ve üçüncü yığına aynı miktarı ekleyerek üç jeton yığınını dönüşümlü olarak değiştirdiği LIM adlı bir çıkarma oyunu , aşağıdakiler kullanılarak tanımlanabilecek bir dizi kazanma pozisyonuna sahiptir. Ulam-Warburton otomatı.

Tarih

Otomatların başlangıcı, Ulam'ın 1929'da yirmi yaşındayken Polonya'nın Lwów kentindeki bir kahvede Stanislaw Mazur ile yaptığı sohbete kadar gider. Ulam , savaş yıllarında John von Neumann ile birlikte çalıştı ve onlar iyi arkadaş oldular ve hücresel otomat hakkında konuştular. Von Neumann, bu fikirleri evrensel bir 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' desenlere odaklandı. Mike Warburton, Edinburgh'daki George Heriot's School'da eğitim görmüş, olasılıksal sayı teorisinde çalışan amatör bir matematikçidir . Oğlunun matematik GCSE dersi, kuralla Öklid düzlemindeki 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ğlıysa doğar. Bu kurs, her nesilde doğan ON hücrelerinin sayısı için özyinelemeli bir formülle sonuçlandı. Daha sonra Warburton, 2002 yılında Open University'nin M500 dergisinde bir not olarak yazdığı keskin üst sınır formülünü buldu. David Singmaster makaleyi okudu, yapıyı analiz etti ve 2003 tarihli makalesinde nesneye Ulam-Warburton hücresel otomat adını verdi. O zamandan beri sayısız tamsayı dizisine yol açmıştır.

Referanslar

Dış bağlantılar

• UWCA, Hex-UWCA ve ilgili tamsayı dizisi animasyonlarını keşfedin
• Neil Sloane: Müthiş Kürdan Kalıpları - Numberphile. (UWCA 8:20'de başlar)