Το «Game of Life» των Math αποκαλύπτει επαναλαμβανόμενα μοτίβα που αναζητούνται από καιρό | Περιοδικό Quanta

Το 1969, ο Βρετανός μαθηματικός John Conway επινόησε ένα απίστευτα απλό σύνολο κανόνων για τη δημιουργία πολύπλοκης συμπεριφοράς. Το Παιχνίδι της Ζωής του, που συχνά αναφέρεται απλώς ως Ζωή, εκτυλίσσεται σε ένα άπειρο τετράγωνο πλέγμα κελιών. Κάθε κύτταρο μπορεί να είναι είτε «ζωντανό» ή «νεκρό». Το πλέγμα εξελίσσεται σε μια σειρά από στροφές (ή «γενιές»), με τη μοίρα κάθε κυττάρου να καθορίζεται από τα οκτώ κύτταρα που το περιβάλλουν. Οι κανόνες είναι οι εξής:

1. Γέννηση: Ένα νεκρό κελί με ακριβώς τρεις ζωντανούς γείτονες γίνεται ζωντανό.
2. Επιβίωση: Ένα ζωντανό κελί με δύο ή τρεις ζωντανούς γείτονες παραμένει ζωντανό.
3. Θάνατος: Ένα ζωντανό κύτταρο με λιγότερους από δύο ή περισσότερους από τρεις ζωντανούς γείτονες πεθαίνει.

Αυτοί οι απλοί κανόνες δημιουργούν μια εκπληκτικά ποικιλόμορφη σειρά μοτίβων ή «μορφών ζωής», που εξελίσσονται από τις πολλές διαφορετικές πιθανές αρχικές διαμορφώσεις του πλέγματος. Οι λάτρεις του παιχνιδιού έχουν καταμετρήσει και ταξινομήσει αυτά τα μοτίβα σε μια διαρκώς διευρυνόμενη διαδικτυακός κατάλογος. Ο Κόνγουεϊ ανακάλυψε ένα μοτίβο που ονομάζεται παρωπίδα, το οποίο ταλαντώνεται μεταξύ δύο καταστάσεων.

Το επόμενο έτος, βρήκε ένα πολύ πιο περίπλοκο μοτίβο που ονομάζεται πάλσαρ, το οποίο ταλαντώνεται μεταξύ τριών διαφορετικών καταστάσεων.

Αμέσως μετά την ανακάλυψη των ταλαντωτών, οι πρώτοι εξερευνητές του παιχνιδιού αναρωτήθηκαν αν υπάρχουν ταλαντωτές κάθε περιόδου. «Στην αρχή, είδαμε μόνο τις περιόδους 1, 2, 3, 4 και 15», είπε ο προγραμματιστής υπολογιστών και μαθηματικός Bill Gosper, ο οποίος θα συνέχιζε να ανακαλύπτει 17 διαφορετικούς νέους ταλαντωτές τις επόμενες δεκαετίες. Οι ταλαντωτές περιόδου 15 (που παρουσιάζονται παρακάτω) εμφανίστηκαν εκπληκτικά συχνά σε τυχαίες αναζητήσεις.

Οι εκπλήξεις καραδοκούσαν για όσους ήταν πρόθυμοι να τις βρουν. «Από ώρες και ημέρες προβολής, η περίοδος 5 φαινόταν αδύνατη», είπε ο Gosper. Στη συνέχεια, το 1971, δύο χρόνια μετά την εφεύρεση του παιχνιδιού, βρέθηκε ένα. Το κυνήγι για νέους ταλαντωτές εξελίχθηκε σε κύριο επίκεντρο του παιχνιδιού, μια αναζήτηση που ενισχύθηκε από την έλευση της τεχνολογίας των υπολογιστών. Οι λογαριασμοί κρυφών ερευνών που έγιναν σε υπολογιστές γραφείου έχουν γίνει ακρογωνιαίος λίθος της λαογραφίας του παιχνιδιού. «Ο χρόνος που έκλεψαν οι υπολογιστές από εταιρικούς και πανεπιστημιακούς μεγάλους υπολογιστές ήταν συγκλονιστικός», είπε ο Gosper.

Καθ' όλη τη διάρκεια της δεκαετίας του 1970, μαθηματικοί και χομπίστες συμπλήρωσαν τις άλλες σύντομες περιόδους και βρήκαν ένα σωρό μεγαλύτερες. Τελικά, οι μαθηματικοί ανακάλυψαν έναν συστηματικό τρόπο κατασκευής ταλαντωτών μακράς περιόδου. Αλλά οι ταλαντωτές με περιόδους μεταξύ 15 και 43 αποδείχτηκαν δύσκολο να βρεθούν. «Οι άνθρωποι προσπαθούν να βρουν τη μέση εδώ και χρόνια», είπε Μάγια Κάρποβιτς, μεταπτυχιακός φοιτητής στο Πανεπιστήμιο του Μέριλαντ. Η συμπλήρωση των κενών ανάγκασε τους ερευνητές να ονειρευτούν μια σειρά από νέες τεχνικές που ωθούσαν τα όρια αυτού που θεωρούνταν δυνατό με τα κυτταρικά αυτόματα, όπως αποκαλούν οι μαθηματικοί εξελισσόμενα πλέγματα όπως το Life.

