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

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

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

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

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

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

$u(0)=0,u(1)=1,$ and for $n\ge 2$

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

όπου $wt(n)$ είναι η συνάρτηση βάρους Χάμινγκ που μετρά τον αριθμό των 1 στο δυαδικό ανάπτυγμα του $n$

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

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

Ο συνολικός αριθμός των κελιών που είναι ενεργοποιημένα ON συμβολίζεται με $U(n)$

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

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

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

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

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

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

Έστω

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

Τότε ο συνολικός αριθμός των κελιών ON στην ακέραια ακολουθία $n_m$ δίνεται από τη σχέση

$U_m(n_m)=\frac{a_m}{m^2}\frac{4}{3}{n}_m^2-\frac{1}{3}$

Ή ως προς $k$ έχουμε

$U_m(k)=a_m\frac{4}{3}{2}^{2k}-\frac{1}{3}$

Πίνακας ακέραιων ακολουθιών n_m και 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	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 στο Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον

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

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

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

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

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

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

Έχουμε

$0.9026116569...=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{U(n)}{n^2}<\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{U(n)}{n^2}=\frac{4}{3}$

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

Σχέση με

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

Εξαγωνικό UWCA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ιστορία

Οι απαρχές των αυτομάτων ανάγονται σε μια συζήτηση που είχε ο Ούλαμ με τον Στάνισλαβ Μαζούρ σε μια καφετέρια στο Λβοβ της Πολωνίας, όταν ο Ούλαμ ήταν είκοσι ετών το 1929. Ο Ούλαμ συνεργάστηκε με τον Τζον φον Νόιμαν κατά τη διάρκεια των ετών του πολέμου, όταν έγιναν καλοί φίλοι και συζήτησαν για τα κυψελοειδή αυτόματα. Ο φον Νόιμαν χρησιμοποίησε αυτές τις ιδέες στην ιδέα του για τον καθολικό κατασκευαστή και τον ψηφιακό υπολογιστή. Ο Ούλαμ επικεντρώθηκε σε βιολογικά και "κρυστάλλινα" μοτίβα δημοσιεύοντας ένα σκίτσο της ανάπτυξης μιας κυτταρικής δομής με βάση το τετράγωνο χρησιμοποιώντας έναν απλό κανόνα το 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
• Οικοδομήσιμο Σύμπαν