# Conway’s Game of Life is Omniperiodic

Nico Brown
<EMAIL_ADDRESS>
Maia Karpovich
<EMAIL_ADDRESS>Carson Cheng
<EMAIL_ADDRESS>
Matthias Merzenich
<EMAIL_ADDRESS>
Mitchell Riley
<EMAIL_ADDRESS>Contact author. Tanner Jacobi
<EMAIL_ADDRESS>
David Raucci
<EMAIL_ADDRESS>
(December 5, 2023)

In the theory of cellular automata, an _oscillator_ is a pattern that repeats
itself after a fixed number of generations; that number is called its
_period_. A cellular automaton is _omniperiodic_ if there exist oscillators of
all periods.

Conway’s Game of Life is by far the most famous cellular automaton. David
Buckingham first established a finite bound above which oscillators of every
period could be built by running a signal around a specially constructed
track. For periods below that cutoff, oscillators need to be found
individually.

At the turn of the millennium, only twelve periods remained to be found: 19,
23, 27, 31, 34, 37, 38, 39, 41, 43, 51 and 53. Over the last couple of
decades, these periods were gradually filled in as increasing computer speed
and more clever search techniques were brought to bear on the problem.

The search has finally ended, with the discovery of oscillators having the
final two periods, 19 and 41. A table with oscillators of all periods is
provided below, proving:

######  Theorem.

Life is omniperiodic. ∎

##  1 Conway’s Game of Life

Conway’s Game of Life [14] is a cellular automaton occurring on an infinite
plane of square grid cells, each of which is in one of two states: alive or
dead. The neighbourhood of a cell is the 8 cells that are connected
orthogonally or diagonally to it. At each time step, or generation, the entire
plane changes state according to the following rules:

  * •

If a dead cell has exactly three live neighbours, it becomes alive.

  * •

If an alive cell has exactly two or three live neighbours, it stays alive.
Otherwise, it becomes dead.

These simple rules give rise to complex behavior which has been studied in
great detail over the last 50 years. Starting with a random initial state,
running Life forwards in time typically causes an initial burst of chaotic
activity that settles down into small patterns of alive cells. Two basic
arrangements are the block, a 2×2 grid of alive cells, which does not change;
and the blinker, a 1×3 line of alive cells, which alternates between
horizontal to vertical at each time step. Vastly more complex patterns exist,
both naturally occurring and intentionally engineered. In particular, this
includes working universal constructors [28, §11] and computers [28, §9] [48].

(p1) Block

(p2) Blinker

Glider

Some Life patterns return to their starting configuration after a finite
amount of time. Such patterns are often categorised by their _period_ : the
number of generations after which the state of the pattern repeats. Patterns
that have a period of 1, like the block, are called _still lifes_. Some
patterns, like the blinker, have period 2 or more; these are called
_oscillators_. Others repeat their state but translate in the plane; such
patterns are called _spaceships_. For example, the famous glider has period 4,
but moves 1 cell diagonally in those 4 generations.

The final states of random soups often contain oscillators of period 2 (such
as the blinker), sometimes period 3 (such as the pulsar), and occasionally
even 15 (the pentadecathlon). Oscillators with other periods are much rarer,
and are generally searched for specifically rather than falling out of random
initial states. Nevertheless, it has long been conjectured that oscillators of
_every_ period $p\geq 1$ exist in Life111The period of an oscillator is almost
universally denoted by $p$ but we do not mean that $p$ is always prime, or
that it is somehow sufficient to consider only prime periods.; i.e. that Life
is _omniperiodic_. Determining whether this is the case has been referred to
as an open problem as far back as we have records of hobbyist discussions
[65].

One aspect that makes the problem so intriguing is that omniperodicity has
long been settled for rules extremely similar to Life. For example, if the
rules are changed so that an alive cell also remains alive when it has zero or
one neighbours, omniperiodicity was proven in 1997 [24]. If instead we also
allow four-neighbour cells to survive, the question was settled in 2010 [35].
Both were achieved using “drifter” techniques (which we will be covering
later).

Low-period oscillators in Life, roughly $p\leq 15$, can be found by playing
with patterns by hand or using brute force computer searches. In 1996, David
Buckingham demonstrated [6] using his “Herschel conduits” that one can
construct oscillators with $p\geq 61$ by sending signals around a closed
track; the cutoff for systematically constructing oscillators was later
improved to $p\geq 43$, by Mike Playle’s discovery of the Snark [43].

Periods in the “missing middle”, $15<p<43$, particularly those that are prime,
proved more difficult to find. From 1996 and concluding in July 2023, a
sequence of discoveries using new mechanisms and improved search algorithms
filled in the remaining gaps. The techniques include: stabilizing infinitely
repeating patterns, hassling common active objects, finding oscillating
perturbations of stable background patterns, multiplying the period of low-
period oscillators and finding dependent glider loops. Together, they suffice
to cover all $p<43$, proving that Life is omniperiodic.

##### Acknowledgements

Thank you to Dave Greene, Nathaniel Johnston, Darren Li and Conwaylife.com
forum user ‘praosylen’ for corrections and suggestions, and to Chris Rowett
for the use of his LifeViewer software to depict each pattern. Thank you also
to everyone who has contributed to the omniperiodicity problem over the years
by making new discoveries, proposing and implementing new approaches, and
running the searches that make these discoveries possible. The discoverers of
the first oscillator of each period are listed in the Appendix.

##  2 A History of Oscillator Searches

In the following sections we describe the techniques listed above, in roughly
the chronological order in which they were developed. In the PDF version of
this paper, each image links to a page with the pattern loaded into
LifeViewer, which can be used to simulate the pattern forward in time. There
is no substitute for seeing the patterns in motion, and we encourage the
reader to experiment with any pattern that interests them.

Oscillators are depicted with a colour ramp on the dead cells, fading from
blue to orange the longer the cell has stayed dead. The number of generations
taken to reach orange in each image is matched to the period of the
oscillator, so the colour ramp can be used to roughly gauge where the active
part of each oscillator is moving in the generation it is displayed: away from
the blue region (where it has just been) and towards the orange region (which
it must at some point reach).

An infinite p19 oscillator

We restrict our attention to _finite_ oscillators, because omniperiodicity for
infinite oscillators is nearly trivial. An infinite stream of evenly-spaced
gliders forms an oscillator, repeating when each glider reaches the position
of the next. This gives an easy construction for all periods $p\geq 14$; the
tightest the gliders can be packed without interfering. Oscillators with all
remaining periods $p<14$ were known by the mid-1970s.

###  2.1 Handcrafted Oscillators, Billiard Tables and Hasslers

(p3) Pulsar

(p5) Octagon 2

(p8) Figure eight

(p14) Tumbler

(p15)
Pentadecathlon

The first few oscillators in Life were found through experimentation with
small starting configurations, often evolved by hand on graph paper or
covertly on corporate computers. The block (period 1) and blinker (p2) were
found almost immediately, descending directly from the two triominoes. Other
early oscillators were found from the lucky evolution of simple starting
configurations, such as the pulsar (p3), figure eight (p8), and pentadecathlon
(p15) found by Conway’s team, the tumbler (p14) found by George D. Collins,
Jr., and octagon 2 (p5) found independently by Sol Goodman and Arthur C. Taber
[14, 15, 60].

(p4) Pinwheel

(p6) $rats

(p7) Burloaferimeter

(p10) 42P10.3

(p11) 38P11.1

In early 1970, while working as part of Conway’s group, Simon Norton
discovered a way to construct a class of oscillators that came to be known as
_billiard tables_. A rectangular region in the Life plane can be surrounded by
a boundary of live cells and stabilized from the outside by still lifes. There
is a chance that a configuration within the bounded region will then oscillate
with aid from the boundary walls, interacting with but not destroying them.
Norton used this technique to find pinwheel, the first period-4 oscillator.
Billiard tables need not be restricted to rectangular regions and solid cell
borders: throughout the 1970s Buckingham found billiard tables of varying
structures including $rats (p6), burloaferimeter (p7), and unnamed oscillators
of periods 10 and 11, each the first known oscillator of their period [26].

(p30) queen bee shuttle

Many larger periods are covered by another class of oscillators called
_hasslers_ , which make up a majority of the new-period discoveries in the
21st century. These consist of an active pattern surrounded by objects that
perturb its evolution and cause or allow it to reoccur. The surrounding
objects are called _catalysts_ and are typically still lifes or other, smaller
oscillators. Most hasslers involve active areas that evolve from commonly
occurring patterns, as those are the most likely to reoccur naturally after
being perturbed.

The first hassler used a pattern found by Robert W. April known as the _queen
bee_. After 15 generations, it reappears facing the opposite direction while
leaving behind an extraneous still life known as a _beehive_ , visible on the
left-hand side above. Advancing another 15 generations brings the queen bee
back to its original position while depositing a second beehive, but
subsequent evolution is disrupted when the advancing queen bee collides with
the first beehive. Two queen bees can be positioned such that these extraneous
beehives mutually annihilate, and Bill Gosper used this fact to form the first
period-30 oscillator: a square of eight interacting queen bees [17].

The original form of this eight-fold queen bee oscillator was not recorded.
Shortly after its construction, Richard P. Howell noticed that a properly
placed block annihilates a beehive without itself being destroyed. This gives
the much smaller queen bee shuttle (p30) shown above, with the blocks acting
as catalysts.

Gosper glider gun

The queen bee comprises one half of the famous _Gosper glider gun_ , the first
pattern found that exhibits infinite growth [15]. The two queen bees in this
glider gun interact every 30 generations such that a glider is released from
the mechanism.

(p46) twin bees shuttle

In a similar fashion, a pair of “B-heptominoes” positioned with a certain
spacing flips and reoccurs after 23 generations, leaving some junk behind.
This junk can also be removed by placing blocks, forming the _twin bees
shuttle_ (p46), also found by Bill Gosper (so named for its twin B’s).

(p9) worker bee

(p12) dinner table

(p52) 35P52

While the queen bee and twin bees miraculously reappear without any external
intervention, most hasslers do not work this way. An example is the worker bee
(p9), discovered by Buckingham in 1972 [62], where a line of six live cells
evolves briefly before having its corners perturbed by four copies of a 7-cell
catalyst known as an _eater_. The catalysis involves the corner of the eater
being briefly disturbed while the rest of the still life remains unchanged.
This robust “eating” capability was first noted by researchers at MIT in 1971
[61] and quickly became a valuable tool in the construction of new hasslers,
two more of which are displayed above [63, 26].

Buckingham’s p13

(p32) gourmet

Many other stable patterns can act as catalysts. Buckingham in particular
possessed an uncanny ability to construct complex catalysts by hand. Of note
is the _eater 2_ [5] which catalyzes reactions in a similar way to the eater,
but takes longer to recover. This extended recovery time allows it to catalyze
some reactions that the eater cannot, such as in Buckingham’s p13 oscillator,
the first of its period known. Another early hassler using an unconventional
catalyst is the period-32 gourmet found by Buckingham in 1978 [26], which
rotates a pi-heptomino by 90 degrees every 8 generations.

