Hunting the Snark

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum

A while ago I wrote about zero-player games, including the famous Game of Life created by mathematician John Conway. If you are confused because you thought the Game of Life was a board game where you put a tiny peg character in a car and drive it around a board, here is a quick reminder of how the mathematical Game of Life works.

Imagine an infinite grid of squares – initially all empty (white). Some of these squares could be coloured in black, which we would call ‘alive’ cells, and the white cells can be thought of as ‘dead’. The way the game works is that at each step in time, we consider all the cells in their current state, and based on some rules we decide whether that cell will be alive, or dead, in the next time step.

The cells in the Game of Life have preferences fairly similar to real living organisms – they do not like to be lonely, so any cell which is only next to one other living cell, or no living cells, will die of loneliness. (‘Next to’ in this case includes horizontally, vertically or diagonally adjacent). They also prefer not to be overcrowded, so any cell which has four or more living neighbours will die out in the next iteration. And anything with exactly two or three neighbours stays alive to fight another day, or comes alive if it was not already.

A grid of white squares with some coloured black, demonstrating the rules of Game of Life in operation (as described in caption) and with a beehive (two cells on top row, two cells diagonally out to the sides on the next row and two cells on bottom row) a block (four cells in a square) and a boat (an L-shape of three black cells with two more black cells diagonally touching the ends of the legs of the L and each other)
Left: a living cell with no living neighbours will die; a dead cell with two living neighbours will come alive.
Right: three examples of ‘still life’ configurations which do not change: clockwise from left – beehive, block, boat

Why two and three?

Obviously, we could have picked any set of rules here – a slightly different definition of ‘neighbour’, or different thresholds for loneliness and overcrowding – but if your settings are not right, you might find it is very difficult to keep anything alive and that things all die out quickly, or that your board gets infested with a growing mass of black cells you cannot stop.

Animation showing a glider moving diagonally down and right; it changes between a long L-shape with one extra cell diagonally adjacent, and an S-shape with one extra cell, changing orientation and flipping between versions of these two

But with these particular rules, there is just enough balance for it to be interesting – some configurations die out, others stay alive forever (some examples above), and some behave in fun ways. For example, it is possible to make a glider, which iterates through a series of steps to create a version of itself one cell across from where it was before. Watching this loop repeat, the shape ‘glides’ across the grid and will keep going forever unless it is interrupted.

Animation showing three cells horizontally alternating with three cells vertically

Mathematicians seek out interesting structures that you can build in this universe of rules. One configuration of interest is the idea of an oscillator – something which loops through a set of states and returns to its exact original configuration. A simple example might be a ‘blinker’ – something which flips between two possible states, the simplest of which is a straight line of three cells. This will oscillate between a vertical line and horizontal line, unless disturbed by any other living cells nearby.

It is also possible to construct oscillators of other periods – ones which take three, four and five steps to return to their original state are seen below.

Animation showing the 'caterer' arrangement which flips through three different states (12 cells)
Animation showing the 'mazing' arrangement which flips through four different states (12 cells) and has diagonal symmetry
Animation showing the 'pseudo-barberpole' arrangement which flips through five different states (15 cells) and is a long diagonal stripe that looks like a bit like a rotating stripy barber's pole

Left-right: Caterer, Mazing and the Pseudo-Barberpole

Zooologists of Life

This obviously leads to a further question: Which periods of oscillator can be created in this game? The people who study this question are probably aware that such discoveries are not going to shatter the foundations of mathematics, or necessarily lead to much else beyond the satisfaction of finding the answer – but whole websites exist of enthusiasts seeking out and excitedly studying and cataloguing examples of life they have found, like Charles Darwin on a voyage of discovery.

The story of periodic oscillators has an interesting history: Oscillators of small periods (up to about 15) were found within a few years of the invention of the game in 1970, as well as some interesting examples of higher periods – the twin bees shuttle, a period 46 oscillator, was found by Life expert Bill Gosper in 1971.

Animation showing the twin bees shuttle, which has two block formations on the left and one on the right, and three other structures which move left to right crashing into the blocks and reversing direction, restoring the blocks each time