Τώρα ο Κάρποβιτς και έξι συν-συγγραφείς ανακοίνωσαν στο α Προεκτύπωση Δεκεμβρίου ότι βρήκαν τις δύο τελευταίες περιόδους που λείπουν: 19 και 41. Με αυτά τα κενά καλυμμένα, η Ζωή είναι πλέον γνωστό ότι είναι «παντοπεριοδική» — ονομάστε έναν θετικό ακέραιο και υπάρχει ένα μοτίβο που επαναλαμβάνεται μετά από τόσα πολλά βήματα.

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

Ταλαντωτές με περιόδους μικρότερες από 15 μπορούν να βρεθούν χειροκίνητα ή με στοιχειώδεις αλγόριθμους που αναζητούν ταλαντωτές ένα κελί τη φορά. Αλλά καθώς η περίοδος μεγαλώνει, τόσο μεγαλώνει και η πολυπλοκότητα, καθιστώντας τις αναζητήσεις ωμής βίας πολύ λιγότερο αποτελεσματικές. «Για μικρές περιόδους, μπορείτε να κάνετε απευθείας αναζήτηση», είπε ο Matthias Merzenich, συν-συγγραφέας της νέας εργασίας που ανακάλυψε τον πρώτο ταλαντωτή περιόδου-31 το 2010. «Αλλά δεν μπορείτε πραγματικά να προχωρήσετε πέρα ​​από αυτό. Δεν μπορείς απλά να διαλέξεις μια περίοδο και να την ψάξεις». (Ο Merzenich απέκτησε το διδακτορικό του στα μαθηματικά από το Oregon State University το 2021, αλλά επί του παρόντος εργάζεται σε μια φάρμα.)

Το 1996, ο Ντέιβιντ Μπάκιγχαμ, ένας Καναδός ανεξάρτητος σύμβουλος υπολογιστών και λάτρης της Ζωής που έψαχνε για μοτίβα από τα τέλη της δεκαετίας του 1970, έδειξε ότι ήταν δυνατό να κατασκευαστούν ταλαντωτές περιόδου 61 και άνω στέλνοντας ένα μοτίβο γύρω από ένα κλειστό κομμάτι σε έναν ατελείωτο βρόχο. . Ελέγχοντας το μήκος του βρόχου - και τον χρόνο που χρειάστηκε το μοτίβο για να ολοκληρωθεί ένα ταξίδι μετ' επιστροφής - το Μπάκιγχαμ διαπίστωσε ότι μπορούσε να κάνει την περίοδο όσο μεγάλη ήθελε. «Είναι χημεία χωρίς αστείες μυρωδιές ή σπασμένα γυάλινα σκεύη», είπε. «Όπως η κατασκευή ενώσεων και στη συνέχεια η εξερεύνηση των αλληλεπιδράσεων μεταξύ τους». Αυτό σήμαινε ότι, με μια πτώση, είχε βρει έναν τρόπο να κατασκευάσει ταλαντωτές αυθαίρετα μεγάλων περιόδων, εφόσον ήταν μεγαλύτερες από 61.

Υπήρξε μια σειρά αποτελεσμάτων στα μέσα της δεκαετίας του 1990, όταν πολλοί από τους ταλαντωτές που έλειπαν μεταξύ 15 και 61 ανακαλύφθηκαν μέσω δημιουργικών συνδυασμών γνωστών ταλαντωτών, στους οποίους είχαν δοθεί μια σειρά από πολύχρωμα ονόματα. Τα κέτερερ συνδυάστηκαν με φανάρια, τα ηφαίστεια έβγαλαν σπίθες και οι φάγοι έτρωγαν ανεμόπτερα.

Μέχρι το γύρισμα του 21ου αιώνα, μόνο μια ντουζίνα περίοδοι ήταν ακόμα εκκρεμείς. «Φαινόταν πολύ πιθανό να λυθεί αυτό το πρόβλημα», είπε ο Merzenich. Το 2013, μια νέα ανακάλυψη που ονομάζεται βρόχος Snark βελτίωσε την τεχνική του Μπάκιγχαμ του 1996 και μείωσε το όριο πάνω από το οποίο ήταν εύκολο να κατασκευαστούν ταλαντωτές από 61 σε 43. Αυτό άφησε μόνο πέντε ελλείπουσες περιόδους. Ένα ακόμη ανακαλύφθηκε το 2019 και δύο ακόμη το 2022, αφήνοντας μόνο 19 και 41 — και τα δύο πρωταρχικά. "Οι πρώτοι είναι πιο δύσκολοι επειδή δεν μπορείτε να χρησιμοποιήσετε ταλαντωτές μικρής περιόδου για να τους κατασκευάσετε", είπε ο Merzenich.

