Μετάβαση στο περιεχόμενο

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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Οι πρώτες είκοσι επαναλήψεις Ούλαμ-Γουάρμπαρτον κυτταρικού αυτόματου

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

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

[Επεξεργασία | επεξεργασία κώδικα]

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

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

and for

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

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]
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

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

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

[Επεξεργασία | επεξεργασία κώδικα]
Συνολικός αριθμός κελιών ON στο Ulam-Warburton CA και τετραγωνικά και

Για όλες τις ακέραιες ακολουθίες της μορφής όπου και

Έστω

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]
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 στο Κυτταρικό αυτόματο Ούλαμ-Γουάρμπαρτον

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

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

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]

Έχουμε

Το κατώτερο όριο προέκυψε από τον Robert Price (OEIS ακολουθία A261313 ) και χρειάστηκαν αρκετές εβδομάδες για να υπολογιστεί και πιστεύεται ότι είναι διπλάσιο από το κατώτερο όριο του όπου είναι ο συνολικός αριθμός των οδοντογλυφίδων στην ακολουθία οδοντογλυφίδων μέχρι τη γενιά [8]

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

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]
Ακολουθία οδοντογλυφίδας - γενιά 13

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

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

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

[Επεξεργασία | επεξεργασία κώδικα]
  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