1D-Raumschiff im Conway's Game of Life entdeckt, 3,7 Milliarden Zellen

• Conways Spiel des Lebens (Conway’s Game of Life) wurde im Forum ein eindimensionales 1D-Raumschiff-Muster (1D spaceship) mit einer Länge von rund 3,7 Milliarden Zellen (3,7B) fertiggestellt
• Dieses Muster bewegt sich mit einer Periode von 133.076.755.768 Generationen; die Startgrenzenbox hat die Größe 3707300605×1 Zellen
• Die Entwickler kombinierten vier Konstruktorarme, darunter den komprimierten Bauarm ECCA1·ECCA2 (arm), den Binärarm (binary arm), den Funkensetzungsarm (fuse arm) und weitere Systeme, um Selbstreplikation, Bereinigung und Neustart umzusetzen
• Die Simulation wurde in den Umgebungen von Golly und lifelib verifiziert; apg(calcyman) fügte einen vollständigen Code zur Zyklusüberprüfung zum Repository hinzu
• Der Fund gilt als Beispiel für Fortschritte in der Slow-Salvo-Technik und bei Werkzeugen zur Automatisierung riesiger Muster

---

Abschlussbericht zum 1D-Raumschiff

• Hippo.69 meldete, dass ein "2c/133076755768-Raumschiff**" fertiggestellt sei; damit verschiebt es zwei Zellen pro Periode
  • Der y-Wertebereich liegt bei etwa ±5,537,521,000, die maximale x-Koordinate bei etwa 11,075,626,500
• apg(calcyman) überprüfte durch eine vollständige Simulation, dass das Muster korrekt läuft, und korrigierte einen Tippfehler in der Periodenangabe
• Das Endergebnis wurde in mehreren .mc-Dateien (example.mc, example_42168M.mc, example_46000M.mc) veröffentlicht und erlaubt die schrittweise Wiedergabe in Golly

Simulation und Fehlersuche

• Während der ersten Debug-Phase erzeugte ein Cordership einen rückwärts gerichteten Glider, der SoD-Schäden (Stop of Destruction) verursachte
  • Der „switch far seed“ wurde angepasst, sodass dieser Glider berücksichtigt wird
• Die Simulation nutzte die Hashlife-Optimierung von lifelib, um schnell um viele Millionen Generationen zu springen
• Ein auf BigNum basierendes Lua-Skript automatisiert in Golly große Generationssprünge und speichert Checkpoints bei wichtigen Ereignissen (z. B. ECCA2-Start, Cordership-Eintreffen usw.)

Aufbau und Funktionsweise

• Das Gesamtsystem besteht aus vier Bauarmen
  • Fuse arm: Erzeugung und Initialisierung eines eindimensionalen Signals auf Basis eines Blinkers
  • Binary arm: Interpretiert Bit-Signale aus der Kombination von zwei Glidern, um Strukturen zu erzeugen
  • ECCA1 / ECCA2: Ein hochdichtes Bauarmsystem, das komprimierte Befehle interpretiert, das Muster bereinigt und die nächste Generation vorbereitet
• Im letzten Schritt schießt ECCA2 eine Cordership-Flotte (cordership fleet), entfernt Restmuster und kehrt letztlich in den eindimensionalen Zustand (y=0) zurück
• Der gesamte Ablauf ist als vollständig symmetrische Struktur ausgelegt, sodass beide Seiten um die zentrale Achse (Spine) identisch arbeiten

Entwicklung und Zusammenarbeit

• Das Projekt wurde von calcyman(apg) und Hippo.69 gemeinsam abgeschlossen
  • calcyman entwarf die erste Hälfte (Arm-Struktur und Codebasis)
  • Hippo.69 führte in den folgenden Jahren die restlichen Arbeiten an Bereinigung, Synchronisierung und Debugging durch
• Forum-Nutzer schlugen den Namen "Arrow 1" oder "Unidimensional Spaceship 1" vor
• Community-Mitglieder wie hth3 und I6_I6 versuchten Simulationen in Golly und hinterließen Glückwünsche