But the rest of the list took a bit longer to fill in. People continued to discover new oscillators over the years, but ticking off the list one at a time was unsatisfying. Surely we can find something that knocks out a bunch of cases in one go, like mathematical induction? Well, yes, we can. The existence of gliders in the game (structures which move in a straight line) means we can build more complex structures using a glider, and tweak them to get different periods.

A reflector is a structure in Life which is stable, but when a glider approaches it from the right direction, it will absorb it and create a new glider going off in a different direction. The first such structure was discovered by Paul Callahan in 1996, and over the next couple of decades many people discovered others, including ones which took fewer and fewer steps to complete the reflection, and using fewer initial live cells. The smallest known reflector is called the Snark, and was discovered in 2013 by Mike Playle – it reflects a glider through 90 degrees, and uses 52 cells (in a box of 23×17 cells).

Animation showing the Snark, which has a block formation in the centre and some wiggly shapes above and to the sides, which a glider hits from the bottom left and leaves towards the bottom right, after scrambling and restoring the block

This kind of structure can be used to build oscillators: Imagine pointing four of these at each other, so they pass a glider around between them. By tweaking the distance between the reflectors, and the types of reflectors used, we can build oscillators of any large period – and in fact this discovery meant that it is possible to construct an oscillator of any period greater than 59. The discovery of the Snark made this even smaller, showing that a non-trivial oscillator of any period 43 or above can be constructed.

Filling in the Gaps

This means, excitingly (for people who find this kind of thing sufficiently exciting), that we might be close to solving the problem in general, and finding an oscillator of every possible period. All we would need is to find oscillators of every period up to 43, and then we are covered. In July this year, one of the missing cases was fixed – a period 19 oscillator named Cribbage was found by Mitchell Riley.

This really put the pressure on Life-ologists to fill the one missing hole: The only period for which we did not know of a non-trivial oscillator was 41. But luckily, mathematicians do some of their best work under pressure and it took less than a week for Nico Brown to find one (casually posting it on the ConwayLife forums with the understated caption “Interesting loop”!) Consisting of 204 cells, the so-far-boringly named 204P41 oscillator (below – click for animation) completes a search which started over 50 years ago when this game was first invented.

Animation showing the 204P41 oscillator which flips through 41 states and has various gliders moving around in different directions between snark-like constructions and other blocks

This confirms that the Game of Life cellular automaton is omniperiodic – it has oscillators of every possible period. And yes, this research is not going to win any Nobel Prizes or spin off into whole new fields of research – but it has closed a gap in human knowledge and given us a new fun thing to play with – and is that not what maths is all about, really?

Avatar photo

Posted by

is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. Katie writes blog posts and editorials for The Aperiodical, a semi-regular maths news site.

