Αυτόματο Ούλαμ-Γουάρμπαρτον

Οι πρώτες είκοσι επαναλήψεις Ούλαμ-Γουάρμπαρτον κυτταρικού αυτόματου

Το Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον (UWCA) είναι ένα δισδιάστατο μορφοκλασματικό πρότυπο που αναπτύσσεται σε ένα κανονικό πλέγμα κελιών που αποτελείται από τετράγωνα. Ξεκινώντας με ένα αρχικά ενεργοποιημένο τετράγωνο και όλα τα υπόλοιπα απενεργοποιημένα, δημιουργούνται διαδοχικές επαναλήψεις ενεργοποιώντας όλα τα τετράγωνα που μοιράζονται ακριβώς μία ακμή με ένα ενεργοποιημένο τετράγωνο. Αυτή είναι η γειτονιά φον Νόιμαν. Το αυτόματο πήρε το όνομά του από τον πολωνικής καταγωγής Αμερικανό μαθηματικό και επιστήμονα Στάνισλαβ Ούλαμ^[1] και τον Σκωτσέζο μηχανικό, εφευρέτη και ερασιτέχνη μαθηματικό Μάικ Γουάρμπαρτον^[2][3].

Ιδιότητες και συσχετισμοί

Το UWCA είναι ένα 2D 5- γειτονικό εξωτερικό ολοκληρωτικό Κυτταρικό αυτόματο που χρησιμοποιεί τον κανόνα 686.^[4]

Ο αριθμός των κελιών που ενεργοποιούνται σε κάθε επανάληψη σημειώνεται ${\displaystyle u(n),}$ χρησιμοποιώντας έναν ρητό τύπο:

${\displaystyle u(0)=0,u(1)=1,}$ and for ${\displaystyle n\geq 2}$

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

όπου ${\displaystyle wt(n)}$ είναι η συνάρτηση βάρους Χάμινγκ που μετρά τον αριθμό των 1 στο δυαδικό ανάπτυγμα του ${\displaystyle n}$^[5]

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

Το ελάχιστο άνω όριο του αθροίσματος για ${\displaystyle k}$ είναι τέτοιο ώστε ${\displaystyle 2^{k}\geq n}$

Ο συνολικός αριθμός των κελιών που είναι ενεργοποιημένα ON συμβολίζεται με ${\displaystyle 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}}}$

Πίνακας ακέραιων ακολουθιών n_m και 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

${\displaystyle U(n)}$ είναι OEIS ακολουθία A147562 και ${\displaystyle u(n)}$ είναι OEIS ακολουθία A147582

Καταμέτρηση κελιών με τετραγωνικά

Συνολικός αριθμός κελιών ON ${\displaystyle U(n)}$ στο Ulam-Warburton CA και τετραγωνικά ${\displaystyle U_{1},U_{3}}$ και ${\displaystyle U_{17}}$

Για όλες τις ακέραιες ακολουθίες της μορφής ${\displaystyle n_{m}=m\cdot 2^{k}}$ όπου ${\displaystyle m\geq 1}$ και ${\displaystyle k\geq 0}$

Έστω

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

Τότε ο συνολικός αριθμός των κελιών ON στην ακέραια ακολουθία ${\displaystyle n_{m}}$ δίνεται από τη σχέση ^[6]

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

Ή ως προς ${\displaystyle k}$ έχουμε

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

Πίνακας ακέραιων ακολουθιών n_m και 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

Ανώτερα και κατώτερα όρια

Συνολικός αριθμός κελιών ON στο Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον

${\displaystyle U(n)}$ έχει συμπεριφορά που μοιάζει με φράκταλ με ένα απότομο άνω όριο για ${\displaystyle n\geq 1}$ που δίνεται από τη σχέση

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

Το ανώτερο όριο έρχεται σε επαφή με το ${\displaystyle U(n)}$ μόνο στα σημεία "υψηλού ύδατος" όταν ${\displaystyle n=2^{k}}$.

Αυτές είναι επίσης οι γενιές στις οποίες το UWCA με βάση τα τετράγωνα, το Εξάγωνο-UWCA με βάση τα εξάγωνα και το τρίγωνο Σιερπίνσκι επιστρέφουν στο βασικό τους σχήμα.^[7]

Ανώτερα και κατώτερα όρια των ${\displaystyle U(n)/n^{2}}$

Ανώτερο όριο και κατώτερο όριο

Έχουμε

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