(p16) Two pre-L hassler

(p18) 117P18

(p36) toad hassler

Catalysts need not be still lifes. Many hasslers are catalyzed by low-period
oscillators that emit _sparks_ — small groups of active cells that are ejected
from the main body of an oscillator before dying off. Such _sparkers_ are
powerful as catalysts because the sparks are free to interact with the active
pattern in many different ways. Because they would die anyway, they do not
need to be restored for the sparker to continue to function. When a sparker is
used as a catalyst, the period of the sparker must divide the period of the
entire oscillator so that the spark appears at the right time during the next
period.

Very few sparkers were known prior to 1989, so hasslers exploiting them were
less common. Above we have displayed three such oscillators, on the generation
just as the spark interacts with the active pattern. Each was the first of its
period known.

(p26) pre-pulsar shuttle

(p28) newshuttle

(p29) pre-pulsar shuttle

A notable class of early hasslers pioneered by Buckingham uses a common
predecessor of the pulsar. The _pre-pulsar_ is an arrangement of two hollow
$3\times 3$ squares that interact in such a way that they duplicate themselves
after 15 generations. Various catalyses can be used to hasten or delay this
reaction, and combined they can be used to create oscillators of many periods.
The three depicted above, all by Buckingham, were the first known oscillators
of their respective periods.

(p23) David Hilbert

The use of computer searches did not foreclose the ability of humans to find
new oscillators by hand through experimentation and intuition. A final hand-
crafted hassler worthy of mention is the first known period-23 oscillator:
this was the 5th last period to be filled. An attempt from 2015 by forum user
“praosylen” was modified by Luka Okanishi in 2019 to be a near-oscillator; the
only defect being that a beehive is pushed away by a one-cell distance [40].
To push the beehive back, a second copy of the near-oscillator is used,
running out-of-phase with the first.

###  2.2 Soup Searches

(p3) jam

(p4) mold

Achim’s p11

As we have seen, one method for finding oscillators is to start with a random
configuration and get lucky. Done on a large scale, these are known as _soup
searches_ , essentially automated versions of the random scribbling that
newcomers to Life perform. A small random starting configuration (i.e., a
_soup_) is chosen, optionally with symmetry, and then run until it stabilises.
The objects that remain in the ash are programmatically separated from one
another and tabulated, resulting in a _census_. With carefully optimised
software, tens of thousands of soups can be tested per second on a standard
computer.

From 1987 to 1988, Achim Flammenkamp wrote the first soup-searching programs,
running soups on a torus — a finite universe that wraps around on its edges.
The period-3 _jam_ and the period-4 _mold_ were discovered this way, spotted
in the ash of soups run on 32×32 toruses. A soup search on symmetrical
configurations yielded the sparking p11 oscillator on the right, which makes
an appearance in Section 2.4.

Rob’s p16

Rich’s p16

(p25) 30P25

Several large censuses have been run since then [13, 41, 27], but by far the
largest is the ongoing Catagolue [20] project run by Adam P. Goucher, having
searched more than 450 trillion soups and tallied more than 12 quadrillion
Life objects since 2015 (at the time of writing). In 2022, the Catagolue
search was connected to the Charity Engine and OpenScienceGrid [45]
distributed computing platforms, significantly boosting the search speed.

Oscillators that are found via soup searches are often spectacularly volatile,
with few cells that remain stable through the entire period. This is in
contrast to the billiard tables and hasslers we have seen, where the majority
of the alive cells are stable, only present to support a small active region.
Soup searches are essentially the only method we have of finding small,
volatile, high-period oscillators.

Above is displayed Rob’s p16 (found by Rob Liston), Rich’s p16 (found by Rich
Holmes) and 30P25 (found by Charity Engine), all through the Catagolue
project.

Merzenich’s p31

Beluchenko’s p37

Beluchenko’s p51

torus [57] by Jason Summers and RandomAgar [39] by Gabriel Nivasch are soup
search programs that attempt to find _agars_ : patterns that are periodic in
space as well as periodic in time. They do so by choosing a symmetry (one of
the wallpaper groups compatible with a square grid222Of the 17 wallpaper
groups, 5 contain a rotation of 120∘ and so cannot be used. Of the 12
remaining, 9 yield distinct symmetries when aligned to the grid orthogonally
and diagonally, so there are 21 possibilities in all.) and size of a
fundamental region, filling the fundamental region with a random initial
configuration, and simulating the finite universe until it becomes periodic.
In some cases, a complete oscillator will occur. The first oscillators with
periods 31, 37 and 51, depicted above, were found in this way using a variant
of RandomAgar written by Nicolay Beluchenko [19, 30, 31].

(p36) 22P36

Raucci’s p38

In other cases the agars do not contain complete oscillators, but external
“fenceposts” can be found to replace the influence of the wraparound at the
edges of the fundamental region, resulting in a standalone oscillator. A
notable oscillator that was found this way is Raucci’s p38: this period was
the fourth last to be filled. The active part of the oscillator was found by
Jason Summers in 2000, as an infinite agar. Only 22 years later, some
appropriate fenceposts were found: a catalyst known as the _traffic stop_.
This catalyst was discovered by a user known pseudonymously as “cvojan”, and
can be seen as one half of a period-36 oscillator found by Noam D. Elkies in
1995. It was then applied by David Raucci to Summers’ period-38 agar—an
excellent example of how much work and collaboration goes into a single
result!

###  2.3 Direct Searches and Drifters

The simplest strategy for searching directly for oscillators is a brute force
search on all states of a fixed size. This quickly becomes unfeasible and so
more refined strategies are needed.

The earliest software capable of searching for oscillators directly was
written by Dean Hickerson in 1989. The program performs a depth-first search
on the state of each cell in a finite grid in every phase of the desired
period, where the rules of Life are enforced forwards and backwards in time.
This puts strong constraints on which choices for each cell are allowed: as
soon as any cell is known to not oscillate at the correct period, that branch
of the search tree can be dropped. This approach is generally effective only
for finding low-period oscillators, and early results were further limited by
the speed of Hickerson’s Apple II. Hickerson described the method in detail,
and several modern search tools are descendants of that original program [58,
56], most notably lifesrc [1] by David Bell.

(p25) 134P25

(p40) B-heptomino shuttle

After the late 1980s, these cell-by-cell search programs allowed more powerful
sparkers to be found. The first known oscillators of periods 25 and 40 use
some of these newer sparkers.

(p17) 54P17.1

The search program dr [23] by Hickerson is similar to these cell-by-cell
search programs, but makes a strong assumption that turns out to be extremely
effective in practice: that the active part of the pattern is a small,
unstable region present on a completely stable background. This could be seen
as a systematic method of hunting for new billiard tables.

The program was originally written to search for signals traveling through
stable _wire_ , after the manual discovery of a signal wire with speed
$2c/3$333In this context, $c$ is the speed of one cell per generation, the
maximum speed attainable by any signal in Life.. The hope was that an _elbow_
could be found, turning a signal 90 degrees. If the repeat time of this elbow
were short enough (i.e. $\leq 19$), this would immediately resolve
omniperiodicity in the affirmative. These searches were not successful, though
there were some near misses [54], including an alternative signal wire with
transmission speed $5c/9$.

The dr program can also identify when it has stumbled on an oscillator.
Typically, these have low periods, but the result can occasionally get into
the high teens and low twenties [25]. The first period-17 oscillator was found
this way by Hickerson. This general strategy of using a backtracking search to
find still lifes with good properties can also be used to produce powerful
catalysts for use in hasslers, as we will see soon.

###  2.4 Period Multipliers

A trivial p12

From oscillators of period $n$ and $m$, we can easily construct a pattern with
period $\operatorname{lcm}(n,m)$ by placing the oscillators in the plane such
that they do not interact. These are _trivial_
period-$\operatorname{lcm}(n,m)$ oscillators, as no cell of the pattern
oscillates at the full period. Above, we show a trivial p12 oscillator
constructed by welding the p3 jam and p4 mold back-to-back.

(p20)

(p21)

(p24)

(p35)

(p42)

Sometimes, however, two oscillators can be placed such that they just barely
interact without destroying either oscillator; such patterns are called _LCM
oscillators_. One way to do this uses sparkers. For example, the first
period-20 oscillator consists of a period-4 oscillator that emits domino
sparks interacting with the period-5 octagon. When the domino spark and the
edge of the octagon 2 are present on the same generation, they interact and
turn on a single cell between the two oscillators. The first oscillators of
periods $20=4\times 5$, $21=3\times 7$, $24=3\times 8$, $33=3\times 11$,
$35=5\times 7$ and $42=6\times 7$ were all found this way.

The above images present the oscillators on the generation before they
interact; the interaction point is visible in orange. These interaction cells
are the only ones that oscillate at the full period.

In fact, this method of period-multiplying could have been used to construct
some periods _earlier_ than their official discovery dates: the requisite
components existed at the time but were never combined. The periods in this
category are 18, 36 and 40. For example, the octagon 2 and the figure eight
may be combined to form a non-trivial oscillator of period 40 using the same
interaction that appears in the period-20 oscillator above.

(p33) 330P33

The $33=11\times 3$ oscillator involves a large sparker on the right, which
was found by Elkies using lifesrc. It was the first known period-3 sparker to
emit a domino spark so isolated from the remainder of the sparker, and has
various other applications in Life.

(p39) 134P39.1

The first period-39 oscillator also multiplies the period of two smaller
oscillators, but uses a different mechanism to do so. The lower part of the
oscillator is Buckingham’s p13 (seen in Section 2.1), which is normally
supported by two stable eater 2s. In 2000, Elkies found a period-3 variant of
the eater 2, such that when the eater 2 catalysis occurs, it toggles the state
of an otherwise stable cell. The period-3 component then toggles the cell
state back, in this case creating an oscillator with period $39=3\times 13$.

(p27) 123P27.1

A third technique is seen in the first known period-27 oscillator. When two
oscillating mechanisms interact, one can cause the other to skip ahead or fall
behind by one or more generations, a phenomenon known as _phase-shifting_. The
first period-27 oscillator, found by Elkies, is a period-9 oscillator with a
small period-7 section attached. When the phases of the mechanisms align in a
certain way, they interact such that the period-7 component skips one
generation.

###  2.5 Signal Loops

(p180) glider loop

(p30) glider loop

(p300) glider loop