Ο Μίτσελ Ράιλι, μεταδιδακτορικός ερευνητής στο Πανεπιστήμιο της Νέας Υόρκης του Άμπου Ντάμπι και ένας άλλος συν-συγγραφέας της νέας εργασίας, ενδιαφέρεται εδώ και πολύ καιρό από έναν τύπο ταλαντωτή που ονομάζεται ταλαντωτής. "Ο τρόπος με τον οποίο λειτουργούν οι ταλαιπωρημένοι είναι, έχετε ένα ενεργό μοτίβο στη μέση και μερικά σταθερά πράγματα στο εξωτερικό που αντιδρούν με αυτό", εξήγησε ο Riley. Το σταθερό υλικό, που ονομάζεται καταλύτης, είναι εκεί για να ωθήσει το ενεργό μοτίβο πίσω στην αρχική του κατάσταση.

Ο σχεδιασμός τους είναι δύσκολος. «Όλα αυτά τα μοτίβα είναι απίστευτα εύθραυστα», είπε ο Ράιλι. «Αν βάλεις μια μόνο κουκκίδα εκτός τόπου, συνήθως απλώς εκρήγνυνται».

Ο Riley δημιούργησε ένα πρόγραμμα που ονομάζεται Barrister για να αναζητήσει νέους καταλύτες. «Αυτό που ψάχνουμε είναι νεκρές φύσεις που είναι στιβαρές. Το όλο θέμα είναι ότι θέλουμε να αλληλεπιδράσουν με αυτό που συμβαίνει στη μέση και μετά να ανακάμψουν», είπε ο Ράιλι.

Ο Riley τροφοδότησε καταλύτες που βρήκε ο Barrister σε ένα άλλο πρόγραμμα αναζήτησης που τους συνδύαζε με ενεργά μοτίβα. Αυτό οδήγησε κυρίως σε αποτυχίες, είπε. «Είναι αρκετά σπάνιο κάποιος από αυτούς τους καταλύτες να επιβιώσει από την αλληλεπίδραση. Δεν υπάρχει εγγύηση επιτυχίας. Απλώς σταυρώνετε τα δάχτυλά σας και ελπίζετε να πετύχετε το τζάκποτ. Αισθάνεται λίγο σαν τζόγος».

Τελικά, το στοίχημά του απέδωσε. Μετά από μερικές παραλίγο αστοχίες - και μια τροποποίηση στον κώδικα που επέκτεινε την αναζήτηση για να συμπεριλάβει συμμετρικά μοτίβα - βρήκε μια αλληλεπίδραση καταλύτη που θα μπορούσε να διατηρήσει έναν ταλαντωτή περιόδου-19. «Οι άνθρωποι δοκίμαζαν όλα τα είδη πραγματικά περίπλοκων αναζητήσεων με πολλούς καταλύτες και πολλά σπάνια ενεργά πράγματα στη μέση, αλλά το μόνο που χρειαζόταν ήταν να βρεθεί αυτός ο νέος ογκώδης καταλύτης», είπε ο Ράιλι.

Η τελευταία περίοδος που λείπει, 41 ετών, βρέθηκε από τον Nicolo Brown, έναν άλλο συν-συγγραφέα, ο οποίος είναι ακόμα προπτυχιακός μάθημα μαθηματικών στο Πανεπιστήμιο της Καλιφόρνια, Santa Cruz. Ο Brown χρησιμοποίησε ανεμόπτερα ως καταλύτες, μια ιδέα που προτάθηκε για πρώτη φορά από τον Merzenich.

«Έχουμε ανακαλύψει τόσο βαθιά συμπεριφορά τα τελευταία 10 χρόνια», είπε ο Karpovich. «Όλοι γιορτάζουν για μια εβδομάδα - και μετά προχωρούν σε άλλα πράγματα. Υπάρχουν τόσα άλλα προβλήματα προς επίλυση». Μπορούν οι ταλαντωτές μιας δεδομένης περιόδου να γίνουν μικρότεροι; Μπορούν να βρεθούν ταλαντωτές στους οποίους κάθε κύτταρο ταλαντώνεται; Μπορούν να κατασκευαστούν όπλα με συγκεκριμένες περιόδους; Μπορούν τα διαστημόπλοια να ταξιδεύουν με συγκεκριμένες ταχύτητες;

Όπως το έθεσε το Μπάκιγχαμ, «Είναι σαν να είσαι παιδί σε ένα άπειρο κατάστημα παιχνιδιών».