Technische Bedeutung

• Dieses Raumschiff ist das erste riesige, selbstreplizierende Muster, das sich in eindimensionaler Form bewegt, und demonstriert ein neues Niveau rechnerischer Komplexität im Game of Life
• Fortgeschrittene Techniken wie Slow-Salvo-Automatisierung, ECCA-Komprimierungsinterpreter und Cordership-Steuerung wurden umfassend eingesetzt
• Forschende planen weitere Optimierungen zur Verkleinerung und zur Geschwindigkeitssteigerung; eine Veröffentlichung zu diesem Thema wird ebenfalls geprüft

[GN⁺]

Hacker-News-Kommentare

• Ich habe erst mit „Oh, interessant“ angefangen zu lesen, hatte aber keine Ahnung, dass es in der Game-of-Life-Community so viel Fachjargon gibt
  Begriffe wie ECCA1 und gpse90 kamen im Sekundentakt vor, sodass ich wohl am Ende ein paar Stunden im Wiki lesen muss

  • Das kostenlose Buch Conway’s Game of Life: Mathematics and Construction ist gut als Einstieg geeignet
  • Ich schaue ungefähr einmal im Jahr in dieses Forum hinein, und es überrascht mich immer wieder, wie viele Menschen dort enorm viel Zeit und Denkleistung investieren
  • Eigentlich ist das weniger „Game-of-Life-Terminologie“ als vielmehr mathematische Terminologie aus dem Bereich cellular automata

• Erstaunlich ist, dass es mit einer einfachen Linie beginnt, dann explosionsartig zu einer riesigen komplexen 2D-Struktur wird und nach zahllosen Generationen wieder zu einer 3,7B Zellen langen Linie zurückkehrt
  Ich wünschte, jemand würde die Abstraktionseinheiten darin analysieren

  • Laut diesem Forenbeitrag ist es tatsächlich eine spärliche Struktur, bei der im Verhältnis zur Linienlänge weniger als 1/100 der Zellen lebendig sind (Unidimensional spaceship 1)
  • Dank der Erklärung verstehe ich es jetzt. Zuerst dachte ich, es sei ein Glider in einem eindimensionalen zellulären Automaten

• Die lange Erklärung im GoL-Forum zu lesen fühlt sich an, als würde mein Ehepartner meinen Zoom-Arbeitsmeetings zuhören. Dieses Feuerwerk an Fachbegriffen ist großartig

  • Um mir das Gefühl vorzustellen, musste ich an dieses Video denken
  • Ich finde, das ist eine viel lustigere Analogie, als es das karma dieses Kommentars vermuten lässt
  • Der einzige Unterschied ist, dass ich auch dann begeistert bin, wenn ich nichts verstehe. Mein Ehepartner interessiert sich eher für meine Stimmung — so etwas wie: „Also entspricht diese RISC-Architektur nicht ADA-1056? Wow, toll Schatz!“

• „Oh mein Gott, das ist ein Quine!“
  Wenn die lineare Bitsequenz als Game-of-Life-Board interpretiert wird, ist es eine Struktur, die sich selbst zwei Pixel nach rechts verschoben reproduziert
  Das ist schwieriger als einfache Reproduktion, aber die Deutung als bandartiger Selbstreplikator, der seinen eigenen Code um 2 Pixel versetzt kopiert, ist wunderschön

  • Tatsächlich nennt man so eine Struktur ein „spaceship“. Es ist eines von zwei spaceships, die am selben Tag entdeckt wurden. Aber ein 1D spaceship ist diesmal eine Premiere
  • Bewegung ist sogar einfacher als Selbstreplikation. Ein echter replicator wurde noch nicht entdeckt, obwohl es Millionen von spaceships gibt