Rather than using a perturbation in a still life as a signal in a loop, an
obvious alternative is to use the glider, which propagates itself without any
external intervention. All that is necessary is some method of reflecting a
glider by 90 degrees. Above, we show some glider loops formed by four copies
of the period-30 _buckaroo_ , a variant of the queen bee shuttle that produces
a spark capable of reflecting a glider. On the left, we have the most basic
version: a single glider is reflected four times to return to its starting
position. We can produce oscillators with factors of its period by placing
additional gliders in the loop (as long as the period is still divisible by
30, so that the gliders arrive at each buckaroo when it is in the correct
phase). The pattern will repeat when each glider moves into the position and
state of the next, rather than when one glider goes the entire way around. In
the center pattern we fit 6 gliders into the same loop, producing the minimum
period of 30. The positions of the reflectors are adjustable and by moving the
buckaroos further apart, larger periods can be produced. Combining these two
tricks, an oscillator with period $30n$ can be produced for any $n$. Glider
loops can be constructed using many different glider reflectors, each giving
an infinite family of oscillators.

(p49) glider loop

A notable example is the _bouncer_ , a periodic glider reflector discovered in
the late 90s by Elkies, based on the collision of a glider with a still life
known as a _boat_. A block, an eater, and a spark perturb the reaction such
that it releases another glider and restores the boat. The spark interacts
briefly and only once per glider reflection, so the reaction can work with a
sparker of any sufficiently large period. This was used to form the first
known oscillator of period 49, displayed above, using period-7 sparkers.

This particular loop can be modified to have any larger period that is a
multiple of 7. But there is an obstruction to adjusting it much lower: if the
period is too low, the reflection reaction may not have completed by the time
the next glider arrives! A gap of 22 generations is sufficient for the
reflections to succeed. For reflectors and other mechanisms, this is called
the _minimum repeat time_ : the minimum delay between two inputs such that the
mechanism works as expected both times. In general, for any period $p\geq 22$,
a bouncer-type oscillator can be assembled as long as a suitable sparker is
known. To function as a loop, the period of the sparker used must divide the
overall length of the loop.

####  2.5.1 Herschel Conduits

The Herschel

Besides the glider, a promising choice of active region for forming signal
loops is the _Herschel_ , an active pattern that often appears in the
evolution of other more common sequences, such as the R-pentomino and
B-heptomino. Crucially, the Herschel typically appears a fairly long distance
from the starting point, providing lots of space for catalysts to tame the
remainder of the reaction.

A length 724 Herschel loop

Through the 1990s, many _Herschel conduits_ were found — that is, placements
of catalysts that cleanly restore a Herschel at a different location. In
particular, Buckingham discovered [6] a set of Herschel conduits that can be
used to construct arbitrarily long loops.

Above, we give an example of a Herschel loop built out of two elementary
components: the ‘F117’ conduit which translates a Herschel forwards in 117
generations, and the ‘R64’ conduit, which translates and turns a Herschel to
the right after 64 generations. A Herschel is placed at the input/output
locations of each component; these are not equally spaced as the two types of
component take different durations to traverse. We have used four of each
component, so a single Herschel travels around the loop in $4\times
117+4\times 64=724$ generations. By deleting all but one Herschel, we have an
oscillator with period equal to the full length of the track: 724. With two
evenly spaced Herschels the period is 362, and with four, the period is 181.
This is the lowest we can manage with this conduit: the next smallest factor
of 724 is 181, and there is certainly no space to fit 181 Herschels.

Crucially, the catalysts used in such conduits are all stable, so the length
of the loop is not constrained by the use of periodic sparkers or reflectors.
By constructing different loops and placing Herschels with regular spacings,
oscillators of _all_ sufficiently large periods can be constructed.
Buckingham’s initial set of conduits found in 1996 established that all
periods $p\geq 61$ could be achieved, the bound coming from the minimum repeat
time of the components used. A careful argument that all periods $p\geq 61$
are attainable with Herschel loops is given in [28, §3.6].

Some additional Herschel conduits with lower repeat times were discovered the
following year, and this bound was compressed first to $p\geq 58$ by
Buckingham and Paul Callahan [7], and later to $p\geq 56$ by Dietrich Leithner
using sparkers [33].

####  2.5.2 Stable Reflectors and the Snark

Herschel conduits are limited by their relatively long minimum repeat time and
glider loops are limited by the period of the reflector used. There was a long
held hope that a _stable_ glider reflector could be found that would push the
bound of unknown periods lower still.

In the earliest days of Life, it was known that a stable glider reflector must
exist. This follows as a theoretical consequence of two important ideas.
First, it was argued that _universal computers_ exist [2, §25] [64, 46]. That
is, one can construct a pattern to simulate an arbitrary Turing machine. It
was also argued that _universal constructors_ exist: patterns that can follow
instructions to construct any _glider-synthesisable_ object, that is, any
object that can be created by colliding gliders in some combination. In
particular, when fed the correct instructions, such a constructor is capable
of building both a distant copy of itself, and a distant copy of a universal
computer.

Together, this implies the existence of a stable reflector; the argument goes
as follows [7, §4]. The incoming glider hits a cluster of still lifes,
destroying them and spawning additional gliders. These gliders can be
redirected through additional destructive collisions, and with sufficient
time, an almost arbitrary flotilla of gliders can be produced. The flotilla
chosen is one that synthesises a universal computer/constructor combination as
described above, together with a program that instructs the computer to: 1)
Emit a glider at 90 degrees from the input; 2) Reconstruct the initial
configuration of still lifes; and, 3) Cleanly self-destruct the universal
computer/constructor. This program can be encoded in the position of a single
distant still life to be read by the computer, to avoid any concerns about the
complexity of having the computer reconstruct a description of itself.

Given a stable glider reflector, we can build a loop from 8 of these
reflectors444We use 8 reflectors rather than 4 to avoid any complications that
would arise if the delay imposed on the glider by the reflector were a
multiple of 4. whose length can be any sufficiently large multiple of 8.
Placing gliders in the loop at regular intervals, we can achieve any
sufficiently large period. This method is massively inefficient: we will see
next that very compact stable glider reflectors exist. Still, it was known
from the earliest days that at most finitely many oscillator periods could
fail to exist; all that remains is stamp collecting.

These early arguments were not constructive, and it was only much later that
explicit Turing machines [48, 18] and universal _construction arms_ [28,
§11.1] [11] were created. An example of a large, universal constructor-based
oscillator has been constructed by forum user Goldtiger997 [16].

The first explicit stable glider reflector was constructed by Callahan [22],
where the chaos from the collision of a glider with a bait object is turned
into a Herschel, and Herschel conduits are used to emit another glider and
restore the original collision site. The repeat time was quickly reduced from
4840 down to 850 generations, and conduit-based constructions by others
eventually reached 444. This was still far too high to construct oscillators
with new periods.

The Snark

In 2013, Mike Playle used his Bellman [42, 44] catalyst search program to
discover the _Snark_ , the first small, stable 90-degree glider reflector. The
glider hits a block creating a symmetrical active region known as a _honey
farm_ , which is shaped by three nearby stable catalysts so as to produce an
output glider perpendicular to the input and restore the block, without going
through a Herschel as an intermediate stage.

(p43) Snark loop

The Snark’s minimum repeat time is 43 generations. As it is a stable
reflector, it can also reflect at any larger spacing, giving a simple and
uniform construction for oscillators of all periods $p\geq 43$. Glider loops
using the Snark provided the first known oscillators with periods 43 and 53
[36]. So that our presentation of omniperiodicity is completely self-
contained, we give a proof that all periods $p\geq 43$ are indeed attainable.

######  Theorem.

For any $p\geq 43$, a Snark loop with period $p$ can be constructed.

###### Proof.

Place four Snarks in a rectangular configuration, as in the case of the
period-43 oscillator above.

This produces a glider path in the shape of a diagonal rectangle, with a width
of $n$ diagonals and a height of $m$ diagonals. The spacings $n$ and $m$ must
be large enough so that the Snarks do not destabilize each other ($n,m>13$ is
sufficient). The time taken for one glider to traverse this loop is given by
the perimeter of the loop, $2n+2m$, divided by the speed of the glider, $1/4$,
plus four times the 2-generation delay imposed by each Snark reflection. In
all, this is $4\times(2n+2m)+8=8(n+m+1)$.

Inserting 8 equally spaced gliders into this loop will create an oscillator
with a period $p=n+m+1$, so long as $p\geq 43$. Thus, for any $p\geq 43$ there
is a Snark loop with period $p$ taking, for concreteness,
$n=\lfloor(p-1)/2\rfloor$ and $m=\lceil(p-1)/2\rceil$. ∎

###  2.6 Catalyst Searches

(p19) cribbage

(p34) 74P34

Just as dr can be seen as a systematic search for billiard tables, we can also
attempt a systematic search for hasslers. Hasslers have three components: the
active pattern, the catalysts, and the catalyst placements. The active regions
that have the best chance of forming hasslers are the ones that occur most
often naturally: after being perturbed, they have the best chance of reforming
in the correct position. Simon Ekström [12] performed a census of 10 million
small active patterns, and the resulting list of the most common patterns
forms the basis of many of the following searches.

Similarly, the most useful catalysts are the ones that have the best chance of
perturbing an active pattern and surviving. These evaluations were run by
Dongook Lee [32], and with a more expansive list by Mitchell Riley [50],
resulting in a shortlist of the catalysts with the most potential to produce
hasslers.

Finally, these catalysts need to be placed in the hopes that the active region
will reform. Like drifter searches, each result of a catalyst-based search is
a roll of the dice: there is no way of specifying in advance which period you
would like to find.

One approach is to simply brute-force every possible position of the
catalysts: this is the approach taken by Michael Simkin’s CatForce [55]. Such
brute-force searches are only feasible for small numbers of catalysts chosen
from a small number of options. Instead, we can place catalysts ahead of the
reaction “just in time” to perturb it, and bail out of testing a configuration
if the catalysis fails or one of the catalysts is later destroyed by the
active pattern. This can naturally be written as a depth-first search through
catalyst positions, and is the approach taken by the ptbsearch [8] and
Catalyst [38] programs.

A second improvement is searching specifically for symmetrical hasslers.
Allowing symmetry greatly enlarges the available search space, more than
simply searching for hasslers with an additional catalyst would, as there are
far more ways for copies of the active region to interact with one another
than there are ways to interact with an additional catalyst successfully.

A search script by Raucci [47] incorporates both of these improvements,
focusing on oscillators supported by sparks. Rather than placing entire
catalysts, an isolated spark is placed to interact with the active region. If
the active region then reoccurs, the “partial” oscillator can sometimes be
completed to a true oscillator by placing sparkers of an appropriate period.

Symmetric CatForce [49] is a modified version of (asymmetric) CatForce that
also incorporates these ideas, using a fast Life-step algorithm [51] by Tomas
Rokicki. The first known oscillators of periods 34 and 19 were found by Riley
using Symmetric CatForce, both coincidentally having 2-fold rotational
symmetry.

####  2.6.1 Dependent Reflectors

(p31) dependent glider loop

