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.
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:
The latter is universal: it can be used to construct a circuit for an arbitrary logical function (provided some “garbage” outputs and “zero” inputs added to achieve reversibility).
Input
Output
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
Truth table of the Toffoli gate, reversible function from {0,1}3 to {0,1}3.
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
Billiard Ball Machine: an example of reversible cellular automata, used to construct universal calculator.
Play with it live.
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.
Proof that Game of life is not reversible. Image from LifeWiki.
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.
Obviously, these 2 rules alone are not enough to build any interesting automaton, since blocks are not interacting. Therefore the 3rd rule is needed:
After each step, partitioning scheme of the lattice is changed.
Margolus neighborhood
One of the simplest and most symmetric partitioning schemes is arguably the Margolus neighborhood. Wikipedia contributors say:
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.
The Margolus neighborhood for a two-dimensional block cellular
automaton. The partition of the cells alternates between the set of 2 × 2
blocks indicated by the solid blue lines, and the set of blocks
indicated by the dashed red lines.
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):
Orthogonal c/2 spaceship and p8 oscillator in the Critters reversible rule. Shift by 1 cell completely changes pattern evolution.
The reason is simple: odd translation will change the partitioning of the pattern to blocks, inevitably changing pattern's behavior.
Block cellular automata are only invariant under translations that don't change the borders of the blocks; in the Margolus neighborhood case it is translations by even amount.
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.
Evolution of the initial pattern under asymmetric rule. Evolution is not symmetric despite the initial pattern is.
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.
The Simulator
User interface.
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.
Running in the browser have some disadvantages though. Particularly, you don't have access the local file system and can't save your work. This problem can however be alleviated thanks to the “Save to URL” feature (currently on the “Settings” pane).
Requirements
The simulator program is written in JavaScript and HTML5, therefore a decent browser, supporting these technologies is an absolute requirement.
I have tested the simulator in the latest version of desktop Firefox, Chrome and Opera; and it works well. It does not works in IE9, but IE 10 should support it (never tested though).
It will also work on some mobile browsers, particularly on Android and Chrome, but the interface is most suited for mouse, not for touch screens.
Basic usage
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).
Selection:
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
Advanced features
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
Pattern analyzer
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.
But even more importantly, it will try to find the canonical form of the pattern. A little explanation here:
In the Game of Life, most commonly occurring patterns have relatively small periods. The glider have period of 4 generations, for blinker it is 2, and so on. In the contrary, for the reversible CAs big periods are not an exception. No, not just big: sometimes they are HUGE. One example:
A diagonal spaceship with period 10896 and velocity c/5448. Rule is “Rotations II”.
Try it live
(new window).
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.
Spaceship catcher
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.
Rule analyzer
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:
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.
Comments