A Physically Universal Cellular AutomatonLuke Schaeffer
is about an implementation of the cellular automaton from my physical
universality paper (available here) in Golly, an
open-source, cross-platform, cellular automaton simulator. We give a
description of the cellular automaton and the
construction in the paper, with more emphasis on the details of the implementation.
Files and GollyYou can find Golly here. The files below are for version 2.5 and up. You may also want to install Python to enable scripts in Golly. Python is not necessary for most basic operations in Golly, but we do use one script, goto.py,
to jump ahead a large number of timesteps. Golly will look for Python
2.7 libraries, so install Python 2.7 and note that "a 32-bit version of
Golly requires a 32-bit version of Python, and a 64-bit Golly requires
a 64-bit Python".
To see the CA and physical universality in action, all you need are these two files:
The first file, PhysicColor.rule,
tells Golly the states, neighbourhood, update rule, etc. for the
cellular automaton. It should be placed either in your user rules
folder (look under Preferences in Golly to see where this is) or in the
Rules subfolder of your Golly installation. The second file, transformation.mc, is a pattern file, describing a specific configuration of the cells. All you need to do is open transformation.mc in Golly; it knows PhysicColor
is the associated rule and will automatically use it (if it can find
it). Note that transformations.mc is quite a large pattern, so you will
need to zoom in (about 1000x) to see individual cells.
The Cellular Automaton
The CA is based on particles moving in two dimensions.
The behaviour of the particles is defined as follows.
- At discrete timesteps, each particle is at an integer point.
- Each particle points in one of four directions: northeast, northwest, southeast, southwest.
- There is at most one particle with a given position and direction.
- Particles are indistinguishable.
- Each particle moves in the direction it points at a rate of one cell per timestep, until it meets other particles.
- Particles interact where they meet, at integer or half-integer points.
- When particles meet, they pass through each other unless there are exactly three particles.
- When three particles meet, the two opposing particles reflect the third particle.
RepresentationIdeally we would represent the CA like this:
cell represents an integer point, and we draw arrows in the cell to
represent the particles present at that point. We have colour-coded the
particles by direction. Some of the cells are also marked gray, but
this is purely cosmetic. We adopt this colour convention throughout:
northeast (green), southwest (red), southeast (yellow), southwest
(blue), with gray to mark regions.
Unfortunately, in this
representation, the state of a cell depends on its current state (4
bits of information) and 12 bits from its neighbours. To implement the
rule, we have to give Golly a table of all 65536 cases. To its credit,
Golly happily accepts the massive rule table, but at some cost to
performance. Instead, we will use a "sparse" representation, which
looks like this.
particles are spaced out, with an extra row and column of empty space
between them. We also split each timestep into two halves: the
particles are at integer points in even timesteps, and at half-integer
points in odd timesteps. Using the sparse representation, each cell
depends on one particle from each of its four diagonal neighbours, so
we can specify it with a table of only 16 rules.
case we use 16 states, whereas in the paper we only use two. The 16
state CA is still physically universal, but we would prefer a binary
CA. The problem is that Golly is designed for Moore neighbourhood rules
(especially Conway's Game of Life) and has only limited support
for Margolus neighbourhoods. It can simulate a given Margolus rule with
a custom 5-state Moore neighbourhood rule, but the pattern has to be
formatted like this:
are Python scripts available to convert patterns between this format
and a truly binary representation, but they are unbearably slow on
patterns of the size we are interested in. Since our CA maps empty
space to empty space, we can construct a 5-state Moore CA where only
live cells must be formatted.
the advantages of simulated-Margolus representations do not outweigh
their disadvantages, so we use the 16-state sparse representation
interactions between particles are summarized in this table (including
trivial zero- and one-particle interactions). Recall that particles
only interact if there are exactly three particles present.
Physical UniversalityA cellular automaton is physically universal
if it can implement any transformation on any finite region by
configuring the surrounding cells and letting the CA evolve. Let's see
an example in our CA. Open up file transformation.mc in Golly. You will be confronted with something like this:
this scale, all the particles appear blue because there are multiple
cells per pixel, so blocks get represented by state 1's colour (blue)
if anything is alive, and state 0's colour if everything is zero. Zoom
in (say, by pressing ] thirteen times) to find
the gray 5-by-5 square in the middle, at coordinates (0,0). The complex
configuration around the gray cells is engineered to perform a
transformation on the square if we let the CA run for 46754 timesteps.
Golly provides the Python script goto.py to advance to a given generation quickly, or you use the regular controls and the generation counter at the top left.
After 46754 timesteps, the following pattern should replace the original gray square.
This is a transformation of our original input. If we go back to the beginning (Ctrl-R),
change some of the gray cells, and step forward again, then the new
output configuration will be the result of applying the transformation
to the new input.
Physical Universality ConstructionIn this section, we will see how the configuration in file transformation.mc implements a transformation. There are three main steps:
- Get the information out of the finite input region.
- Perform the computation.
- Fill the output region with the desired output.
Extracting the InputWe
may assume the input region is a square, since any finite region is
contained in a square region (i.e., bounding box) and we can extend the
transformation from the region to the box arbitrarily. Extracting the
input from the box is surprisingly simple:
particles literally escape on their own. Moreover, the particles exit
the box quickly, and in orderly square groups. If some of the particles
in the box are missing, then there will be holes in the groups.
presence or absence of particles in these groups tells us everything we
need to know about the initial configuration of the box. We call these bits of information signals.
computation phase will useall four groups to compute the output
configuration. It is difficult to perform computations when the signals
are moving in four different directions at the speed of light (i.e., as
fast as they can move), so we will manipulate the signals into a column
before we begin computation.
Redirecting the InputRecall
from the paper that we can reflect or deflect a signal. Suppose a
signal is moving southeast. If we intercept it with two signals at
right angles, then we have
signal leaves going northwest. On the other hand, if we intercept the
signal with a particle in the opposite direction and a particle at
right angles then we have this
The signal continues through, but we get a copy of the signal (and its negation) at right angles.
these two operations, we can essentially redirect particles however we
like, given enough time. For example, at the very beginning we copy or
rearrange signals so that all the information from the four square
groups is moving northeast.See below.
short yellow and blue lines of particles (southwest of the box) reflect
the southwest group before it can even leave the box. Meanwhile, the
red blob to the east, and the blue curve below intercept the group
moving southwest and deflect a copy of the information as a green blob.
The same happens on the other side, so we end up with two blobs and two
squares moving northeast, carrying all the information about the input
with them. Next, we want to take the cloud of signals moving northeast
and rearrange them into a column. This is done in two steps.
we rearrange the signals so there is at most one signal along each
northeast/southwest diagonal. The two blobs already have one signal per
diagonal, but the two square groups need to be fixed.
can see five yellow pulses meet five red pulses and one of the square
groups. This creates five blue pulses, moving west relative to the
group, carrying all the information from that square group. Then
another five yellow pulses and five red pulses fix the blue signals
into five green lines, to the west of one of the green blobs. The same
thing happens to the other square group. Once we have copied both
groups, we no longer need them, so two pairs of yellow and blue lines
reflect the groups southwest.
Second, we reflect each signal backwards for just the right amount of time to align all the signals into a column.
blue and yellow structures intercept the green signals, reflecting them
backwards (in red), where another pair of blue and yellow structures
align them into a column. Note that the second set of yellow structures
are themselves in a column. In fact, the yellow particles are in the
same column as the green signals, so it is unfortunately a bit
difficult to distinguish one from the other.
Computation and OutputAll
computations are done using the interaction below. A red particle meets
two unknown signals from the southwest and northwest.
Call the yellow signal x, and the green signal y. A particle escapes moving southeast if and only if x and not y.
practice, the input signals, and signals for intermediate computations
are in a column formation moving northeast. We implement a logical gate
by sending a (yellow) particle, the runner, southeast through the
column. The runner passes all of the signals along the way. We send red
particles from the northeast to intercept the runner when it meets the
signals corresponding to the inputs of the gate. If any of those input
signals is 1 (i.e., a particle is present) then the runner is
reflected. The runner gets through if and only if all the signals are
zero. Finally, a (blue) particle from the southeast meets the runner
and a (red) particle from the northeast. This creates a new signal
because the red particle is reflected into position if and only if the
runner is present.
You can see the computation in transformation.mc
below. The input signals are barely visible as a pair of lines at the
bottom left. A long line of yellow particles on the left serve as
runners. The gates are specified by the large red triangle. The red
particles at the bottom edge of the triangle, along with corresponding
line of blue particles (mostly out of frame, to the south), create the
new signals used within the computation, and eventually the output
this level of zoom, we can only see very high-level features of the
transformation being implemented. You may be able to see a string of
four to six parallelogram-like structures near the bottom of the red
triangle, growing larger in the middle and smaller towards the ends.
These implement circuits for decoding the original input configuration
from the input signals, and then reencoding the output signals to
achieve the desired output. This entails simulating the CA backwards on
the 5-by-5 square for 5 steps. But if we watch the input diffuse out of
the box in reverse, we see that when the four groups interact, it is
initially only in a single cell, then 4 cells in the next step, 9
cells, and so on. There is a parallelogram for each step, but only
the last two or three are large enough to be identifiable. Then the
same thing happens in reverse for the output. The parallelograms are
clearer when the input is larger.
the computation is complete, we reflect all the signals except the ones
we want. Then a sequence of redirections puts the output signals into
four square groups.
only lasts for a moment (actually, a few thousand timesteps) before we
redirect them again. Two of the groups will be reflected to arrive at
the output at the desired time from the northeast and southwest. The
other two groups are redirected to intercept two square configurations
of particles, shown below.
two groups of particles were on a collision course from the very
beginning, destined to meet in the gray box after 46754 timesteps. We
carve out particles from these two groups to create the configurations
we want. Eventually, the four groups converge on the gray square and
produce the desired output.
This completes the construction.