Among hasslers, a large, fruitful, and tractable search space exists with
_dependent glider reflectors_. These reflectors are much like traditional
glider reflectors such as the Snark, but are dependent on a regularly-spaced
stream of input gliders. Any interruption or disturbance in the glider stream
destroys the reflector. There is no assumption that a glider will strike a
bait object to initiate the reflection sequence. Instead, the glider will
often strike an actively-evolving pattern in the dependent reflector, and this
disturbed pattern will be guided back to its original location while emitting
another glider.

This is demonstrated above in a period-31 dependent glider loop discovered by
Merzenich. The honey farm interacts with the eater in precisely the same way
as used in the Snark reflector, emitting a glider. Rather than simply settling
down to a block, the active region interacts with the incoming glider and
outermost block to reform a honey farm directly.

Dependent reflectors are far easier to find than stable reflectors. Since
evolving active regions both 1) are larger than the still lifes useful in
traditional glider reflectors and 2) have more than one phase at which the
glider can strike them, there are many more available possibilities for the
initial glider collision. As an extreme example, a glider striking a block has
only three distinct reactions that could lead to a stable reflector — one
yielding a pi-heptomino, one a honey farm, and one that annihilates the block
and glider in 28 generations. Meanwhile, dependent reflector targets can
easily exceed 100 distinct useful interactions.

A search for dependent reflectors can be seen as a hassler search where the
incoming glider is treated as a “catalyst” that does not have to recover. In
this way, dependent reflectors enlarge the available search space in much the
same way as searching with symmetry. Of course, to actually be a “reflector”,
the reaction has to at some point emit another glider.

(p41) 204P41

LocalForce [3] by Nico Brown is a variant of CatForce that supports placing
gliders as catalysts, and it quickly yielded numerous dependent reflectors
based on the honey-farm reaction. Searches with other active regions yielded
numerous partial results where the active region repeated with period 41, but
did not release the glider required to act as a dependent reflector. While
these partials did not create gliders, several created sparks. Upon further
modifying LocalForce to search for interactions involving these sparks, a
period-41 dependent reflector combining two active regions was quickly found,
yielding a period-41 loop and proving that Life is omniperiodic.

###  2.7 Future

The omniperiodicity problem has served as a rallying point for the Life
community, leading to the creation of the many tools and programs we have
detailed above.

However, there are still vast gaps in our knowledge about what is possible in
Life [37]. Perhaps the most significant is which of the theoretically
possible555No pattern can propagate faster than the ‘speed of light’ $c$, the
distance of one cell per generation. For spaceships moving through empty
space, the limits are much lower: $c/2$ for orthogonal motion and $c/4$ for
diagonal motion [28, §4.5]. _spaceship_ velocities can be realised. Recall
that a spaceship is a periodic pattern that reoccurs at some translation from
its original position; one might think of oscillators as stationary
spaceships. Similarly to oscillators, there are non-constructive arguments
that show that all sufficiently slow spaceship velocities are attainable, but
low-period spaceships with new velocities are exceptionally difficult to find.
A notable example is Sir Robin [21], the first discovered elementary spaceship
with a non-orthogonal and non-diagonal velocity.

Another class of periodic objects is _glider guns_ ; patterns that release
gliders at regular intervals. Glider guns are known that produce glider
streams of all possible666Glider guns must have a period $p\geq 14$ for the
gliders to not interfere with each other. output periods. However, for a
handful of periods, no “true-period” gun exists: the gun does not have the
same period as the output stream. For example, the known gun that produces a
period-15 glider stream consists of the period-30 Gosper glider gun together
with a second period-30 mechanism that inserts a glider into each gap. At the
time of writing, the remaining true-period guns to be found have period
$14\leq p\leq 19$, and $p=23,26,29,31,35,38,39,47$ and $53$.

(p28) newshuttle

(p28) lcm(4, 14) oscillator

Even without leaving the search for oscillators, there is still much to do.
For example, there is interest in finding oscillators with as low a population
as possible, so-called Smallest Known Oscillators of Period $p$ [59, 34]. In
the above sections we have generally shown the first known oscillator of each
period, but most are no longer the smallest. For example, the period-28
newshuttle is over 6 times as large as a $\operatorname{lcm}(4,14)$
oscillator, the smallest known period-28 oscillator at the time of writing.

The oscillator hunt continues if we add criteria that the oscillators must
satisfy. Indeed, the rules have already changed at least once as, in the past,
LCM oscillators were considered “too boring to count” as filling a period.
This is just a matter of aesthetics, but those worried about the
interestingness of oscillators can still be satisfied: at least one non-LCM
oscillator exists for each period first found using an LCM oscillator, so what
one might call _omni-interesting-periodicity_ holds.

(p2) phoenix

statorless p5

A class of oscillators for which we do not have all periods is _strictly
volatile_ oscillators: patterns where every cell oscillates at the full
period. The vast majority of oscillators we have seen fail this requirement:
of all the oscillators displayed in this document, only figure eight, tumbler,
pentadecathlon and Rob’s p16 are strictly volatile. Brown [4] gives a
systematic construction for strictly volatile oscillators with all periods
$p\geq 949$, using opposing flotillae of spaceships to construct each other.
Below that, very little is known; even period-7 is unresolved. Above we have
displayed a strictly volatile period-2 oscillator known to the MIT group in
the early 70s, and the only known strictly volatile period-5 oscillator,
discovered by Josh Ball in 2016. Most search techniques we have seen are
useless here. For example, catalyst searches and Herschel conduits rely on
stable catalysts, and drifter searches typically result in large stable
supports.

The use of constraint solvers is an under-explored search technique. The
existence of an oscillator of some size and period can be expressed as a
Boolean satisfiability problem and passed to a standard SAT solver [29, p.
201–204] [10]. The periods for which this is currently effective are still
fairly low, however. Constraint solvers have helped resolve other questions
about Life, such as the “generalized grandfather problem” [52], the maximum-
density still life problem [9], and the computational universality of
determining whether a pattern can be reversed even a single step [53].

Life’s work is never done!

##  First Known Oscillators of All Periods

Period | Name | Discoverer | Year
---|---|---|---
1 | block | John H. Conway | 1969
2 | blinker | John H. Conway | 1969
3 | pulsar | John H. Conway | 1970
4 | pinwheel | Simon Norton | 1970
5 | octagon 2 | Sol Goodman, Arthur C. Taber | 1971
6 | $rats | David Buckingham | 1972
7 | burloaferimeter | David Buckingham | 1972
8 | figure eight | Simon Norton | 1970
9 | worker bee | David Buckingham | 1972
10 | 42P10.3 | David Buckingham |  $\leq$1976
11 | 38P11.1 | David Buckingham | 1977
12 | dinner table | Robert T. Wainwright | 1972
13 | Buckingham’s p13 | David Buckingham | 1976
14 | tumbler | George D. Collins, Jr. | 1970
15 | pentadecathlon | John H. Conway | 1970
16 | two pre-L hassler | Robert T. Wainwright | 1983
17 | 54P17.1 | Dean Hickerson | 1997
18 | 117P18 | David Buckingham |  $\leq$1991
19 | cribbage | Mitchell Riley | 2023
20 |  $\operatorname{lcm}(4,5)$ oscillator | ? |  $\leq$1992
21 |  $\operatorname{lcm}(3,7)$ oscillator | ? |  $\leq$1992
22 | 168P22.1 | Noam D. Elkies | 1997
23 | David Hilbert | Luka Okanishi, praosylen | 2019
24 |  $\operatorname{lcm}(3,8)$ oscillator | ? |  $\leq$1992
25 | 134P25 | Noam D. Elkies | 1994
26 | p26 pre-pulsar shuttle | David Buckingham | 1983
27 | 123P27.1 | Noam D. Elkies | 2002
28 | newshuttle | David Buckingham | 1973
29 | p29 pre-pulsar shuttle | David Buckingham | 1980
30 | queen bee shuttle | Bill Gosper, Robert W. April | 1970
31 | Merzenich’s p31 | Matthias Merzenich | 2010
32 | gourmet | David Buckingham | 1978
33 | 258P3 on Achim’s p11 | Noam D. Elkies, Achim Flammenkamp | 1997
34 | 74P34 | Mitchell Riley | 2022
35 | toaster on 44P7.2 | Dean Hickerson, David Buckingham |  $\leq$1992
36 | p36 toad hassler | Robert T. Wainwright | 1984
37 | Beluchenko’s p37 | Nicolay Beluchenko | 2009
38 | Raucci’s p38 | David Raucci | 2022
39 | 134P39.1 | Noam D. Elkies, David Buckingham | 2000
40 | p40 B-heptomino shuttle | David Buckingham |  $\leq$1991
41 | 204P41 | Nico Brown | 2023
42 | unix on 44P7.2 | ? |  $\leq$1992
$\geq$43 | Snark loop | Mike Playle | 2013
44 | p44 pi-heptomino hassler | David Buckingham | 1992
45 | pentadecathlon on snacker | Mark Niemiec, John H. Conway |  $\leq$1992
46 | twin bees shuttle | Bill Gosper | 1971
47 | p47 pre-pulsar shuttle | David Buckingham | 1982
48 |  $\operatorname{lcm}(3,16)$ oscillator | Bill Gosper, Achim Flammenkamp | 1994
49 | p49 glider loop | Noam D. Elkies | 1999
$50+40n$ | p$(50+40n)$ glider shuttle | Dean Hickerson | 1992
51 | Beluchenko’s p51 | Nicolay Beluchenko | 2009
52 | lumps of muck hassler | David Buckingham | 1977
54 | p54 shuttle | David Buckingham |  $\leq$1976
55 | p55 pre-pulsar hassler | David Buckingham | 1986
56 | p56 B-heptomino shuttle | David Buckingham |  $\leq$1991
57 | p57 Herschel loop | Dietrich Leithner | 1997
58 | p58 toadsucker | Bill Gosper, Mark Niemiec | 1994
59 | p59 Herschel loop | David Buckingham | 1997
$60+120n$ | p60 glider shuttle | ? |  $\leq$1971
$\geq$61 | Herschel loops | David Buckingham | 1996
$66+24n$ | p$(66+24n)$ glider shuttle | Robert T. Wainwright | 1984
72 | R-pentomino hassler | Robert T. Wainwright | 1990
$75+120n$ | 6 bits | Robert T. Wainwright | 1984
80 |  $\operatorname{lcm}(5,16)$ oscillator | Dean Hickerson, Bill Gosper | 1994
84 | pi orbital | Noam Elkies | 1995
87 | $\operatorname{lcm}(3,29)$ oscillator | Bill Gosper | 1994
$44n$ | p$44n$ glider loop | David Buckingham | 1992
$30n$ | p$30n$ glider loop | ? |  $\leq$1973
$46n$ | p$46n$ glider loop | Bill Gosper | 1971
$94n$ | p$94n$ glider loop | Dean Hickerson | 1990
96 | p96 Hans Leo hassler | Noam D. Elkies | 1995
100 | centinal | Bill Gosper |  $\leq$1987
102 | p$(102+18n)$ traffic jam | Dean Hickerson | 1994
$100+4n$ | p$(100+4n)$ traffic jam | Bill Gosper | 1994
105 | pentadecathlon on 44P7.2 | ? |  $\leq$1992
108 | p108 toad hassler | David Buckingham |  $\leq$1991
$100+10n$ | p$(100+10n)$ traffic jam | Bill Gosper | 1994
116 | $\operatorname{lcm}(4,29)$ oscillator | Bill Gosper | 1994
124 | p124 lumps of muck hassler | Dean Hickerson | 1994
125 | p$25n$ glider loop | Noam D. Elkies | 1996
126 | p$(102+6n)$ traffic jam | Noam D. Elkies |  $\leq$1996
128 | p128 Herschel loop | David Buckingham | 1991
$135+120n$ | p$(135+120n)$ glider shuttle | Bill Gosper | 1989
$136+8n$ | p$(136+8n)$ Herschel loop | David Buckingham | 1991
$144+72n$ | p$(144+72n)$ gunstar | David Buckingham | 1990
145 | $\operatorname{lcm}(5,29)$ oscillator | Bill Gosper | 1994
$150+3n$ | p$(150+3n)$ Herschel loop | David Buckingham | 1991
$150+5n$ | p$(150+5n)$ Herschel loop | Dean Hickerson, David Buckingham | 1992
$152+4n$ | p$(152+4n)$ Herschel loop | David Buckingham | 1991
$165+120n$ | p$(165+120n)$ glider shuttle | Robert T. Wainwright |  $\leq$1989
$100n$ | p$100n$ glider loop | Bill Gosper |  $\leq$1987
$230+40n$ | p$(230+40n)$ glider shuttle | Dean Hickerson | 1992
$240n$ | p$240n$ glider loop | John H. Conway | 1970
246 |  pinball variant | Dean Hickerson | 1992
256 | p256 Herschel loop | David Buckingham | 1991
$270+24n$ | pinball | Dean Hickerson | 1989
329 |  $\operatorname{lcm}(7,47)$ oscillator | Dean Hickerson, David Buckingham |  $\leq$1992
$856n$ | p$856n$ glider loop | David Buckingham | 1991

