Maths „Spiel des Lebens“ enthüllt lang ersehnte, sich wiederholende Muster | Quanta-Magazin

Im Jahr 1969 entwickelte der britische Mathematiker John Conway ein verblüffend einfaches Regelwerk zur Erzeugung komplexer Verhaltensweisen. Sein Spiel des Lebens, oft einfach als „Leben“ bezeichnet, entfaltet sich auf einem unendlichen quadratischen Gitter aus Zellen. Jede Zelle kann entweder „lebendig“ oder „tot“ sein. Das Gitter entwickelt sich über eine Reihe von Runden (oder „Generationen“), wobei das Schicksal jeder Zelle durch die acht sie umgebenden Zellen bestimmt wird. Die Regeln lauten wie folgt:

1. Geburt: Eine tote Zelle mit genau drei lebenden Nachbarn wird lebendig.
2. Überleben: Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt am Leben.
3. Tod: Eine lebende Zelle mit weniger als zwei oder mehr als drei lebenden Nachbarn stirbt.

Diese einfachen Regeln erzeugen eine erstaunlich vielfältige Reihe von Mustern oder „Lebensformen“, die sich aus den vielen verschiedenen möglichen Ausgangskonfigurationen des Gitters entwickeln. Liebhaber des Spiels haben diese Muster in einer ständig wachsenden Zahl zusammengestellt und taxonomisiert Online-Katalog. Conway entdeckte ein Muster namens Blinker, das zwischen zwei Zuständen oszilliert.

Im nächsten Jahr entdeckte er ein viel komplizierteres Muster namens Pulsar, das zwischen drei verschiedenen Zuständen oszilliert.

Kurz nach der Entdeckung der Oszillatoren fragten sich die frühen Entdecker des Spiels, ob es Oszillatoren jeder Epoche gibt. „Zuerst sahen wir nur die Perioden 1, 2, 3, 4 und 15“, sagte der Computerprogrammierer und Mathematiker Bill Gosper, der im Laufe der nächsten Jahrzehnte 17 verschiedene neuartige Oszillatoren entdecken sollte. Oszillatoren der Periode 15 (siehe unten) tauchten bei Zufallssuchen überraschend häufig auf.

Überraschungen lauerten auf diejenigen, die bereit waren, sie zu finden. „Nach stunden- und tagelangen Betrachtungen schien Periode 5 unmöglich“, sagte Gosper. Dann wurde 1971, zwei Jahre nach der Erfindung des Spiels, eines gefunden. Die Suche nach neuen Oszillatoren wurde zu einem Hauptschwerpunkt des Spiels, eine Suche, die durch das Aufkommen der Computertechnologie noch verstärkt wurde. Berichte über verdeckte Durchsuchungen auf Bürocomputern sind zu einem Eckpfeiler der Folklore des Spiels geworden. „Die Menge an Computerzeit, die den Großrechnern von Unternehmen und Universitäten gestohlen wurde, war atemberaubend“, sagte Gosper.

In den 1970er Jahren füllten Mathematiker und Hobbyforscher die anderen kurzen Zeiträume aus und fanden ein paar längere Zeiträume. Schließlich entdeckten Mathematiker einen systematischen Weg, Oszillatoren mit langer Periode zu bauen. Es erwies sich jedoch als schwierig, Oszillatoren mit Perioden zwischen 15 und 43 zu finden. „Seit Jahren versuchen die Leute, die Mitte herauszufinden“, sagte er Maia Karpowitsch, ein Doktorand an der University of Maryland. Um die Lücken zu schließen, mussten sich die Forscher eine Reihe neuer Techniken ausdenken, die die Grenzen dessen erweiterten, was mit zellulären Automaten, wie Mathematiker sich entwickelnde Gitter wie das Leben nennen, für möglich gehalten wurde.

Jetzt haben Karpovich und sechs Co-Autoren in einem angekündigt Dezember-Vorabdruck dass sie die letzten beiden fehlenden Perioden gefunden haben: 19 und 41. Nachdem diese Lücken gefüllt sind, ist das Leben nun als „omniperiodisch“ bekannt – nennen Sie eine positive ganze Zahl, und es gibt ein Muster, das sich nach so vielen Schritten wiederholt.

Die wachsende Gemeinschaft, die sich dem Studium des Lebens widmet und zu der viele forschende Mathematiker, aber auch viele Hobbyforscher gehören, hat nicht nur Oszillatoren, sondern alle möglichen neuen Muster gefunden. Sie haben Muster gefunden, die sich über das Gitter bewegen, sogenannte Raumschiffe, und Muster, die andere Muster bilden: Waffen, Konstrukteure und Brüter. Sie fanden Muster, die Primzahlen berechnen, und sogar Muster, die beliebig komplizierte Algorithmen ausführen können.

Oszillatoren mit Perioden von weniger als 15 können manuell oder mit rudimentären Algorithmen gefunden werden, die Zelle für Zelle nach Oszillatoren suchen. Doch je länger der Zeitraum wird, desto größer wird auch die Komplexität, wodurch Brute-Force-Suchen deutlich weniger effektiv werden. „Nach kleinen Perioden kann man direkt suchen“, sagt Matthias Merzenich, Mitautor der neuen Arbeit, der 31 den ersten Perioden-2010-Oszillator entdeckte. „Aber man kann nicht wirklich darüber hinausgehen.“ Man kann nicht einfach einen Zeitraum auswählen und danach suchen.“ (Merzenich erlangte 2021 seinen Doktortitel in Mathematik an der Oregon State University, arbeitet aber derzeit auf einer Farm.)

Im Jahr 1996 zeigte David Buckingham, ein kanadischer freiberuflicher Computerberater und Life-Enthusiast, der seit den späten 1970er Jahren nach Mustern gesucht hatte, dass es möglich war, Oszillatoren der Periode 61 und höher zu konstruieren, indem man ein Muster in einer Endlosschleife um eine geschlossene Spur schickte . Durch die Kontrolle der Länge der Schleife – und der Zeit, die das Muster für einen Umlauf benötigte – stellte Buckingham fest, dass er die Periode so groß machen konnte, wie er wollte. „Es ist Chemie ohne komische Gerüche oder zerbrochene Glaswaren“, sagte er. „Zum Beispiel Verbindungen aufzubauen und dann die Wechselwirkungen zwischen ihnen zu untersuchen.“ Das bedeutete, dass er auf einen Schlag eine Möglichkeit gefunden hatte, Oszillatoren mit beliebig langen Perioden zu konstruieren, solange diese länger als 61 waren.

Mitte der 1990er Jahre gab es eine Reihe von Ergebnissen, als viele der fehlenden Oszillatoren zwischen 15 und 61 durch kreative Kombinationen bekannter Oszillatoren entdeckt wurden, denen eine Reihe farbenfroher Namen gegeben worden waren. Caterer wurden mit Ampeln kombiniert, Vulkane spuckten Funken und Esser aßen Segelflugzeuge.

Um die Wende des 21. Jahrhunderts waren nur noch ein Dutzend Perioden ausstehend. „Es schien sehr gut möglich, dieses Problem zu lösen“, sagte Merzenich. Im Jahr 2013 verbesserte eine neue Entdeckung namens Snark-Schleife Buckinghams Technik von 1996 und senkte den Grenzwert, oberhalb dessen es einfach war, Oszillatoren zu konstruieren, von 61 auf 43. Dadurch fehlten nur noch fünf Perioden. Eine weitere wurde 2019 entdeckt und zwei weitere im Jahr 2022, so dass nur noch 19 und 41 übrig blieben – beide erstklassige. „Primzahlen sind schwieriger, weil man zu ihrer Konstruktion keine Oszillatoren mit kleiner Periode verwenden kann“, sagte Merzenich.

Mitchell Riley, Postdoktorand an der New York University Abu Dhabi und weiterer Co-Autor der neuen Arbeit, ist seit langem von einer Art Oszillator namens Hassler fasziniert. „Die Art und Weise, wie Hassler arbeiten, ist, dass man in der Mitte ein aktives Muster und außen ein stabiles Zeug hat, das darauf reagiert“, erklärte Riley. Der stabile Stoff, der als Katalysator bezeichnet wird, dient dazu, das aktive Muster wieder in seinen ursprünglichen Zustand zu versetzen.

Sie zu entwerfen ist schwierig. „Alle diese Muster sind unglaublich fragil“, sagte Riley. „Wenn man einen einzelnen Punkt verrutscht, explodieren sie normalerweise einfach.“

Riley hat ein Programm namens Barrister ins Leben gerufen, um nach neuen Katalysatoren zu suchen. „Was wir suchen, sind Stillleben, die robust sind. Der springende Punkt ist, dass wir wollen, dass sie mit dem, was in der Mitte passiert, interagieren und sich dann erholen“, sagte Riley.

Riley speiste Katalysatoren, die Barrister gefunden hatte, in ein anderes Suchprogramm ein, das sie mit aktiven Mustern verknüpfte. Dies führe meist zu Misserfolgen, sagte er. „Es ist ziemlich selten, dass einer dieser Katalysatoren die Wechselwirkung überlebt. Es gibt keine Erfolgsgarantie. Man drückt einfach die Daumen und hofft, dass man den Jackpot knackt. Es fühlt sich ein bisschen wie Glücksspiel an.“

Schließlich zahlte sich seine Wette aus. Nach ein paar Beinaheunfällen – und einer Änderung des Codes, die die Suche auf symmetrische Muster erweiterte – fand er eine Katalysatorwechselwirkung, die einen Oszillator der 19. Periode aufrechterhalten konnte. „Die Leute hatten alle möglichen wirklich komplizierten Suchvorgänge mit vielen Katalysatoren und vielen seltenen aktiven Dingen in der Mitte ausprobiert, aber alles, was nötig war, war, diesen neuen, klobigen Katalysator zu finden“, sagte Riley.

Der letzte fehlende Punkt, 41, wurde von Nicolo Brown gefunden, einem weiteren Co-Autor, der immer noch Mathematik an der University of California in Santa Cruz studiert. Brown nutzte Segelflugzeuge als Katalysatoren, eine Idee, die erstmals von Merzenich vorgeschlagen wurde.

„Wir haben in den letzten zehn Jahren so viel tiefgreifendes Verhalten entdeckt“, sagte Karpovich. „Jeder feiert eine Woche lang – und wendet sich dann anderen Dingen zu. Es gibt so viele andere Probleme zu lösen.“ Können Oszillatoren einer bestimmten Periode kleiner gemacht werden? Gibt es Oszillatoren, bei denen jede einzelne Zelle schwingt? Können Waffen mit bestimmten Perioden hergestellt werden? Können Raumschiffe mit bestimmten Geschwindigkeiten unterwegs sein?

Wie Buckingham es ausdrückte: „Es ist, als wäre man ein Kind in einem unendlichen Spielzeugladen.“