Το κατώτερο όριο προέκυψε από τον Robert Price (OEIS ακολουθία A261313 ) και χρειάστηκαν αρκετές εβδομάδες για να υπολογιστεί και πιστεύεται ότι είναι διπλάσιο από το κατώτερο όριο του ${\displaystyle {\frac {T(n)}{n^{2}}}}$ όπου ${\displaystyle T(n)}$ είναι ο συνολικός αριθμός των οδοντογλυφίδων στην ακολουθία οδοντογλυφίδων μέχρι τη γενιά ${\displaystyle n}$^[8]

Σχέση με

Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον (Hex-UWCA) - γενιά 11

Εξαγωνικό UWCA

Το Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον (Hex-UWCA) είναι ένα 2-διάστατο μορφοκλασματικό σχέδιο που αναπτύσσεται σε ένα κανονικό πλέγμα κυττάρων που αποτελείται από εξάγωνα. Ισχύει ο ίδιος κανόνας ανάπτυξης για το UWCA και το μοτίβο επιστρέφει σε ένα εξάγωνο σε γενιές ${\displaystyle n=2^{k}}$, όταν το πρώτο εξάγωνο θεωρείται ως γενιά ${\displaystyle 1}$. Το UWCA έχει δύο γραμμές ανάκλασης που περνούν από τις γωνίες του αρχικού κελιού χωρίζοντας το τετράγωνο σε τέσσερα τεταρτημόρια, ομοίως το Hex-UWCA έχει τρεις γραμμές ανάκλασης χωρίζοντας το εξάγωνο σε έξι τμήματα και ο κανόνας ανάπτυξης ακολουθεί τις συμμετρίες. Τα κύτταρα των οποίων τα κέντρα βρίσκονται πάνω σε μια γραμμή συμμετρίας ανάκλασης δεν γεννιούνται ποτέ.

Το μοτίβο Hex-UWCA μπορεί να εξερευνηθεί εδώ.

Τρίγωνο Σιερπίνσκι

Για περισσότερες λεπτομερές: Τρίγωνο Σιερπίνσκι

Τρίγωνο Σιερπίνσκι - γενιά 16

Το τρίγωνο Σιερπίνσκι εμφανίζεται σε ιταλικά ψηφιδωτά δαπέδου του 13ου αιώνα. Ο Βάτσλαβ Σιερπίνσκι περιέγραψε το τρίγωνο το 1915.

Αν εξετάσουμε την ανάπτυξη του τριγώνου, με κάθε σειρά να αντιστοιχεί σε μια γενιά και την πάνω σειρά γενιά ${\displaystyle 1}$ να είναι ένα ενιαίο τρίγωνο, τότε όπως το UWCA και το Hex-UWCA επιστρέφει στο αρχικό του σχήμα, σε γενιές ${\displaystyle n=2^{k}.}$

Ακολουθία οδοντογλυφίδας

Ακολουθία οδοντογλυφίδας - γενιά 13

Το σχήμα οδοντογλυφίδας κατασκευάζεται με την τοποθέτηση μιας οδοντογλυφίδας μοναδιαίου μήκους σε ένα τετράγωνο πλέγμα, ευθυγραμμισμένο με τον κατακόρυφο άξονα. Σε κάθε επόμενο στάδιο, για κάθε εκτεθειμένο άκρο οδοντογλυφίδας, τοποθετείται μια κάθετη οδοντογλυφίδα με κέντρο το άκρο αυτό. Η προκύπτουσα δομή έχει εμφάνιση που μοιάζει με φράκταλ.

Οι δομές οδοντογλυφίδας και UWCA είναι παραδείγματα κυτταρικών αυτομάτων που ορίζονται σε γράφο και όταν θεωρούνται ως υπογράφος του άπειρου τετραγωνικού πλέγματος η δομή είναι ένα δέντρο.

Η ακολουθία της οδοντογλυφίδας επιστρέφει στο βασικό περιστρεφόμενο σχήμα "H" σε γενιές ${\displaystyle n=2^{k}}$ όπου ${\displaystyle k\geq 1}$

Η ακολουθία οδοντογλυφίδας και διάφορες ακολουθίες που μοιάζουν με οδοντογλυφίδες μπορούν να εξεταστούν εδώ.

Συνδυαστική θεωρία παιγνίων

Ένα παιχνίδι αφαίρεσης που ονομάζεται LIM, στο οποίο δύο παίκτες τροποποιούν εναλλάξ τρεις στοίβες από μάρκες παίρνοντας ίση ποσότητα από δύο στοίβες και προσθέτοντας την ίδια ποσότητα στην τρίτη στοίβα, διαθέτει ένα σύνολο νικηφόρων θέσεων που μπορούν να περιγραφούν χρησιμοποιώντας το αυτόματο Ούλαμ-Γουάρμπαρτον.^[9][10]