For the oscillators whose discovery year is marked with $\leq$, the exact
discovery date was not recorded.

##  Gallery

On the right we provide the patterns in RLE format, a compact representation
that can be pasted into almost any Life software (for example, Golly or
LifeViewer).

(p1) Block
x = 2, y = 2, rule = B3/S23
2o$2o!

(p2) Blinker
x = 3, y = 1, rule = B3/S23
3o!

(p3) Pulsar
x = 13, y = 13, rule = B3/S23
2b3o3b3o2$o4bobo4bo$o4bobo4bo$o4bobo4bo$2b3o3b3o2$2b3o3b3o$o4bobo4bo$o
4bobo4bo$o4bobo4bo2$2b3o3b3o!

(p4) Pinwheel
x = 12, y = 12, rule = B3/S23
6b2o$6b2o2$4b4o$2obo2bobo$2obobo2bo$3bo3b2ob2o$3bo4bob2o$4b4o2$4b2o$4b 2o!

(p5) Octagon 2
x = 8, y = 8, rule = B3/S23 3b2o$2bo2bo$bo4bo$o6bo$o6bo$bo4bo$2bo2bo$3b2o!

(p6) $rats
x = 12, y = 11, rule = B3/S23
5b2o$6bo$4bo$2obob4o$2obo5bobo$3bo2b3ob2o$3bo4bo$4b3obo$7bo$6bo$6b2o!

(p7) Burloaferimeter
x = 10, y = 11, rule = B3/S23
4b2o$5bo$4bo$3bob3o$3bobo2bo$2obo3bobo$2obobo2bo$4b4o2$4b2o$4b2o!

(p8) Figure eight
x = 6, y = 6, rule = B3/S23
3o$3o$3o$3b3o$3b3o$3b3o!

(p9) Worker bee
x = 16, y = 11, rule = B3/S23
2o12b2o$bo12bo$bobo8bobo$2b2o8b2o2$5b6o2$2b2o8b2o$bobo8bobo$bo12bo$2o 12b2o!

(p10) 42P10.3
x = 13, y = 13, rule = B3/S23
6b2o$6b2o2$4b4o$3bo4bo$o2b5obo$3o6bo$3bo3bobob2o$2bo2bo4bobo$2bob2ob3o
$3bo2bo$4bo2bo$5b2o!

(p11) 38P11.1
x = 12, y = 12, rule = B3/S23
2b2ob2o$3bobobo$3bo4bo$2obo5bo$2obo6bo$3bobo5bo$3bob2o3b2o$4bo$5b7o$11b
o$7b2o$7b2o!

(p12) Dinner table
x = 13, y = 13, rule = B3/S23
bo$b3o7b2o$4bo6bo$3b2o4bobo$9b2o2$5b3o$5b3o$2b2o$bobo4b2o$bo6bo$2o7b3o$11bo!

(p13) Buckingham’s p13
x = 25, y = 15, rule = B3/S23
4bo15bo$3bobo13bobo$3bobo13bobo$b3ob2o11b2ob3o$o23bo$b3ob2o11b2ob3o$3b
ob2o11b2obo$10bo3bo$11bobo$10b2ob2o$8bo2bobo2bo$7bobobobobobo$7b2o2bo
bo2b2o$11bobo$12bo!

(p14) Tumbler
x = 7, y = 6, rule = B3/S23
2o3b2o$obobobo$obobobo$2bobo$b2ob2o$b2ob2o!

(p15) Pentadecathlon
x = 10, y = 3, rule = B3/S23
2bo4bo$2ob4ob2o$2bo4bo!

(p16) Two pre-L hassler
x = 24, y = 16, rule = B3/S23
4b2o12b2o$4o4b2o4b2o4b4o$3ob2o2b2o4b2o2b2ob3o$5bo12bo2$13b2o$13b2o$13b
3o$8b3o$9b2o$9b2o2$5bo12bo$3ob2o2b2o4b2o2b2ob3o$4o4b2o4b2o4b4o$4b2o12b 2o!

(p17) 54P17.1
x = 15, y = 13, rule = B3/S23
5bo$4bobo$4bobo3b2o$b2obob2o3bo$2bobo6bob2o$o2bob2ob2obo2bo$2obobobo2b
obo$3bob2ob2o2b2o$3bobo3bobo$4b2obobobo$6bobobo$6bobo$7b2o!

(p18) 117P18
x = 39, y = 30, rule = B3/S23
37b2o$8b2o27bo$9bo25bobo$9bobo23b2o$10b2o14bo4bo$15bo4bo3b2ob4ob2o$13b
2ob4ob2o3bo4bo$15bo4bo14b2o$10b2o23bobo$9bobo25bo$9bo27b2o$8b2o$23b2o
$18b3o2b2o$18bo$18b2o$14b2o$14b2o$29b2o$2o27bo$bo25bobo$bobo23b2o$2b2o
14bo4bo$7bo4bo3b2ob4ob2o$5b2ob4ob2o3bo4bo$7bo4bo14b2o$2b2o23bobo$bobo
25bo$bo27b2o$2o!

(p19) Cribbage
x = 32, y = 21, rule = B3/S23
4b2o$4bo$b2obo10bo$bo2b2o9b3o$3bo2bo11bo$bob4o10b2o$obo$o2b4o12b3o$b2o
3bo11bo3bo6b2o$3b2o5b3o4bo5bo4bobo$3bo5bo3bo4bo3bo5bo$bobo4bo5bo4b3o5b
2o$b2o6bo3bo11bo3b2o$10b3o12b4o2bo$29bobo$13b2o10b4obo$13bo11bo2bo$14b
3o9b2o2bo$16bo10bob2o$27bo$26b2o!

(p20) octagon on HW emulator
x = 16, y = 16, rule = B3/S23
3bo2bo$3bo2bo$b2ob2ob2o$3bo2bo$3bo2bo$b2ob2ob2o$3bo2bo$3bo2bo2$7b2o$2b
2obo4bob2o$2bo10bo$3b2o6b2o$3o2b6o2b3o$o2bo8bo2bo$b2o10b2o!

(p21) jam on 44P7.2
x = 16, y = 17, rule = B3/S23
10b2o$4bo4bo2bo$3bobo3bobo$3bobo4bo3b2o$2obob2o4b2obo$ob2o4bo3bo$4b3ob
o3bo$4bo$5b3o2b2o$8bo$5b2obobobo$5b2obobob3o$9b2o4bo$11b4o$11bo$12bo$ 11b2o!

(p22) 168P22.1
x = 33, y = 23, rule = B3/S23
12b2o5b2o$7b2o3bo7bo3b2o$6bobo4bo5bo4bobo$8bob3obo3bob3obo$5b2obobo3b
o3bo3bobob2o$8bo5bobobo5bo$7bobo2b2obobob2o2bobo$8bo3bo2bobo2bo3bo$4b
2o8b2ob2o8b2o$2o2bo23bo2b2o$obobo5b3o7b3o5bobobo$2bob2o4bobo7bobo4b2o
bo$obobo5b3o7b3o5bobobo$2o2bo23bo2b2o$4b2o8b2ob2o8b2o$8bo3bo2bobo2bo3b
o$7bobo2b2obobob2o2bobo$8bo5bobobo5bo$5b2obobo3bo3bo3bobob2o$8bob3obo
3bob3obo$6bobo4bo5bo4bobo$7b2o3bo7bo3b2o$12b2o5b2o!

(p23) David Hilbert
x = 33, y = 26, rule = B3/S23
7b2o15b2o$8bo15bo$6bo19bo$6b5o11b5o$10bo11bo$4b4o16b5o$4bo2bo17bo2bo$
7bo2bo14b2o$7bo3bo12b3o$7bo3bo2b2ob2o5b2o$8bo2b2ob2ob2o5b2o$10bo12bo$
8b2o$7b3o13bo$3b2o2b3o6b2o4bobo3b2o$3bo11bo2bo3bobo4bo$2obo12b2o4b3o4b
ob2o$ob2ob2o19b2ob2obo$5bo21bo$5bobo17bobo$6b2o17b2o$10bo11bo$6b5o11b
5o$6bo19bo$8bo15bo$7b2o15b2o!

(p24) pulsar on figure eight
x = 26, y = 15, rule = B3/S23
4bo5bo$4bo5bo7b2o$4b2o3b2o$16bo3bo$3o2b2ob2o2b3obo4bo$2bobobobobobo5bo
bobo$4b2o3b2o8bobobo$20bo4bo$4b2o3b2o10bo3bo$2bobobobobobo$3o2b2ob2o2b
3o7b2o2$4b2o3b2o$4bo5bo$4bo5bo!