16 comments

  1. This puzzle rsp game fascinates me every time – and for three years now, on every reminder like this one above, I’ve been thinking of Dylan Beattie’s talk ‘The Art of Code‘ at a 2023 NDC{London}, whose one sequence, the linked one, culminates in ‘Game of Life’ being programmed in ‘Game of Life’. Fabulous…

  2. Paul Rendell created „Game of Life“ patterns which are capable of Turing-complete computation. Its construction was completed on April 2, 2000. This particular Turing machine is infinite, as it requires an infinite length of tape to perform arbitrary

    see Turing machine

  3. Wer über grundsätzliche Funktionalität der Welt, dieser Welt nachdenken möchte, und so auch halbwegs konsistent getan hat, landet sozusagen zwangsläufig bei der Idee der sog. zellulären Automaten.

    Weil sich anders ein erkennendes Subjekt nicht kohärent vorstellen kann, im Kleinstwesen, in der “Mikrowelt”, die sich nicht mit der “Makrowelt” vereinbaren lässt, bisher nicht.

    Angeblich gibt es Regeln für diese Welt, die “turinggemäß” stattfinden könnten, wiederum sog. zelluläre Automaten meinend. – Einige nennen hier bestimmte Regeln, die sie sich mit Nummern merken.

    Allerdings ist, wie einige finden,
    die Naturwelt nie von der gedachten Welt, der Geisteswelt, eindeutig beschreibbar.
    Insofern ist Alan Turing hier nur mit Übung aufgefallen, wie übrigens auch Ludwig Wittgenstein.
    Beiderseits : positiv (wobei der “Tractatus” schon ein starkes Stück, auch in negativer Rezipienz, war).

    Mit freundlichen Grüßen
    Dr. Webbaer (der hier also ein Negativ zu setzen hat : ‘And yes, this research is not going to win any Nobel Prizes or spin off into whole new fields of research – but it has closed a gap in human knowledge and given us a new fun thing to play with – and is that not what maths is all about, really?’)

    • Die Mathematik meint, auch wörtlich, die Fähigkeitslehre, die insbesondere auch auf ihre Wiederwendbarkeit abhebt, sie meint “nicht wirklich” die Welt.

      Sondern Welten, die mit dieser Wellt übereinstimmen könn(t)en, sie ist an sich kohärent zu halten, sie erlaubt auch Anwendungen, dann in der physikalischen Abwendung.
      Es wird an dieser Stelle auch von Formalwissenschaft geredet.

      Sie kann auch als Veranstaltung hier gemeinter Trockennasenprimaten verstanden werden.

      Nie aber im Sinne weltlicher Wahrheit unterwegs.
      “Hope to Help”, HTH
      Dr. Webbaer (der sich so – ‘And yes, this research is not going to win any Nobel Prizes or spin off into whole new fields of research – but it has closed a gap in human knowledge and given us a new fun thing to play with – and is that not what maths is all about, really?’ – immer noch ein wenig ungut erregt, sich bekanntlich nie aufregen soll. Blutdruck und so)

    • Dr. Webbaer schrieb (23.11.2023, 13:41 o’clock):
      > […] Welten, die mit dieser Welt übereinstimmen könn(t)en […]

      Wer über grundsätzliche Bewertungen gegebener oder simulierter Welt(-Ausschnitte) durch die (wirklich, oder simuliert) direkt daran Beteiligten nachdenkt, sich dazu gedanklich ggf. “in die Lage” jeweils eines solchen Beteiligten “setzt”, und ausschließlich solche Bewertungs-Operationen anwenden möchte, deren Verständnis von vornherein und zugleich jedem solchen Beteiligten zugestanden werden müsste, der guten Gewissens fragen könnte: “Wie und Was soll ich denn überhaupt bewerten (damit mir all jene, die ebenfalls direkt beteiligt sind, zustimmen können) ?”, landet sozusagen zwangsläufig bei “den (traditionellen) Denkgesetzen” und den entsprechenden “elementaren Bewertungen mit binärem (Bit-)Wertebereich”:

      – entweder “das Selbe”, oder “Verschiedenes”;

      – entweder “zusammen/koinzident”, oder “voneinander getrennt/separat”;

      – entweder “wahr”, oder “falsch”;

      entweder “dead/off/blank”, oder “live/on/marked”;

      – entweder “neighbour”, oder “not”.

      Dass daraus wiederum Bewertungen von “(wahrscheinlichster) Funktionalität” bzw. “(wahrscheinlichster) Regel-mäßigkeit” nach (Robertson-Schrödinger-)(Fisher-Cramér-Rao-)Yang-Mills zu ermitteln sind … ist wohl mehr als “nur noch Formsache”, denn “dazwischen” bedarf es der ausdrücklichen und einvernehmlichen Konstruktion von (insbesondere geometrischen) Messgrößen bzw. Bewertungsoperationen, die Beziehungen zwischen mehr als nur zwei Beteiligten betreffen.

      • Es darf auch geredet werden, btw, der Webverweis auf die “(traditionellen) Denkgesetze” funktioniert nicht.
        Die Rede meint die Näherung, sie darf gerne kohärent sein, sie ist es aber “nie wirklich”, denn die Sprache ist an sich unpräzise, während Formeln nicht in der Lage sind die Welt sozusagen wirklich zu treffen, dafür aber ist die Formalwissenschaft kohärent.
        Insofern gibt es sog. Geisteswissenschaften, deren Personal, hier hat Dr. W zuzustimmen, idR intellektuell-kognitiv sparsam, wie ein Sparschwein sozusagen, ist, aber den “Geist” gilt es dann doch wissenschaftlich zu erfassen, sich dieser Erfassung anzunähern. [1]

        Amüsanterweise würde auch zeitgenössische AI mit anderen Personen, auch mit anderer zeitgenössischer AI den Verkehr in menschlicher Sprache suchen.
        Also nicht formalwissenschaftlich theoretisiert, sondern im Bildlichen.
        Dr. W sich hier sicher sein.

        Mit freundlichen Grüßen
        Dr. Webbaer

        [1]
        Eine sozusagen ganz zähe Person in diesem Zusammenhang war Carl Schmitt :
        -> https://de.wikipedia.org/wiki/Carl_Schmitt
        …der sozusagen ga-anz nah an der Sprache war, an ihrer Funktion, bestmöglich sozusagen; seine Nähe zum NS war unentschuldbar, er hat auch nie um Entschuldigung gebeten, soweit der Schreiber dieser Zeilen weiß, aber er war “nah an der Sache”; wer anders will, kann es mit Karl Kraus versuchen, der allerdings zur Parteilichkeit tendierte, sozusagen Parteilichkeit war, was aber auch nicht falsch sein muss.

      • Bonuskommentar dazu :

        entweder “wahr”, oder “falsch”

        An sich ist abär klar, dass es Unerfasstheiten gibt, bspw. so in zeitgenössischer, relationaler Datenhaltung repräsentiert :
        -> https://en.wikipedia.org/wiki/Null_(SQL)
        Wobei eine oder ein NULL auch ein ‘Value’ sein kann, anders als in der bekannten Online-Enzyklopädie benachrichtigt :

        SQL null is a marker, not a value. [Quelle]

        Was amüsant ist, so sein könnte, sozusagen direkt die Grenzen bärischer und menschlicher Erkenntnis adressiert.
        Wenn es sozusagen schon in der bekannten Online-Enzyklopädie, äh, versaut wird.
        Der NULL-Wert ist sozusagen intrinsisch auch einen Wert, der auch näher spezifiziert werden kann, ein NULL-Wert hat immer einen Zusammenhang, im Weltlichen.
        Dies eher spaßeshalber und sozusagen autistisch angemerkt.

    • Dr. Webbaer schrieb (24.11.2023, 09:18 o’clock):
      > […] btw, der Webverweis auf die “(traditionellen) Denkgesetze” funktioniert nicht.

      Ach! — danke! — und Entschuldigung! — Hier (auf die Schnelle, der Nachvollziehbarkeit halber) korrigiert:

      “… bei “den (tradionellen) Denkgesetzen” …”.

      (Das gründlichere Lesen der beiden kürzlich/heute von Dr. Webbaer vorgelegten Kommentare nehme ich mir demnächst vor; mit anschließender ausführlicherer Beantwortung ist zu rechnen.)

      • Jaja, Dr. W wartet nunmehr seit vier Tagen.

        Es gibt ansonsten Logik, die Formalwissenschaft meinend, und Folgerichtigkeit, die soziale Bezüge meint. [1]

        Ihrem obigen und an anderer Stelle erfolgten Gerede, Herr Dr. Frank Wappler, das nicht als Geschwätz bezeichnet werden soll, kann Dr. Webbaer an dieser Stelle und sog. traditionelle Denkgesetze meinend, nicht zustimmen.


        “Traditonellen Denkgesetzen” könnten zum Beispiel so gefolgt werden, auch das Biologische meinend :

        1.) Mache nie so, wie es die “Skaker” getan haben !

        2.) Nenne eine Hund einen Hund, nicht Menschen !

        3.) Suche nicht nach biologisch nicht nachgewiesener Maßnahme, wenn so die so folgenden Personen sozusagen Morgen nicht mehr da sein werden !
        (Die sogenannte Generation meinend.)


        Womit, bei den genannten Beispielen, wie logisch und folgerichtig sie auch sein könnten, letztlich die soziale Verständigkeit gemeint ist, die auch Opportunismus genannt werden könnte. [2]

        Wissenschaft, die Suche nach Erkenntnis kann ausschnittsweise, näherungsweise und um Interessen (!) bemüht bleiben, auch sich anschließende Theoretisierung so ausschnittsweise, näherungsweise und um Interessen (!) bemüht bleiben kann.

        Mit freundlichen Grüßen
        Dr. Webbaer

        [1]
        Dr. W quiekte – sozusagen! – wie gemeint auch zuletzt mit Freund “ChatGPT” ein wenig herum, wenn es um die (wichtige) Unterscheidung von Logik und Folgerichtigkeit ging; gegrunzt worden ist womöglich, abär nie gewiehert! *

        [2]
        Sie wird idR ‘utilaristisch’ genannt, was sozusagen auch cooler ist, die Menge nicht selten nicht folgen kann.

        *
        ‘Gewiehert’ werden sollte nicht, auch wenn gänzlich klar war, geworden ist, bei näherer wie gemeinter Diskussion, dass “Commander Spock” hier nicht selten fehlgegriffen hat, so vereinbart, in der Anschauung zwischen Dr. W und Freund “ChatGPT”.

        • Dies hier ist sozusagen der zentrale Song, Dr W. mag auch den Bass und ist sich vglw. sicher auch bei der werten hiesigen Inhaltegeberin gut anzukommen :

          -> https://www.youtube.com/watch?v=low6Coqrw9Y

          Angenommen, dass sich hier in der wie gemeinten kleinen Diskussion sozusagen einige wirklich auskennen, und sozusagen wirklich musikalisch bleiben.

          Musikalisch und theoretisch sozusagen, Dr. spielt nun zum Beispiel so ein :

          -> https://www.youtube.com/watch?v=low6Coqrw9Y

          MFG
          Wb – sicherlich geht es hier auch um die Metaphorik.

          Dr. W hat Roger Hodgson einmal getroffen, die, diese Band war “eigentlich” gar nicht so-o schlecht,

          • Dr. Webbaer schrieb (28.11.2023, 11:57 o’clock):
            > […] die (wichtige) Unterscheidung von Logik und Folgerichtigkeit […]

            Ohne irgendwen, der das nicht sowieso schon vor(gehabt)hätte, dazu anstiften zu wollen, diese zweifellos wichtige Unterscheidung ausführlicher auszumalen und zu dokumentieren:

            Mindestens ebenso wichtig finde ich aber den Begriff “Unterscheidung” an sich.

            Wer hielte es für denkbar, diesen Begriff (den wir in der deutschen Sprache “Unterscheidung” nennen; einschl. verwandter Begriffe, die insbesondere mit Worten des selben Wortstammes benannt werden) jemandem de novo” beizubringen,
            also jemandem, der nicht etwa nur das Wort “Unterscheidung” vorher noch nie gehört/gelesen/benutzt hat (weil er z.B. eine andere Muttersprache als Deutsch hat),
            sondern der gar keine Ahnung von dem (Konzept, Begriff) hat, was wir mit diesem Wort (Gewohnheits-, Erziehungs- und Ausbildungs-bedingt) benennen;
            der also von vornherein und zunächst gar nicht über den Begriff “Unterscheidung” verfügt
            ?

            (In dieser Fragestellung, geschätzter Dr Webbaer, erschöpft sich mein Interesse an unserer Korrespondenz mittlerweile weitgehend.
            Bei Interesse an meinen anderen Interessen gern nachfragen.)

            p.s.
            > Jaja, Dr. W wartet nunmehr seit vier Tagen. […]

            Tut mir leid; mein Verschulden; spricht wohl nicht besonders für die Unterhaltsamkeit der allfälligen “Chat”-ware.

            p.p.s.
            > “Traditonellen Denkgesetzen” könnten zum Beispiel so gefolgt werden […]
            > 1.) Mache nie so, wie es die “S[h]aker” getan haben !

            Warum eigentlich nicht ? —
            “Die” haben’s als Gruppe immerhin zu einem Wikipedia-Eintrag gebracht (der von jenen, die mit Wikipedia wie mit ihrem Eigentum umgehen, ja wohl hoffentlich nicht allzu bald gecancelt wird).

            > 2.) Nenne eine Hund einen Hund, nicht Menschen !

            Alias Ockhams Klinge; als Pendant zu “Leibniz’s Tüte”:
            Nenne einen Mann mit seinem Hund, die aneinander geleint sind, anders als den selben Mann mit seinem selben Hund, die einander frei laufen lassen; sofern du das unterscheiden kannst, und willst.

            p.p.p.s.
            > Dr. W hat Roger Hodgson einmal getroffen […]

            Fleetwood Mac ? (Davon pfuffel ich mir Manches, beim Verkehrsnachrichten-Hören …)

            Ach so!: Supertramp. (Davon pfuffel ich mir Manches, beim Verkehrsnachrichten-Hören … Besonders Saxophon-Solos.)

          • Frank Wappler schrieb (29.11.2023, 18:05 o’clock):
            > [… Roger Hodgson …] Fleetwood Mac ? […]

            Diese Frage war (und bleibt) leider insofern suboptimal, als das (namensgebende) Mitglied von [[Fleetwood Mac]], an das mich die (oberflächliche Betrachtung) eines Wikipedia-Fotos von [[Roger Hodgson]] erinnerte, unter denjenigen, denen [[Fleetwood Mac]] als Band namentlich kennen, weithin (und somit auch mir) als [[Mick Fleetwood]] bekannt ist.

            Daher ist diese meine Frage ziemlich offensichtlich als rhetorisch/konstruiert zu erkennen; was sie tatsächlich/zugegebenermaßen war (mit Gründen).

            Ob es gegenüber Dr. Webbear (28.11.2023, 11:57 o’clock) zumindest eristisch besser gewesen wäre, wenn ich

            Yes ?

            gefragt hätte ? — würde ich doch recht gerne wissen.

  4. The hunting of the Snark, das ist der Originaltitel von Dodgson, einer phantasievollen Ballade über eine Jagdexpedition. https://de.wikipedia.org/wiki/The_Hunting_of_the_Snark
    John Conway , Dodgson und Miss Steckles, was haben die gemeinsam, sie sind Mathematiker.
    Und was machen Mathematiker in ihrer freien Zeit ? Sie entwerfen Spiele. Conway hat das gemacht, Dodgson hat das gemacht und Miss Steckles schreibt darüber. Mr. Webbaer, Phantasie lässt sich nicht in Zahlen ausdrücken, sie ist das Schlupfloch, das die Mathematiker nutzen.

  5. Katie Steckles wrote (22. Nov 2023):
    > […] A reflector is a structure in [the Game of] Life which is stable, but when a glider approaches it from the right direction, it will absorb it and create a new glider going off in a different direction. […] The smallest known reflector is called the Snark [ https://conwaylife.com/wiki/Snark ], and was discovered in 2013 by Mike Playle – it reflects a glider through 90 degrees, and uses 52 cells (in a box of 23×17 cells). This kind of structure can be used to build oscillators: Imagine pointing four of these at each other, so they pass a glider around between them.

    The linked wiki-page also provides “LiveViewer” presentations of one (type of) Snark reflector in detail, as well as of an oscillator built from four Snark reflectors; each including (only) one glider at once.

    > By tweaking the distance between the reflectors, and the types of reflectors used, we can build oscillators of any large period […] The discovery of the Snark […] show[ed] that a non-trivial oscillator of any period 43 or above can be constructed.

    (I figure that oscillation period 43 is realized if the four-Snarks-oscillator structure shown in the wiki-page is suitably symmetrically populated with four gliders.)

    Also, the “LiveViewer” presentations of the linked wiki-page allow to adjust view parameters. Watching there with “playback speed” set suitably slow I seem to be able to recognize quite a few more distinct states in the evolution of “a Snark reflector having been approached by a glider, from the right direction”, than I’m able to recognize in the “snark.gif” included in the above SciLog article.

    • Frank Wappler wrote (23.11.2023, 17:32 o’clock):
      > […] (I figure that oscillation period 43 is realized if the four-Snarks-oscillator structure shown in the wiki-page is suitably symmetrically populated with four gliders.)

      No — that actually takes eight gliders; as documented (if not conclusively explained) there.

  6. Like real-life creatures, cells in the Game of Life prefer not to be alone; as a result, any cell that is next to either no cells at all or just one other live cell will eventually perish from loneliness.

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +