Reversible cellular automata
This is the first my post on Reversible Cellular Automata, there will be several more.
TL;DR: play with reversible cellular automata simulator. It is in HTML5, so you probably need some decent browser. Come back to this page, if you don't understand, what is going on.
Don'w want to read about the math? Then skip to the Simulator section below.
- Reversible computation
- Reversible cellular automata
- Block cellular automata: an easy way to construct reversible CAs
- Margolus neighborhood
- The Simulator
- Some of the rules, supported by the simulator
Computation y=f(x) is reversible, if input data x can always be uniquely restored from output y. Wikipedia have more detailed page on reversible computations.
For example, logical negation: y = ¬x is reversible. If output is 1 then input is 0 and vice versa. In contrary, 2-ary AND (conjunction) is not, since output 0 corresponds to the three different inputs: (0,0), (0,1), (1,0). Most of the commonly used logical gates are not reversible too.
However, it is possible to construct blocks, that are reversible. It can be easily seen (by the pigeonhole principle) that reversible logical gate (function) with n inputs must have exactly n outputs. Such function can be seen as transposition of 2n elements. Famous examples are:
|0 0 0||0 0 0|
|0 0 1||0 0 1|
|0 1 0||0 1 0|
|0 1 1||0 1 1|
|1 0 0||1 0 0|
|1 0 1||1 0 1|
|1 1 0||1 1 1|
|1 1 1||1 1 0|
Indeed, reversible computing is interesting topic by its own. Curiously it is not a pure mathematical toy: it is deeply connected with quantum computing and theory of computation. But I am giving up here - ask Wikipedia for more information.
Reversible Cellular Automata
What I want to write about are Reversible Cellular Automata, i.e. cellular automata, allowing deterministic evaluation “back in time”: from the future to the past. Transition function in such automata must be reversible.
It is easy to prove that the iconic Conway's Life is not reversible. This directly follows from the existence of many different configurations that eventually die out. Consequently, empty field do not have unique predecessor, and cellular automaton is irreversible. Existence of configurations without any predecessors: Gardens of Eden, is a much less trivial fact.
Building a non-trivial reversible cellular automaton may appear to be a tricky task. In fact, there is a theorem stating that testing reversibility of a 2-dimensional CA is an undecidable problem: no algorithm can do it for sure. But there is a class of CAs, where reversibility can be achieved and tested in a simple and straightforward manner: block cellular automata.
Block Cellular Automata
The idea behind block cellular automata construction is:
- The lattice of cells is partitioned to equal blocks.
- Each block is transformed independently.
- After each step, partitioning scheme of the lattice is changed.
One of the simplest and most symmetric partitioning schemes is arguably the Margolus neighborhood. Wikipedia contributors say:
See also definition in the MCell documentation.
In the Margolus neighborhood, the lattice is divided to 2-cell blocks (or 2 × 2 squares in two dimensions, or 2 × 2 × 2 cubes in three dimensions, etc.) which are shifted by one cell (along each dimension) on alternate timesteps.
Properties of the Margolus Neighborhood
An important difference between the block CAs (included those based on Margolus neighborhood) and the more widely known totalistic CAs with Moore or von-Neumann neighborhoods (like the Game of Life) is that the former are generally have less symmetry.
First of all, Margolus neighborhood CAs are not invariant under translations by odd amount. Take one pattern of alive cells, move it by 1 cell vertically, horizontally or both, and you will generally get a pattern with completely different behavior. See the example below and try it live in the simulator (opens in the new window):
Analogously, Margolus neighborhood CAs are not invariant under translations in time by odd number of steps, i.e. they are not completely stationary. Since in block CAs partitioning scheme changes on every generation, the same pattern will evolve differently, depending on whether it was started from the step 0 or from the step 1. In other words, state of the block CA universe have an additional parameter besides the state of the cells: the phase of the partitioning. In the Margolus neighborhood, there are 2 phases, thus 1 additional bit of information is required.
In the general case, block CAs are not invariant neither under rotations by 90° nor under flips. They are only invariant under these transforms, if the block transition function is invariant under them. This means that the space of such CAs is less isotropic than the space of the conventional totalistic CAs. There are asymmetric rules where, for example, orthogonal spaceships moving to the right are completely different from the ones moving to the left.
It is easy to see that in the Margolus neighborhood, the whole CA is invariant under the geometrical transform iff its block transition function is invariant under this transform.
Rules in the Margolus neighborhood
In the block CA with Margolus neighborhood, each block consists of 4 cells, thus transition function must have 4 inputs and 4 outputs. For the binary cellular automata, this gives 24=16 possible input and output states. A block transition funciton must map every possible input to some output. To be reversible, this mapping must be one-to-one (bijective), thus effectively being a transposition of 16 elements.
State of the block can be encoded into one 4-bit binary number. Then any function can be written down as a list of 16 numbers in the range [0..15]. If the function is reversible, then every number occurs exactly one time in this list. For example, [0,8,4,3,2,5,9,7,1,6,10,11,12,13,14,15] describes a reversible function.
I am proud to present a working simulator program for the reversible cellular automata with Margolus neighborhood. It runs directly in the browser, without download and installation.
- The Simulator. (link opens in the new window)
- Sources (Github). Mostly written in CoffeeScript. Don't expect too much: it's my first big JS/CS project so far, it is written mostly for practice.
- Help page of the simulator .
I hope you will find the interface of the Simulator to be mostly self-explanatory. Like in then most conventional CA simulators, you can edit cell patterns with mouse and run simulation, step-by-step or continuously. If you have seen Golly then you know it all. The key feature you will not find in Golly is the “Reverse Play” button that allows you to evaluate cellular universe back in time. Indeed, it is only possible for the reversible cellular automata.
Basic features are:
- Editing cells using mouse or touch interface (the latter is not convenient but supported).
- Running the automaton in the forward and reverse direction.
- Changing cellular automation rule. Either select one of the predefined rules, or enter your own in the transposition notation (See “Rulse in the Margolus neighborhood” above).
- Clear selected or non-selected area
- Fill with random cells
- Analyze selected pattern (see advanced features)
- Copy selected pattern to the internal buffer, and then paste it to the field
Besides the basic field editing and simulation, simulator program provides some features for more detailed analysis of the rules and patterns. These features include:
- Pattern analyzer
- Spaceship catcher
- Rule analyzer
- Save state to the URL
Want to know, whether the pattern is a oscillator, spaceship or something other; what are its period and movement speed? Just select it and click the “Analyze” button. The application will evaluate the pattern and extract some basic information about it, including:
- Pattern type: oscillator, spaceship (diagonal, orthogonal or slant) or neither.
- Pattern period, if it is an oscillator or spaceship.
- Pattern movement speed, in case it is a spaceship.
Such large periods enormously complicate manual analysis of the patterns. Given 2 visually different patterns, how do you decide: are they different phases of the same pattern, or just 2 different patterns? Canonical form gives a solution to this problem. Analyzer evaluates given pattern during its period, and chooses one configuration, that minimizes some criteria. (Precisely speaking, it searches for the most compact configuration, but it is not actually important). What is important is that such canonical form is determined uniquely (in most cases). Additionally, if the pattern was identified to be a spaceship, and the rule allows rotations, canonical form is rotated so that movement direction was to the right (orthogonal) or to the bottom-right (diagonal). Using canonical form, determining equivalence of two patterns is trivial: equivalent patterns has the same canonical forms.
This feature facilitates search for the naturally born spaceships by initializing field with random initial pattern in the center and collecting escaping spaceships. When the spaceship catcher is enabled, all patterns touching the border of the field are removed from it, analyzed and spaceships are added to the currently open library. Every 30000 steps (which is default value that can be changed on the “Settings” pane), the field is re-initialized: current selection is filled randomly.
In the “Rule” pane, various information regarding the current rule is shown. Besides the (hopefully) obvious graphical representation of the transfer function, it includes the following information:
- Rule code, as 16 comma-separated integers. This code can be edited manually. See "Rules in the Margolus neighborhood" above.
- Reversibility of the rule: whether it is reversible or not.
- Rule invariants, such as rotation by 90° or 180° and mirror flips.
- Duality transformation of the rule. I'll cover this later. See help page for details.
These rules are taken from the MCell documentation page.
|BBM||0, 8, 4, 3, 2, 5, 9, 7, 1, 6, 10, 11, 12, 13, 14, 15||Famous Billiard Ball Machine - from Cellular Automata Machines. A rule by Edward Fredkin. This rule supports bouncing cells and stable borders.|
|Bounce Gas||0, 8, 4, 3, 2, 5, 9, 14, 1, 6, 10, 13, 12, 11, 7, 15||An uniform “gas”. A rule by Tim Tyler. Similar to BBM, but without borders.|
|Bounce Gas II||0, 8, 4, 12, 2, 10, 9, 7, 1, 6, 5, 11, 3, 13, 14, 15||Another uniform “gas”. A rule by Tim Tyler.|
|Critters||15, 14, 13, 3, 11, 5, 6, 1, 7, 9, 10, 2, 12, 4, 8, 0||This rule supports “spaceships” - as described in Cellular Automata Machines. A rule by Margolus/Toffoli.|
|HPP Gas||0, 8, 4, 12, 2, 10, 9, 14, 1, 6, 5, 13, 3, 11, 7, 15||HPP (Hardy/Pazzis/Pomeau) lattice gas - as described in Cellular Automata Machines. A rule by Hardy, Pazzis, and Pomeau.|
|Rotations||0, 2, 8, 12, 1, 10, 9, 11, 4, 6, 5, 14, 3, 7, 13, 15||Limited diffusion. A rule by Tim Tyler.|
|Rotations II||0, 2, 8, 12, 1, 10, 9, 13, 4, 6, 5, 7, 3, 14, 11, 15||Limited diffusion. A rule by Tim Tyler. This rule has a rich set of extremely slow spaceships with periods around 10000. You will need to increase maximum analysis depth in the settings, if you want to identify these spaceships.|
|Rotations III||0, 4, 1, 10, 8, 3, 9, 11, 2, 6, 12, 14, 5, 7, 13, 15||Slow, random-looking diffusion. A rule by Tim Tyler. Supports many slow spaceships.|
|Rotations IV||0, 4, 1, 12, 8, 10, 6, 14, 2, 9, 5, 13, 3, 11, 7, 15||Slow, random-looking diffusion. A rule by Tim Tyler. Supports many relatively fast spaceships.|
|String Thing||0, 1, 2, 12, 4, 10, 9, 7, 8, 6, 5, 11, 3, 13, 14, 15||String shaped patterns. A rule by Tim Tyler.|
|String Thing II||0, 1, 2, 12, 4, 10, 6, 7, 8, 9, 5, 11, 3, 13, 14, 15||More string shaped patterns. A rule by Tim Tyler.|
|Swap On Diag||0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15||A gas with no particle interactions - as described in Cellular Automata Machines. A rule by Margolus/Toffoli.|
|Tron||15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0||A “trip-a-tron” - from the pages of Cellular Automata Machines. A rule by Margolus/Toffoli.|