(p25) 134P25
x = 23, y = 35, rule = B3/S23
11b2o$7b2o2bo$6bo2bobo$2b2obob3ob2o$2bob2obobobo$13bo$3b4obob3obo$2bo
3b2ob2o3bo$3b3ob3ob3o$5bo5bo7bo$17b3o$6bo3bo5bo$8bo7b2o$2o$bo$bobo9b3o
$2b2o9bobo$7b3o3b3o$7bobo9b2o$7b3o9bobo$21bo$21b2o$5b2o7bo$6bo5bo3bo$
3b3o$3bo7bo5bo$9b3ob3ob3o$8bo3b2ob2o3bo$8bob3obob4o$9bo$11bobobob2obo$
10b2ob3obob2o$11bobo2bo$11bo2b2o$10b2o!

(p26) p26 pre-pulsar shuttle
x = 39, y = 39, rule = B3/S23
16b2o3b2o$15bo2bobo2bo$11b2o3b2o3b2o3b2o$11bo15bo$8b2obo15bob2o$7bobo
b2o13b2obobo$7bobo5b3o3b3o5bobo$5b2o2bo5bobo3bobo5bo2b2o$4bo4b2o4b3o3b
3o4b2o4bo$4b5o21b5o$8bo21bo$2b4o27b4o$2bo2bo27bo2bo2$16b2o3b2o$bo4b3o
8bo3bo8b3o4bo$obo3bobo5bo9bo5bobo3bobo$obo3b3o5b2o7b2o5b3o3bobo$bo35b
o2$bo35bo$obo3b3o5b2o7b2o5b3o3bobo$obo3bobo5bo9bo5bobo3bobo$bo4b3o8bo
3bo8b3o4bo$16b2o3b2o2$2bo2bo27bo2bo$2b4o27b4o$8bo21bo$4b5o21b5o$4bo4b
2o4b3o3b3o4b2o4bo$5b2o2bo5bobo3bobo5bo2b2o$7bobo5b3o3b3o5bobo$7bobob2o
13b2obobo$8b2obo15bob2o$11bo15bo$11b2o3b2o3b2o3b2o$15bo2bobo2bo$16b2o 3b2o!

(p27) 123P27.1
x = 20, y = 22, rule = B3/S23
b2ob2o$2bobobob2o$bo4bobo$ob4o4bo$o4bo3b4obo$b4o3bo4b2o$3bo4b4o3b2o$5b
obo4b2o3bo$4b2obo2b2o2b2obo$3bo3bobo2bobobo$4b3o2b2obo6bo$7b2o3bo2b5o$
6bo2bob2obobo$5bob2o3bo2bo2b2o$6bo2b2o3bobo2bo$7b2o3bobob2o$9b4obobo$
9bo2bobobo$10b5ob2o$15bo2bo$9bob4o2b2o$9b2obo!

(p28) newshuttle
x = 51, y = 51, rule = B3/S23
26b2o$20bo3bo2bo2bo$18b3o3b3o3b3o$8b2o7bo15bo7b2o$9bo7b2o5b3o5b2o7bo$
9bobo11bo3bo11bobo$10b2o11b2ob2o11b2o2$3bo43bo$3b3o39b3o$6bo7b3o17b3o
7bo$5b2o7bobo17bobo7b2o$14b3o3b3o5b3o3b3o$20bobo5bobo$10b3o7b3o5b3o7b
3o$10bobo25bobo$10b3o25b3o$3b2o18b2ob2o18b2o$2bobo18bo3bo18bobo$2bo21b
3o21bo$b2o9b3o11bobo7b3o9b2o$12bobo12b2o7bobo$12b3o5b2o14b3o$2o3b2o10b
2o2bo10b2o10b2o$obobobo10bob2o10bobo10bobob2o$2bobo14bo11bo14bobo$b2ob
obo10bobo10b2obo10bobobobo$5b2o10b2o10bo2b2o10b2o3b2o$12b3o14b2o5b3o$
12bobo7b2o12bobo$b2o9b3o7bobo11b3o9b2o$2bo21b3o21bo$2bobo18bo3bo18bobo
$3b2o18b2ob2o18b2o$10b3o25b3o$10bobo25bobo$10b3o7b3o5b3o7b3o$20bobo5bo
bo$14b3o3b3o5b3o3b3o$5b2o7bobo17bobo7b2o$6bo7b3o17b3o7bo$3b3o39b3o$3bo
43bo2$10b2o11b2ob2o11b2o$9bobo11bo3bo11bobo$9bo7b2o5b3o5b2o7bo$8b2o7bo
15bo7b2o$18b3o3b3o3b3o$20bo2bo2bo3bo$23b2o!

(p29) p29 pre-pulsar shuttle
x = 28, y = 28, rule = B3/S23
15bo$13b3o$12bo$12b2o2$bo$obo6b3o$bo7bobo3b2o$9b3o3b2o3$19b2o$9b3o7b2o
5b2o$bo7bobo14bo$obo6b3o12bobo$bo22b2o$13b3o3b3o$13bobo3bobo$13b3o3b3o
7$13bo7bo$12bobo5bobo$13bo7bo!

(p30) queen bee shuttle
x = 7, y = 22, rule = B3/S23
9b2o$9bobo$4b2o6bo7b2o$2obo2bo2bo2bo7b2o$2o2b2o6bo$9bobo$9b2o!

(p31) Merzenich’s p31
x = 24, y = 13, rule = B3/S23
7b2obo2bob2o$2o4bo2bo4bo2bo4b2o$2o5bobo4bobo5b2o$8bo6bo6$8bo6bo$2o5bob
o4bobo5b2o$2o4bo2bo4bo2bo4b2o$7b2obo2bob2o!

(p32) gourmet
x = 20, y = 20, rule = B3/S23
10b2o$10bo$4b2ob2obo4b2o$2bo2bobobo5bo$2b2o4bo8bo$16b2o2$16b2o$o9b3o2b
obo$3o7bobo3bo$3bo6bobo4b3o$2bobo14bo$2b2o2$2b2o$2bo8bo4b2o$4bo5bobob
o2bo$3b2o4bob2ob2o$9bo$8b2o!

(p33) 258P3 on Achim’s p11
x = 31, y = 49, rule = B3/S23
19b2o$19b2o$14bo10bo$13bobo8bobo$12bo2bo3b2o3bo2bo$11bo6b4o6bo$12b2o4b
o2bo4b2o3$14b2o8b2o$9b2o2b2o10b2o2b2o$9b2o2b2o10b2o2b2o$14b2o8b2o3$12b
2o4bo2bo4b2o$11bo6b4o6bo$12bo2bo3b2o3bo2bo$13bobo8bobo$14bo10bo$19b2o$
14bo4b2o3$3bo3bobob6obobo3bo$2bob2obo2bobo2bobo2bob2obo$2bo7b2o4b2o7bo
$b2o2bo3bo2b4o2bo3bo2b2o$o2b6ob2o4b2ob6o2bo$2o6b2ob6ob2o6b2o$2b2obo16b
ob2o$2o2bo8b2o8bo2b2o$bobo2b3o3bo2bo3b3o2bobo$o2b3o5b2o2b2o5b3o2bo$b2o
3bob2obo4bob2obo3b2o$2bobo2bob3o4b3obo2bobo$2bob2obo3b6o3bob2obo$b2o2b
obobobo4bobobobo2b2o$o2bo7b6o7bo2bo$b2o3bo14bo3b2o$5bo3b4o2b4o3bo$4bob
2obo2bo2bo2bob2obo$4bo2b3o8b3o2bo$b2obo2b3o2bo2bo2b3o2bob2o$b2obob2o4b
4o4b2obob2o$5bo3bo8bo3bo$6bobo10bobo$4bobobobo6bobobobo$4b2o3b2o6b2o3b 2o!

(p34) 74P34
x = 27, y = 31, rule = B3/S23
15bo$13b3o$3b2o7bo$4bo7b2o$4bobo$5b2o2$2o$bo$bobo$2b2o11bo$15bo9b2o$9b
3o4bo8bo$9bobo11bobo$9bobo11b2o2$2b2o11bobo$bobo11bobo$bo8bo4b3o$2o9bo
$11bo11b2o$23bobo$25bo$25b2o2$20b2o$20bobo$13b2o7bo$14bo7b2o$11b3o$11b o!

(p35) toaster on 44P7.2
x = 25, y = 17, rule = B3/S23
16bo6b2o$15bobob2o2bo$4bo10bobobobobo$3bobo8b2obo3bob2o$3bobo6bo3b2obo
b2o3bo$2obob2o8bo7bo$ob2o4bo6bo7bo$4b3obo3bo3b2obob2o3bo$4bo9b2obo3bob
2o$5b3o2b2o3bobobobobo$8bo6bobob2o2bo$5b2obobobo3bo6b2o$5b2obobob4o$9b
2o$11b3o$11bo2bo$13b2o!

(p36) p36 toad hassler
x = 20, y = 26, rule = B3/S23
2o16b2o$bo7b2o7bo$bobo3bo4bo3bobo$2b2o2bo6bo2b2o$5bo8bo$5bo8bo$5bo8bo$
2b2o2bo6bo2b2o$bobo3bo4bo3bobo$bo7b2o7bo$2o16b2o$11bo$9bo2bo$9bo2bo$
10bo$2o16b2o$bo7b2o7bo$bobo3bo4bo3bobo$2b2o2bo6bo2b2o$5bo8bo$5bo8bo$5b
o8bo$2b2o2bo6bo2b2o$bobo3bo4bo3bobo$bo7b2o7bo$2o16b2o!

(p37) Beluchenko’s p37
x = 37, y = 37, rule = B3/S23
11b2o11b2o$11b2o11b2o3$6bo23bo$5bobo6b3o3b3o6bobo$4bo2bo5bo9bo5bo2bo$
5b2o6bo2bo3bo2bo6b2o$14b2o5b2o3$2o33b2o$2o33b2o$6b2o21b2o$5bo2bo19bo2b
o$5bo2bo19bo2bo$5bobo21bobo4$5bobo21bobo$5bo2bo19bo2bo$5bo2bo19bo2bo$
6b2o21b2o$2o33b2o$2o33b2o3$14b2o5b2o$5b2o6bo2bo3bo2bo6b2o$4bo2bo5bo9bo
5bo2bo$5bobo6b3o3b3o6bobo$6bo23bo3$11b2o11b2o$11b2o11b2o!

(p38) Raucci’s p38
x = 42, y = 13, rule = B3/S23
4bo32bo$4bo32bo$4bo32bo$6b2o3bo18bo3b2o$3o3b2o3b2o16b2o3b2o3b3o$13bo
14bo$12b2o14b2o3$6b2o26b2o$6bo28bo$7b3o22b3o$9bo22bo!