Ιστορία

Οι απαρχές των αυτομάτων ανάγονται σε μια συζήτηση που είχε ο Ούλαμ με τον Στάνισλαβ Μαζούρ σε μια καφετέρια στο Λβοβ της Πολωνίας, όταν ο Ούλαμ ήταν είκοσι ετών το 1929^[11]. Ο Ούλαμ συνεργάστηκε με τον Τζον φον Νόιμαν κατά τη διάρκεια των ετών του πολέμου, όταν έγιναν καλοί φίλοι και συζήτησαν για τα κυψελοειδή αυτόματα. Ο φον Νόιμαν χρησιμοποίησε αυτές τις ιδέες στην ιδέα του για τον καθολικό κατασκευαστή και τον ψηφιακό υπολογιστή. Ο Ούλαμ επικεντρώθηκε σε βιολογικά και "κρυστάλλινα" μοτίβα δημοσιεύοντας ένα σκίτσο της ανάπτυξης μιας κυτταρικής δομής με βάση το τετράγωνο χρησιμοποιώντας έναν απλό κανόνα το 1962. Ο Μάικ Γουόρμπαρτον είναι ερασιτέχνης μαθηματικός που ασχολείται με την πιθανολογική θεωρία αριθμών και σπούδασε στο George Heriot's School του Εδιμβούργου. Η εργασία μαθηματικών GCSE του γιου του περιελάμβανε τη διερεύνηση της ανάπτυξης ισόπλευρων τριγώνων ή τετραγώνων στο ευκλείδειο επίπεδο με τον κανόνα - μια νέα γενιά γεννιέται εάν και μόνο εάν συνδέεται με την προηγούμενη με μία μόνο ακμή. Αυτή η εργασία κατέληγε σε έναν αναδρομικό τύπο για τον αριθμό των κελιών ON που γεννιούνται σε κάθε γενιά. Αργότερα, ο Γουόρμπαρτον βρήκε τον τύπο του αιχμηρού ανώτερου ορίου, τον οποίο έγραψε ως σημείωμα στο περιοδικό M500 του Ανοικτού Πανεπιστημίου το 2002. Ο Ντέιβιντ Σίνγκμαστερ διάβασε το άρθρο, ανέλυσε τη δομή και ονόμασε το αντικείμενο κυτταρικό αυτόματο των Ούλαμ-Γουόρμπαρτον σε άρθρο του το 2003. Έκτοτε έχει δώσει αφορμή για πολυάριθμες ακέραιες ακολουθίες.

Εξωτερικοί σύνδεσμοι

• Explore the UWCA, Hex-UWCA and related integer sequence animations
• Neil Sloane: Terrific Toothpick Patterns - Numberphile. (The UWCA starts at time 8:20)

Δείτε επίσης

• Αλγόριθμος διαμαντιού τετραγώνου
• Καμπύλη που γεμίζει το χώρο
• Νιφάδα του Κοχ
• Καμπύλη Χίλμπερτ
• Καμπύλη του δράκου
• Σπόγγος του Μένγκερ

• Σύνολο Μάντελμπροτ
• Σύνολο Julia
• Οικοδομήσιμο Σύμπαν

Παραπομπές

1. S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in BiologicalSciences, 14 (1962), 215–224.
2. M. Warburton, One-edge connections, M500 Magazine of The Open University, 188 Αρχειοθετήθηκε 2021-10-21 στο Wayback Machine. (2002), 11
3. D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195 Αρχειοθετήθηκε 2022-07-06 στο Wayback Machine. (2003), 2–7
4. OEIS - Index to 2D 5-Neighbor Cellular Automata,[1],
5. Applegate, David; Pol, Omar E.; Sloane, N. J. A. (2010). «The Toothpick Sequence and Other Sequences from Cellular Automata». Congressus Numerant 206: 157–191. 
6. Mike Warburton, "Ulam-Warburton Automaton - Counting Cells with Quadratics ", arXiv:1901.10565
7. Tanya Khovanova, Eric Nie, Alok Puranik, "The Sierpinski Triangle and the Ulam-Warburton Automaton", arXiv:1408.5937
8. Steven R. Finch, Mathematical Constants II, 364-365
9. Fink, Alex; Fraenkel, Aviezri S.; Santos, Carlos (May 2013), «LIM is not slim», International Journal of Game Theory 43 (2): 269–281, doi:10.1007/s00182-013-0380-z 
10. Khovanova, Tanya; Xiong, Joshua (2014), «Nim fractals», Journal of Integer Sequences 17 (7): Article 14.7.8, 17 
11. S. M. Ulam, Adventures of a Mathematician, p32