• Da stand, man solle „zu Generation 42168M springen, weil der Anfang langsam ist“, und dabei musste ich an Wesen denken, die das Universum wie ein Spielzeug behandeln und sagen: „So ab 13,8B Jahren wird es interessant“

  • Philosophisch betrachtet könnte auch die Realität eine komplexe GoL-Simulation sein. Wenn wir uns in einer Simulation befinden, würden wir das überhaupt erkennen können?

• Es gibt zwei interessante offene Fragen zum Game of Life

  1. Wie ist das Verhalten bei zufälligen Anfangszuständen? Da es Turing-vollständig ist, könnten sogar intelligente Lebensformen entstehen. Herrscht Chaos vor, oder taucht Intelligenz auf? (dazugehörige Diskussion)
  2. Gibt es superstabile Strukturen, die trotz beliebiger externer Störungen erhalten bleiben? (dazugehörige Frage)
  • Die erste Frage wird in William Poundstones The Recursive Universe (1984) behandelt. Das Buch versteht selbstreplizierende Maschinen als Definition von Leben, und später war Gemini von Andrew J. Wade aus dem Jahr 2010 der erste erfolgreiche Fall, der dieser Definition entsprach.
    Die Wahrscheinlichkeit, dass in zufälligen Anfangszuständen Leben entsteht, ist nahezu null, aber Leben hat Evolutionspotenzial
  • Es ist zwar Turing-vollständig, aber reale Berechnung ist schwierig, und Muster tendieren eher zu Chaos oder zum Erlöschen. Um Information zu transportieren, braucht man komplexe Strukturen wie spaceships. Varianten wie Lenia oder Neural CA sind dagegen stabiler
  • Zufällige Konfigurationen sind voller homogener Störungen mit 50 % Dichte, daher entstehen interessante Strukturen nur selten. Man muss mit skalenfreiem Rauschen beginnen, damit globale Strukturen auftreten
  • Turing-Vollständigkeit garantiert keine Intelligenz, aber auf einer unendlichen Ebene könnte irgendwann doch ein intelligentes Wesen entstehen und alles ausfüllen. Wenn mehrere entstehen, könnten sie allerdings in einen gegenseitigen Auslöschungswettbewerb geraten
  • Wenn man einer unendlichen Ebene weiter zufällig Punkte hinzufügt, wird irgendwann ein intelligentes Leben entstehen, das Energie niedriger Entropie in hohe Entropie umwandelt

• Ich habe früher einmal ein Experiment mit einem kontinuierlich bewegten Glider gemacht — glider.gif

  • Wirklich wunderschön. Es wirkt wie ein Kunstwerk, das die Grundregeln visuell ausdrückt

• Ich habe mich gefragt, ob es eine Visualisierung dieses Gliders gibt. Ich wollte die Zeitachse als eine Dimension sehen

  • So wie ich es verstehe, ist das in 2D-GoL einfach nur eine Anfangs-Linie von 1x3,7B Zellen
  • Zum Ausführen ist die Software Golly am besten geeignet. Dank des HashLife-Algorithmus lässt es sich schnell simulieren
  • Nach dem ersten Schritt ist es schon nicht mehr 1D, daher ist so eine Visualisierung unmöglich

• Es handelt sich um eine Struktur, die nur in bestimmten Phasen in einen Kasten mit der Höhe 1 Zelle passt

  • Ich bin kein GoLtician, aber unter den Standardregeln scheint so etwas außer Stillstand oder Auslöschung unmöglich zu sein.
    Trotzdem ist die in diesem Thread spürbare Leidenschaft und Sorgfalt wirklich beeindruckend

• 1995 bekam ich einmal eine E-Mail von jemandem namens John Conway. Damals nur wegen eines Beitrags, den ich in einer Mathematik-Newsgroup geschrieben hatte, und erst später wurde mir klar, dass es tatsächlich Conway war
  Wenn ich jetzt diese erstaunliche GoL-Welt sehe, frage ich mich, wofür die Menschheit dieses kreative Potenzial eigentlich einsetzen sollte