(p39) 134P39.1
x = 29, y = 25, rule = B3/S23
7b2o3b2o$7bo3bobo$4b2obo2bo2bobo$4bo2b2o3bo2b3o$6bo3bo2bo4bo$7b3obob2o
b3o$9bo5bo$10bo4bob2o$4b2o5b2ob2ob2o$2obobo3bo2bobo$2obob3ob2obobo10bo
$3bo2b2o3bobo10bobo$3bobo2b2o2bo11bobo$4bobo3b2o11b2ob2o$6bobo$6bobob
2o11b2ob2o$7b2ob2o11b2obo$15bo3bo8bo$16bobo8b2o$15b2ob2o$13bo2bobo2bo$
12bobobobobobo$12b2o2bobo2b2o$16bobo$17bo!

(p40) p40 B-heptomino shuttle
x = 27, y = 23, rule = B3/S23
b2o20b2o$b2o20bobo$24b3o$25b2o$3o19b2o$2o20b3o$3b2o$2b3o$bobo3b2o2b2o
10b2o$b2o3bo8b2o6b2o$7b2o7b2o$15b2o$11bo3bo$11bo$7bo4bo5bo$6bobo8bobo$
7bo10bo$11bo2bo$9bo2b2o2bo$9bo2b2o2bo$11b4o$9bobo2bobo$9b2o4b2o!

(p41) 204P41
x = 73, y = 61, rule = B3/S23
34bo$32b3o$31bo$16b2o13b2o$17bo$17bobo$18b2o$29bo$28bobo$27bo3bo$27bo
3bo$27bo3bo$28bobo$29bo2$5b2o24b2o$6bo24bo8bobo$4bo14b2o11b3o6b2o$2b4o
10b2o2bo13bo6bo$bo12bob2o3b4o$o2b3o8b2o3bo3b2obo$b2o2bo8bob2o3bo3b2o$
3b2o5b2o4b4o3b2obo$3bo5b2o9bo2b2o$4bo6bo8b2o$b3o$bo5b2o15bo27bo$8bo14b
obo24bobo$5b3o15b2o26b2o$5bo2$67bo$20b2o26b2o15b3o$20bobo24bobo14bo$
20bo27bo15b2o5bo$69b3o$51b2o8bo6bo$48b2o2bo9b2o5bo$46bob2o3b4o4b2o5b2o
$46b2o3bo3b2obo8bo2b2o$46bob2o3bo3b2o8b3o2bo$48b4o3b2obo12bo$31bo6bo
13bo2b2o10b4o$30b2o6b3o11b2o14bo$30bobo8bo24bo$40b2o24b2o2$43bo$42bobo
$41bo3bo$41bo3bo$41bo3bo$42bobo$43bo$53b2o$53bobo$55bo$40b2o13b2o$41bo
$38b3o$38bo!

(p42) unix on 44P7.2
x = 20, y = 19, rule = B3/S23
16b2o$16bo2bo2$4bo$3bobo10bob2o$3bobo5b2o2bobo$2obob2o4bo4bo$ob2o4bo6b
o$4b3obo3bo2bo$4bo$5b3o2b2o$8bo$5b2obobobo$5b2obobob3o$9b2o4bo$11b4o$
11bo$12bo$11b2o!

For periods 20, 21, and 24, the precise form of the first LCM oscillators is
unknown: the patterns provided are the earliest that could have been
constructed.

## References

  * [1] David Bell  “lifesrc”, 2001  URL: http://members.tip.net.au/~dbell/programs/lifesrc-3.8.tar.gz
  * [2] Elwyn R. Berlekamp, John H. Conway and Richard K. Guy  “Winning Ways for Your Mathematical Plays”  Academic Press, 1982
  * [3] Nico Brown  “LocalForce”, 2022  URL: https://github.com/nicobrownmath/LocalForce
  * [4] Nico Brown  “Strictly Volatile Loop”, 2022  URL: https://conwaylife.com/forums/viewtopic.php?f=2&t=1437&start=3425#p154361
  * [5] David J. Buckingham  “Some Facts of Life”  In _Byte Magazine_ 03.12, 1978, pp. 54–67  URL: https://archive.org/details/byte-magazine-1978-12/page/n55/mode/2up
  * [6] David J. Buckingham  “My Experience with B-heptominos in Oscillators”, LifeCA mailing list, 1996  URL: http://conwaylife.com/ref/lifepage/patterns/bhept/bhept.html
  * [7] David J. Buckingham and Paul B. Callahan  “Tight Bounds on Periodic Cell Configurations in Life”  In _Experimental Mathematics_ 7.3 Taylor & Francis, Philadelphia, 1998, pp. 221–241  DOI: 10.1080/10586458.1998.10504370
  * [8] Paul Callahan  “ptbsearch”, 1998  URL: https://www.ics.uci.edu/~eppstein/ca/ptbsearch.tar.gz
  * [9] Geoffrey Chu and Peter J. Stuckey  “A complete solution to the Maximum Density Still Life Problem”  In _Artificial Intelligence_ 184, 2012, pp. 1–16  DOI: 10.1016/j.artint.2012.02.001
  * [10] Oscar Cunningham  “Logic Life Search”, 2018  URL: https://gitlab.com/OscarCunningham/logic-life-search
  * [11] Simon Ekström  “New construction arms”, 2015  URL: https://conwaylife.com/forums/viewtopic.php?&p=26024#p26024
  * [12] Simon Ekström  “Census of small evolving patterns”, 2016  URL: https://conwaylife.com/forums/viewtopic.php?&p=38773
  * [13] Achim Flammenkamp  “Top 100 of Game-of-Life Ash Objects”, 2004  URL: http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html
  * [14] Martin Gardner  “Mathematical Games: The fantastic combinations of John Conway’s new solitaire game “life””  In _Scientific American_ 223.4, 1970, pp. 120–123
  * [15] Martin Gardner  “Mathematical Games: On cellular automata, self-reproduction, the Garden of Eden and the game “life””  In _Scientific American_ 224.2, 1971, pp. 112–117
  * [16] Goldtiger997  “Reflectorless Rotating Oscillator Discussion Thread in Life”, 2021  URL: https://conwaylife.com/forums/viewtopic.php?&p=135135#p135135
  * [17] Bill Gosper  “paleoballistics”, LifeCA mailing list, 2008
  * [18] Adam P. Goucher  “Universal Computation and Construction in GoL Cellular Automata”  In _Game of Life Cellular Automata_ Springer London, 2010, pp. 505–518  DOI: 10.1007/978-1-84996-217-9˙25
  * [19] Adam P. Goucher  “Is Life omniperiodic?”, 2011  URL: https://web.archive.org/web/20110415012248/http://pentadecathlon.com/lifeNews/2011/01/is_life_omniperiodic.html
  * [20] Adam P. Goucher  “Catagolue”, 2015  URL: https://catagolue.hatsya.com/home
  * [21] Adam P. Goucher  “A rather satisfying winter”, 2018  URL: https://cp4space.hatsya.com/2018/03/11/a-rather-satisfying-winter/
  * [22] Dave Greene  “Re: The search for an Spartan reflector and/or g-x”, 2019  URL: https://conwaylife.com/forums/viewtopic.php?&p=72760#p72760
  * [23] Dean Hickerson  “dr, the drifter search program”, 1997  URL: https://github.com/Matthias-Merzenich/dr/blob/main/dr.documentation.txt
  * [24] Dean Hickerson  “Re: B3/S0123”, 1997  URL: https://conwaylife.com/forums/viewtopic.php?&p=139416#p139416
  * [25] Dean Hickerson  “New billiard tables”, 1998  URL: https://conwaylife.com/ref/DRH/nbt.html
  * [26] Dean Hickerson  “Stamp collection”, 2000  URL: https://conwaylife.com/ref/DRH/stamps.html
  * [27] Nathaniel Johnston  “The Online Life-Like CA Soup Search”, 2009  URL: https://web.archive.org/web/20110510032152/https://www.conwaylife.com/soup/census.asp?rule=B3/S23&sl=1&os=1&ss=1
  * [28] Nathaniel Johnston and Dave Greene  “Conway’s Game of Life: Mathematics and Construction”  Self-published, 2022  DOI: 10.5281/zenodo.6097284
  * [29] Donald Knuth  “Combinatorial Algorithms, Part 2”  Upper Saddle River, New Jersey: Addison-Wesley, 2023
  * [30] Heinrich Koenig  “New Oscillators”, 2009  URL: https://web.archive.org/web/20090417030009/http://pentadecathlon.com/lifeNews/2009/04/new_oscillators_5.html
  * [31] Heinrich Koenig  “New Oscillators”, 2009  URL: https://web.archive.org/web/20090416221124/http://pentadecathlon.com/lifeNews/2009/03/new_oscillators_4.html
  * [32] Dongook Lee  “Results of catalyst tests”, 2015  URL: https://conwaylife.com/forums/viewtopic.php?t=1878
  * [33] Dietrich Leithner  “p57 and p56 Herschel loops”, LifeCA mailing list, 1997  URL: https://conwaylife.com/ref/lifepage/patterns/p57/p57.html
  * [34] LifeWiki contributers  “Oscillator”, 2023  URL: https://conwaylife.com/wiki/Oscillator
  * [35] Matthias Merzenich  “Re: B3/S234”, 2010  URL: https://conwaylife.com/forums/viewtopic.php?&p=2521#p2521
  * [36] Matthias Merzenich  “Re: Just the place for a Snark!”, 2013  URL: https://conwaylife.com/forums/viewtopic.php?p=7820#p7820
  * [37] Matthias Merzenich  “LifeWiki:Game of Life Status page”, 2023  URL: https://conwaylife.com/wiki/LifeWiki:Game_of_Life_Status_page
  * [38] Gabriel Nivasch  “Catalyst”, 2001  URL: https://www.gabrielnivasch.org/fun/life/
  * [39] Gabriel Nivasch  “RandomAgar”, 2002  URL: https://www.gabrielnivasch.org/fun/life/random-agar
  * [40] Luka Okanishi  “Re: Oscillator Discussion Thread”, 2019  URL: https://conwaylife.com/forums/viewtopic.php?&p=85719#p85719
  * [41] Andrzej Okrasinski  “LIFESTAT/Life Screen Saver results”, 2003  URL: http://web.archive.org/web/20091027025324/http://geocities.com/conwaylife/
  * [42] Mike Playle  “Bellman”, 2013  URL: https://github.com/simeksgol/BellmanWin_szlim
  * [43] Mike Playle  “Just the place for a Snark!”, 2013  URL: https://conwaylife.com/forums/viewtopic.php?p=7820
  * [44] Mike Playle  “Bellman: a program for finding catalysts in cellular automata”, 2014  URL: https://github.com/rokicki/lifecontent/raw/master/bellman/bellman-B-2014-08-02.pdf
  * [45] Ruth Pordes et al.  “The open science grid”  In _J. Phys. Conf. Ser._ 78, 78, 2007, pp. 012057  DOI: 10.1088/1742-6596/78/1/012057
  * [46] William Poundstone  “The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge”  Contemporary Books, 1985
  * [47] David Raucci  “Re: Golly scripts”, 2021  URL: https://conwaylife.com/forums/viewtopic.php?f=9&t=45&start=275#p130212
  * [48] Paul Rendell  “Turing Machine Universality of the Game of Life”  Springer, Cham, 2015  DOI: 10.1007/978-3-319-19842-2
  * [49] Mitchell Riley  “Symmetric CatForce”, 2022  URL: https://github.com/mvr/CatForce
  * [50] Mitchell Riley  “Results of catalyst tests”, 2023  URL: https://conwaylife.com/forums/viewtopic.php?p=159968#p158889
  * [51] Tomas Rokicki  “Life Algorithms”  In _Gathering 4 Gardner 13 Exchange Book_ , 2018  URL: https://www.gathering4gardner.org/g4g13gift/math/RokickiTomas-GiftExchange-LifeAlgorithms-G4G13.pdf
  * [52] Ville Salo and Ilkka Törmä  “What Can Oracles Teach Us About the Ultimate Fate of Life?”  In _49th International Colloquium on Automata, Languages, and Programming_ , 2022  DOI: 10.4230/LIPIcs.ICALP.2022.131
  * [53] Ville Salo and Ilkka Törmä  “Computing backwards with Game of Life, part 1: wires and circuits”, 2023  arXiv:2308.10198 [cs.FL]
  * [54] Stephen Silver  “signal elbow”  In _Life Lexicon_ , 2018  URL: https://conwaylife.com/ref/lexicon/lex_s.htm#signalelbow
  * [55] Michael Simkin  “CatForce”, 2014  URL: https://github.com/simsim314/CatForce
  * [56] Karel Suhajda  “JavaLifeSearch”, 2012  URL: https://conwaylife.com/forums/viewtopic.php?f=9&t=990
  * [57] Jason Summers  “torus”, 2000  URL: http://entropymine.com/jason/life/software/
  * [58] Jason Summers  “WinLifeSearch”, 2012  URL: https://github.com/jsummers/winlifesearch
  * [59] Jeremy Tan  “Skopje”, 2021  URL: https://github.com/Parcly-Taxel/Skopje
  * [60] “LIFELINE: A Quarterly Newsletter for Enthusiasts of John Conway’s Game of Life”, 1971  URL: https://conwaylife.com/wiki/Lifeline_Volume_1
  * [61] “LIFELINE: A Quarterly Newsletter for Enthusiasts of John Conway’s Game of Life”, 1971  URL: https://conwaylife.com/wiki/Lifeline_Volume_3
  * [62] “LIFELINE: A Quarterly Newsletter for Enthusiasts of John Conway’s Game of Life”, 1972  URL: https://conwaylife.com/wiki/Lifeline_Volume_5
  * [63] “LIFELINE: A Quarterly Newsletter for Enthusiasts of John Conway’s Game of Life”, 1972  URL: https://conwaylife.com/wiki/Lifeline_Volume_6
  * [64] Robert T. Wainwright  “Life is Universal!”  In _Proceedings of the 7th Conference on Winter Simulation_ 2, WSC ’74  Washington, DC: Winter Simulation Conference, 1974, pp. 449–459  DOI: 10.1145/800290.811303
  * [65] Allan Wechsler  “Missions”, LifeCA mailing list, 1992


