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

Το Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον (UWCA) είναι ένα δισδιάστατο μορφοκλασματικό πρότυπο που αναπτύσσεται σε ένα κανονικό πλέγμα κελιών που αποτελείται από τετράγωνα. Ξεκινώντας με ένα αρχικά ενεργοποιημένο τετράγωνο και όλα τα υπόλοιπα απενεργοποιημένα, δημιουργούνται διαδοχικές επαναλήψεις ενεργοποιώντας όλα τα τετράγωνα που μοιράζονται ακριβώς μία ακμή με ένα ενεργοποιημένο τετράγωνο. Αυτή είναι η γειτονιά φον Νόιμαν. Το αυτόματο πήρε το όνομά του από τον πολωνικής καταγωγής Αμερικανό μαθηματικό και επιστήμονα Στάνισλαβ ΟύλαμS. M. Ulam, On some mathematical problems connected with patterns of growth of figures, Mathematical Problems in BiologicalSciences, 14 (1962), 215–224. και τον Σκωτσέζο μηχανικό, εφευρέτη και ερασιτέχνη μαθηματικό Μάικ ΓουάρμπαρτονM. Warburton, One-edge connections, M500 Magazine of The Open University, 188  (2002), 11D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of The Open University, 195  (2003), 2–7.

Ιδιότητες και συσχετισμοί
Το UWCA είναι ένα 2D 5- γειτονικό εξωτερικό ολοκληρωτικό Κυτταρικό αυτόματο που χρησιμοποιεί τον κανόνα 686.OEIS - Index to 2D 5-Neighbor Cellular Automata,,

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

 and for 

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

Το ελάχιστο άνω όριο του αθροίσματος για  είναι τέτοιο ώστε 

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

Πίνακας ακέραιων ακολουθιών nm και Um

 0  1  1 39 5  25 749 1  2 5 637 10  10114197 2  4 21 1214920  40528789 3  8 85 2459740 1,621 563,157 4  16 341 482,38980 6,48511212,629 5  32 1,365 969,557160 25,941 22450,517

 είναι OEIS ακολουθία A147562 και  είναι OEIS ακολουθία A147582

Καταμέτρηση κελιών με τετραγωνικά
Για όλες τις ακέραιες ακολουθίες της μορφής  όπου  και 

Έστω

Τότε ο συνολικός αριθμός των κελιών ON στην ακέραια ακολουθία  δίνεται από τη σχέση Mike Warburton, "Ulam-Warburton Automaton - Counting Cells with Quadratics ", arXiv:1901.10565

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

Πίνακας ακέραιων ακολουθιών nm και Um
 0  1  1 39 5  25 749 1  2 5 637 10  10114197 2  4 21 1214920  40528789 3  8 85 2459740 1,621 563,157 4  16 341 482,38980 6,48511212,629 5  32 1,365 969,557160 25,941 22450,517

Ανώτερα και κατώτερα όρια
 έχει συμπεριφορά που μοιάζει με φράκταλ με ένα απότομο άνω όριο για   που δίνεται από τη σχέση



Το ανώτερο όριο έρχεται σε επαφή με το  μόνο στα σημεία "υψηλού ύδατος" όταν .

Αυτές είναι επίσης οι γενιές στις οποίες το UWCA με βάση τα τετράγωνα, το Εξάγωνο-UWCA με βάση τα εξάγωνα και το τρίγωνο Σιερπίνσκι επιστρέφουν στο βασικό τους σχήμα.Tanya Khovanova, Eric Nie, Alok Puranik, "The Sierpinski Triangle and the
Ulam-Warburton Automaton", arXiv:1408.5937


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

Έχουμε

Το κατώτερο όριο προέκυψε από τον Robert Price (OEIS ακολουθία A261313 ) και χρειάστηκαν αρκετές εβδομάδες για να υπολογιστεί και πιστεύεται ότι είναι διπλάσιο από το κατώτερο όριο του  όπου  είναι ο συνολικός αριθμός των οδοντογλυφίδων στην ακολουθία οδοντογλυφίδων μέχρι τη γενιά Steven R. Finch, Mathematical Constants II, 364-365

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

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

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

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

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

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

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

Η ακολουθία της οδοντογλυφίδας επιστρέφει στο βασικό περιστρεφόμενο σχήμα "H" σε γενιές   όπου 

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

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

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

Παραπομπές



Κατηγορία:Φράκταλ