$\displaystyle U_{1,2l+1}(\theta)$ $\displaystyle=$ $\displaystyle e^{-i\theta
Z_{2l}}$ (176) $\displaystyle U_{p{\tau},2l+1}(\theta)$ $\displaystyle=$
$\displaystyle e^{-i\theta X_{2l}}$ (177) $\displaystyle U_{2,2l}(\theta)$
$\displaystyle=$ $\displaystyle e^{-i\theta Z_{2l-1}X_{2l}Z_{2l+1}}.$ (178)

By fixing every even qubit, indexed by $2l$, to be in the $|0^{(x)}\rangle$
state this becomes a universal gate set on $\frac{n}{2}$ qubits:

$\displaystyle U_{1,2l+1}(\theta)$ $\displaystyle=$ $\displaystyle e^{-i\theta
Z_{2l}}$ (179) $\displaystyle U_{p{\tau},2l+1}(\theta)$ $\displaystyle=$
$\displaystyle e^{-i\theta X_{2l}}$ (180) $\displaystyle U_{2,2l}(\theta)$
$\displaystyle=$ $\displaystyle e^{-i\theta Z_{2l-1}Z_{2l+1}}.$ (181)

##  Appendix D 1-form symmetry of the $(3,12^{2})$ lattice

In this section we describe implications of the 1-form symmetry of the graph
state on the $(3,12^{2})$ lattice. As seen in Fig. 28, the 1-form symmetry is
generated by loops of $X$ operators around any 12 sided shape in the lattice.
To understand the computational properties of this state we analyze the
capacity of a bowtie subgraph (shaded in grey in Fig. 28) to teleport two
qubits encoded at the left edge to the two at the right edge.

Figure 28: 1-form symmetry of the $(3,12^{2})$ graph state. There is one
symmetry generator for each 12 sided shape in the lattice. The bowtie subgraph
of interest is shaded in grey. Figure 29: Labeling of qubits for the bowtie
subgraph of the $(3,12^{2})$ lattice.

Let us follow the labeling of qubits shown in Fig. 29. For two qubits encoded
on the left edge the logical operators are

$\displaystyle X_{1}^{L}$ $\displaystyle=$ $\displaystyle X_{1}Z_{c_{1}}Z_{3}$
(182) $\displaystyle X_{2}^{L}$ $\displaystyle=$ $\displaystyle
X_{2}Z_{c_{2}}Z_{4}$ (183) $\displaystyle Z_{1}^{L}$ $\displaystyle=$
$\displaystyle Z_{1}$ (184) $\displaystyle Z_{2}^{L}$ $\displaystyle=$
$\displaystyle Z_{2}.$ (185)

Also, there are the standard graph state stabilizers of Eq. (8), $S_{v}$,
centered at all other qubits. Notice that,

$X_{1}X_{2}X_{c_{1}}X_{c_{2}}=-S_{c_{1}}S_{c_{2}}Z_{1}^{L}X_{1}^{L}Z_{2}^{L}X_{2}^{L}\equiv
Y_{1}^{L}Y_{2}^{L}.$ (186)

Thus, measuring the first, second, and two center qubits in the $X$ basis
performs a logical measurement of $Y_{1}^{L}Y_{2}^{L}$, thereby projecting the
input into the $(-1)^{m_{1}+m_{2}+m_{c_{1}}+m_{c_{2}}}$ eigenspace.

Returning to the $(3,12^{2})$ lattice, we see that performing $X$ measurements
on each qubit along each column implements a circuit consisting of
$Y_{j}^{L}Y_{j+1}^{L}$ parity measurements. Thus, this lattice acts as a
foliated repetition code with stabilizer generators

$\displaystyle\langle\left\\{Y^{L}_{j}Y^{L}_{j+1}\right\\}_{\forall
j}\rangle.$ (187)

Figure 30: The basics of the ZX-calculus. (a)The ZX-Calculus consists of three
basic elements. Z-Spiders, X-Spiders, and the Hadamard. Notice X and Z-spiders
are related by applying a Hadamard to each leg. (b) The only two rewrite rules
we will need are the spider and bi-algebra rules. These can be easily derived
using the definitions of the X and Z-spiders. (c) Simple identities that will
be useful for our purposes. Notice for the $CNOT$ operation the target is the
red spider. Figure 31: The ZX-diagram for the a-causal circuit. By pushing
Hadamards to the end, applying the bi-algebra rule, and deforming the
resulting diagram, the a-causal part of the circuit is reduced to $n-1$ wires.
Figure 32: Simplifying the ZX-diagram. Applying the bi-algebra and spider rule
iteratively, the a-causality of the diagram can be shown to have the structure
of a circuit in which one qubit is measured.

##  Appendix E Proof of QCA circuit for alternatively foliated $(3^{6})$
lattice

In this section we derive the expression for the circuit shown in Fig. 18
corresponding to the ring tensors for the triangular lattice graph state with
the alternative foliation, shown in Fig. 17. First, contract each physical
index around the ring with an arbitrary $X$ eigenstate (i.e. the measurement
tensor in Eq. (62)). By Eq. (73) any $Z$ operator can be pulled through to the
left virtual index of its respective site,

$\includegraphics[width=216.81pt]{Ring_Tensor_Eq1}.$ (188)

Notice that $|m^{(x)}\rangle=Z^{m}|0^{(x)}\rangle$ so contracting a physical
index with $|m^{(x)}\rangle$ is equivalent to first applying $Z^{m}$, and then
contracting with $|0^{(x)}\rangle$. Decomposing each measurement tensor in
this way and pushing the outcome dependent $Z$ operator to the virtual level,
each tensor can be replaced with a Hadamard gate by Eq. (71),

$\includegraphics[width=216.81pt]{Ring_Tensor_Eq2}.$ (189)

Contracting the upper and lower indices of these tensors around a ring gives a
quantum circuit that contains an acausal component. To exorcise the acausality
we appeal to the ZX-calculus [55, 56], a diagramatic language for simplifying
and rewriting quantum operations. The basic rules of this formalism needed for
this calculation are summarized in Fig. 30.

Let us focus on the acausal part of the circuit. This is recast as the ZX-
diagram in Fig. 31. By first moving all Hadamard gates to the right, applying
the bi-algebra rule on the bottom wire untwists that wire out of the acausal
loop. Leveraging the spider rule, the resulting diagram contains an acausal
loop on the remaining $n-1$ wires with the last wire separated out.

Iterating this procedure until the acausal part only acts on three wires, one
more iteration leaves us with a diagram containing a structure that looks like
the right hand side of the bi-algebra law on the top two wires. Apply the bi-
algebra rule on this structure and insert an identity as a Z and X-spider on
the left and right, respectively. By the spider rule we may then pull out a
single node of an Z and X-spider from these identities. Pulling out a Hadamard
on the right hand side and inserting a resolution of the identity in the form
of,

$\mathbbm{1}=\left(\prod_{j=2}^{n}CNOT_{1,j}\right)^{2},$ (190)

we end up with the diagram at the bottom of Fig. 32.

Noting that,

$\left(\prod_{j=2}^{n}CNOT_{1,j}\right)\Pi_{X}\left(\prod_{j=2}^{n}CNOT_{1,j}\right)=\Pi_{\bar{X}},$
(191)

the operation on the left hand side of the last diagram in Fig. 32 may be
replaced by $\Pi_{\bar{X}}$. The resulting circuit is then,

$\includegraphics[width=433.62pt]{Circuit_Part_3}.$ (192)

Returning to the full circuit, we may Heisenberg evolve the outcome dependent
$Z$ operators through the circuit to obtain an expression for the contracted
ring tensor. Therefore, preforming $X$ measurements on each site around a ring
at the boundary of the state implements the following circuit,

$\includegraphics[width=433.62pt]{Circuit_Part_5}.$ (193)