Skip to content

TheRules

Tim Hutton edited this page Apr 16, 2017 · 27 revisions

The Rule Tables:

Here is a list of rule tables for simulating cellular automata in Golly:

Von Neumann's CA and close variations

Von Neumann, famous for inventing parallel processing and the concept of storing data and instructions in the same tape, created the first cellular automaton in order to allow self-replication. Since then, Renato Nobili and Tim Hutton have successively augmented the rules to simplify the machines.

year rule description images
late 1940's JvN29.table John von Neumann's original 29-state CA. The rule is a complex UCC rule, it uses two types of signal, ordinary and special transmission, each working in the four cardinal directions and having quiescent and excited properties. The rule also has temporary states for construction. http://gollygang.github.io/ruletablerepository/downloads/jvn29.PNG
1994 Nobili32.table Renato Nobili's extension of von Neumann's 29-state CA to allow easier crossing of wires, leading to simpler machines. Golly includes four configurations in this rule. Adam P. Goucher has built a fast replicator, which only takes 2.08 million generations to replicate. Read more...
2008 Hutton32.table This is a modification of Nobili32 created by Tim Hutton to allow simpler construction and rotational symmetry. This enables the replicator to construct two copies, perpendicular to each other, so that the replicator grows like a binary tree. Read more...

Codd's CA and descendents

Codd produced a CA that had far fewer states than Von Neumann's original 29-state rule, it also allowed rotational invariance. His design for a self-replicating machine is much more complex, and Tim Hutton has only recently implemented it. Adam P. Goucher made a universal constructor that replicates much faster. However, Goucher's machine is inferior to the Codd-Hutton machine, as it is incapable of computation.

Tim Hutton has recently released a paper, outlining Codd's self-replicating machine and describing his implementation. The tape for self-replication is almost 207 000 000 bits in length!

http://www.sq3.org.uk/papers/Hutton_CoddsSelfReplicatingComputer_2010.pdf

year rule description images
1968 Codd.table Edgar F. Codd's cellular automaton, which requires only eight states -- a significant reduction over JvN29. This is achieved in part by using a sheath to cover the signal wires, to remove the need for directional arrows. Codd's book. Wikipedia
1971 Codd-ICRA A team of Hungarian researchers modified Codd's rules (paper). Crossovers can be made with only nine cells, and gates can be constructed by passing 7-0 signals. This rule table is not the original ruleset, but rather the Codd-ICRA rule with TJH's safe sheathing transitions (see Codd2.table, below). There are three pattern files attached that demonstrate the advantages of the Codd-ICRA variant.
1973 Devore.table John Devore altered Codd's ruleset to allow for more compact machines. The main difference between Devore's and Codd's cellular automata is that Devore's allows 2x2 blocks of cells to behave like split devices, merge units or one-way diodes. With this rule, a much simpler crossing can be created. Golly has a functioning self-replicator in this ruleset: Devore-rep.rle. Additionally, Adam P. Goucher made another replicator that uses a weak form of run-length encoding to compress the size of the tape: D-compressed-replicator.gz. However, he did not have access to the small crossing, so had to make a large, cumbersome one instead.
2009 Codd2.table It was recently realised that Codd's rule table required three extra transitions in order to be able to sheath large complex structures. With this rule, an implementation of Codd's self-replicating machine was created: Codd-self-rep.zip (12MB) (now contains the full tapes for self-rep!) In addition to this, a replicator has been built in this rule that uses a repeater-emitter loop, similar to Hutton's replicator. It replicates in under one billion generations.

Self-replicating loops

Christopher Langton altered Codd's ruleset, removing the universality to allow simple self-replicating loops. Several rules have been made to either:

  • Re-introduce the computation/construction abilities. (Tempesti, Perrier)
  • Allow a further reduction in size (Byl-loop, Chou-Reggia-1, Chou-Reggia-2)
  • Simulate evolution and genetic mutation. (SDSR, Evoloop, Sexyloop)
year rule description images
1984 Langtons-Loops.table Chris G. Langton extended Codd's rules to allow a totally novel form of simple self-replicator - the loop. This was based on a very simple element of Codd's CA - the periodic emitter. The instructions for extending and turning the pseudopod is simpler in Langton's loops than Codd's CA - it requires half as many pulses to extend and turn the arm. This comes at the expense of removing the ability for universal computation and construction.
1989 Byl-Loop.table J. Byl managed to reduce the size of Langton's Loop. Whereas Langton's loop consists of an internal and external sheath, the Byl loop only requires an external sheath. This reduced the size of the replicator from 86 to just 12 live cells.
1993 Chou-Reggia-1.table, Chou-Reggia-2.table A further reduction of Langton's Loops - down to just five cells. This is a modification of Byl's loop that doesn't even need an external sheath. However, the simplicity of it makes it difficult to identify it as a loop.
1995 Tempesti.table Gianluca Tempesti's programmable loop that is capable of constructing various things inside itself - for example the initials of Tempesti's group: "LSL". Tempesti's thesis.
1996 Perrier.table Perrier added universal computation capabilities to Langton's loop by adding a program stack and an extensible data tape.
1998 SDSR-Loop.table Hiroki Sayama introduced a change to Langton's Loops that caused dead loops to disappear, allowing live ones to reproduce further. Homepage.
1999 Evoloop.table Another loop from Sayama, that allows colliding loops to sometimes merge genetic content. Over time, smaller loops appear as these outcompete the larger ones. Homepage.
2007 SexyLoop Nicolas Oros and Chrystopher L. Nehaniv modified Sayama's evoloop to allow the transfer of genetic material from one loop into another. The zip file contains 3 rule tables (Sexyloop-M1, Sexyloop-M2, F-sexyloop) and some example patterns. Details and references can be found here. http://gollygang.github.io/ruletablerepository/downloads/Sexyloop.png
2009 Goucher's Loops A 24-state version of Langton's loops, that permits construction and computation universality, right turns as well as left turns, genome combination and competition. In this rule, smaller loops do not necessarily survive better; square loops are very fragile, whereas crosses are more resilient.
2010 Bakker loop Grant Bakker made a 7-state sheath-free loop with the interesting property of sending out 'runners' to start new colonies. His Java implementation is included in the zip. http://gollygang.github.io/ruletablerepository/downloads/Bakker-Loop.png
2013 Petelka Petelka (Petelka - "Little loop" in Polish) with variant Petelka-2 - rule with something similar to little loop. Probably it is not a loop beating the record of Chou-Reggia Loop, but I don't know which part of definition is not fulfilled. Petelka has also 1D replicator. In Petelka-2 the same pattern creates two loops. http://gollygang.github.io/ruletablerepository/downloads/Golly_Petelka_mini.png

WireWorld and derivatives

Brian Silverman's WireWorld rule is available here, together with some interesting modifications by Alan Tennant and Mark Jeronimus.

year rule description images
1987 WireWorld Brian Silverman's famous CA for electronic wiring. This uses four states and has a finite size. An impressive computer has been built that calculates 16-bit prime numbers. Read more...
2009 WWE, WWE2, WWEJ and WWEJ2 Previous Wireworld Extendable rules. WWE and WWE2 were created by Alan Tennant and WWEJ and WWEJ2 by Mark Jeronimus. Unlike the original WireWorld rule, these rules support universal construction, replication and modification. Includes various examples including a replicator by Adam P. Goucher.
2010 WWEJ3 WWEJ3 by Mark Jeronimus and Alan Tennant, coded by Mark Jeronimus, contains all the functionality of old WWEs with none of the compromises or bugs, and with only 18 states.
2010 WireWorldMarked A marked version of WireWorld. It supports six extra wire colors but no extra functionality. A marked version of the Quinapalus' Primes Computer is included. http://gollygang.github.io/ruletablerepository/downloads/WireWorldMarked.png
2009 Switch CA WSwitch is a 5-state rule by Alan Tennant. The rule is loosly based on WireWorld. The construction of logic gates is not possible directly. Instead, 3 types of pulse dividers are possible.
2011 Particles Particles is loosely based on Wireworld, with a few differences: Particles move through open space instead of wires, and they can also collide to create, move, or remove blocks. This means that a Particles system could reproduce itself. A rule by Joel Walker. http://gollygang.github.io/ruletablerepository/downloads/Particles.png
2011 Blocks And Walls A complex yet simple to use cellular automata that is based loosely off Particles. A rule by Conrad Walden. http://gollygang.github.io/ruletablerepository/downloads/BlocksAndWallsPNG.png

Other computation rules

This section comprises other rule tables, which facilitate universal computation. These support logic gates and storage devices easily, making them useful rules for testing logic circuits in a precise and efficient manner.

year rule description images
1971 Banks-I, Banks-II, Banks-III, Banks-IV Edwin Roger Banks made various cellular automata that support universal computation. The first rule has a fixed size (and memory); the second allows memory expansion. The third rule uses the Moore neighborhood to reduce the number of states to just two. The fourth rule allows universal construction and replication.
1986 Serizawa A 3-state von Neumann neighborhood rule capable of universal computation and construction. A quadratic self-replicator has not yet been implemented in this rule, but the latest archive includes Michael Simkin's linear self-constructing Geminoid puffer. http://gollygang.github.io/ruletablerepository/downloads/Serizawa_thumbnail.gif
2009 MRM CA A 4-state rule made by Paul Chapman to support Minsky Register Machines, up to and including universal MRMs. Included with this rule table is a .colors file and a sample MRM. The supplied MRM, also by Paul Chapman, calculates the nth prime. Paul Chapman has also built MRMs in Life, but they are naturally much slower than the ones in this specialised rule.

Lattice gases

A lattice gas is a cellular automaton used specifically to simulate a gas. Whereas actual gases operate in a 3-dimensional continuous space, lattice gases use a 2-dimensional discrete space. Interestingly, most of the properties of actual gases can be observed in lattice gases.

year rule description images
1973 HPP.table The HPP lattice gas can be simulated in the Margolus rule, but Brian Wylie showed how to simulate it with 16 states and the von Neumann neighborhood. TJH added another 16 'reflection' states to allow the rule to function in a bounded, non-toroidal space.
1981 Diffusion-limited aggregation Diffusion-limited aggregation using the HPP lattice gas. This model was studied to simulate the fractal growth characterised by electrolysis of copper sulphate.
2010 Pressure Pressure is a rule by Dean Hickerson, which is loosely based on gas particles exerting pressure on the walls of a chamber. http://gollygang.github.io/ruletablerepository/downloads/Pressure_thumbnail.png

Margolus neighborhood

The Margolus neighborhood is one of the simplest CA neighborhoods. A description of the rule can be found online, at this website. For each of the rules below, two different rule tables are supplied. One is the actual Margolus rule; the other is an emulation of it using a Moore neighborhood and extra states.

year rule description images
1981 DLA-Margolus.table, DLA-Margolus-emulated.table, DLA-Margolus-emulated.colors Diffusion-limited aggegation in the Margolus neighborhood.
1982 BBM-Margolus.table, BBM-Margolus-emulated.table, BBM-Margolus-emulated.colors Ed Fredkin's Billiard Ball Model in the Margolus neighborhood.
2009 Sand-Margolus.table, Sand-Margolus-emulated.table, Sand-Margolus-emulated.colors MCell's 'Sand' rule in the Margolus neighborhood. For a similar non-Margolus rule see Sand.zip. http://gollygang.github.io/ruletablerepository/downloads/sand-margolus.png

Hexagonal neighborhood

A number of people have explored various CA rules on a hexagonal grid, where each cell has 6 neighbors. This neighborhood can be emulated on a square grid by ignoring 2 diagonally opposite neighbors (e.g., the NE and SW corners).

year rule description images
1971 Hex-B2omS2 A 2-state non-totalistic CA on a hexagonal grid, by Ken Preston Jr. This rule was first described in LifeLine number 2 on page 15. The rule name uses Paul Callahan's notation (see below). http://gollygang.github.io/ruletablerepository/downloads/Hex-B2omS2.png
1984 Snowflake Contains a script for generating examples of Norman Packard's snowflake-like CA, described in this 1986 paper. An earlier description appears in Stephen Wolfram's article "Computer Software in Science and Mathematics" in Scientific American, Sept. 1984. http://gollygang.github.io/ruletablerepository/downloads/snowflake.png
1997 Hex-B2oS2m34 A 2-state non-totalistic CA on a hexagonal grid, by Paul Callahan. See Paul's excellent article describing the notation used in the rule name, and the many interesting objects he discovered (some are included in the zip file). http://gollygang.github.io/ruletablerepository/downloads/Hex-B2oS2m34.png
2003 HexBuss A 3-state totalistic CA on a hexagonal grid, by Frank Buss. See Frank's website for more details. http://gollygang.github.io/ruletablerepository/downloads/HexBuss.png

Triangular neighborhood

A triangular grid supports 2 possible neighborhoods. If only shared edges are allowed then each cell has 3 neighbors. If shared vertices are allowed then each cell has 12 neighbors (this results in more interesting rules). A triangular neighborhood can be emulated on a square grid by dividing each square into 2 triangles, so a 2-state triangular CA can be emulated using 4 states:

http://gollygang.github.io/ruletablerepository/downloads/triangular-emulation.png

year rule description images
1994 TriLife 2-state totalistic CA rules on a triangular grid are emulated by a 4-state CA. Based on the work by Carter Bays (see this applet). The zip file includes a script for generating TriLife-Bnnn...Snnn... rules, some example rules and patterns, a .icons file, and another script that counts the number of triangles in a TriLife pattern. http://gollygang.github.io/ruletablerepository/downloads/TriLife.png

For the general case, an emulation script is now available for rule tables that use the triangularVonNeumann or triangularMoore neighborhood (see RoadMap): Scripts/Python/RuleTableToTree.py (available in Golly 2.2 or later).

Langton's Ant and other Turing Machines

These cellular automata simulate Turing Machines, abstract entities that move on a discrete grid, altering the grid and changing direction. In the classical sense, a Turing machine uses a 1-dimensional grid; Langton's Ant uses a 2-dimensional grid.

year rule description images
1986 Langtons-Ant Langton's other famous system. An ant moves around an infinite universe, flipping the color of the squares it lands on and turning left or right accordingly. The ant moves chaotically for the first 10 000 steps, before settling into a sequence where it slowly migrates diagonally. This eventual fate is conjectured to be true of any initial setup. Wikipedia.
1995 n-color extension of Langton's Ant A script for creating examples in the n-color extension of Langton's Ant. This package also includes a sample pattern and rule. See the YouTube video. http://gollygang.github.io/ruletablerepository/downloads/LangtonsAnt-LLRRRLRLRLLR.png
1986? Ant counter Langton's Ant can be modified to count in binary, as shown in this MathWorld article. It is a special case of a Turmite, or 2-dimensional isotropic Turing machine. It only differs from Langton's Ant in that it moves forwards on a white square, rather than turning left. This 'counting ant' was discovered by Ed Pegg, Jr. http://gollygang.github.io/ruletablerepository/downloads/Turmite-BinaryCounter.png
1987 Turmites A Turmite is a 2D Turing machine; a generalization of Langton's Ant to n states and m colors. http://gollygang.github.io/ruletablerepository/downloads/Turmite8.png
1987 Absolute Turmites (2D Turing machines) While turmites store their orientation as part of their state, absolute turmites have no orientation. Fewer interesting examples are known. Included are some examples from Wolfram's NKS. More research here. http://gollygang.github.io/ruletablerepository/downloads/AbsoluteTurmites_thumbnail.png
2006 Iceskater A rule by Jordan Goldstein: "I wrote a rule table based on an idea I had about 2 years ago. ... It's similar to Langton's ant in that it walks around the board modifying a set of inactive cells; however, it never repeats itself and thus grows forever to become an large white blob of chaos. Enjoy---an explanation is included in the zip file." Email. It was later spotted that Iceskater is equivalent to Turmite #9 here.
2008 Worm-1040512.table, Worm-1042015.table, Worm-1042020.table, Worm-1252121.table, Worm-1525115.table Dean Hickerson's implementation of Paterson's Worms - The hexagonal neighborhood is emulated using the Moore neighborhood.
2009 BusyBeaver Adam P. Goucher has made a program to convert m-state n-symbol Turing machines into Rule Tables. The two example machines are Busy Beavers, Turing machines that try to write as many '1's as possible before halting. To run each machine in Golly, seed the universe with a single cell of state 2.
2009 Wolfram's Turing Machine This rule simulates Wolfram's 2-state 3-symbol Turing Machine, which was proven by Alex Smith to be universal. The rule displays all previous states of the machine, not just the current one.

Life-inspired CAs

This section contains rules based on Conway's Game of Life, the most popular CA.

year rule description images
1973 LifeColor A colored variant of the Game of Life, by François Boisson. link
2007 Life on the Edge and Slope Franklin T. Adams-Watters described a CA in which all the action occurs on the edges of a square grid. Each edge can be ON or OFF and has six neighbors, three at each end. An edge is ON in the next generation if exactly two of the edges in its seven edge neighborhood (including the edge itself) are on. Also provided is an implementation of the rule, rotated 45° so that only 2 live states are required. Email.
2007 History Life rules History Life rules performing functions such as highlighting cells that were ever alive and marking cells. Rule by Dave Greene, translation to a table by Adam P. Goucher. Read more...
2009 Life Pattern Emulators Two rules, one by Dean Hickerson and one by Adam P. Goucher, designed to simulate two of Dean Hickerson's transcendental Life patterns - the Clouds pattern and Prime number generator, respectively. Included are the rule tables, sample patterns and equivalent Life patterns.
2011 ExtendedLife Conway's Game of Life with a few extra special states. Idea and rule table by Martin Grant, a.k.a. "Extrementhusiast". http://gollygang.github.io/ruletablerepository/downloads/extendedlife.png
2012 MilhinSA 3 states, similar to Conway's Game of Life, by Sergei Milhin. Updated October 2014. http://gollygang.github.io/ruletablerepository/downloads/Steppers_Icon.png
2013 SlowLife A variant of Life that shows births (green cells) and deaths (red cells) in every 2nd generation. SlowLife patterns work the same as in Life, but twice as slow. http://gollygang.github.io/ruletablerepository/downloads/SlowLife.png

Miscellaneous

If there is a rule that doesn't fit into one of the above sections, nor does it warrant its own section, it goes here.

year rule description images
1970 Ed-rep In 1970, Terry Winograd proved that Fredkin's replicator CA (the parity rule B1357/S1357) could be extended to N states, as long as N is a prime number. Golly's demo pattern Ed-rep.rle shows a 7-color photo of Ed Fredkin that replicates itself. http://gollygang.github.io/ruletablerepository/downloads/Ed-rep.png
1987 Bak-Tang-Wiesenfeld sandpile model A simple 2D model of a sandpile was found to self-organize itself to criticality. Wikipedia http://gollygang.github.io/ruletablerepository/downloads/BTWSandpile.png
1989 Cyclic CA A rule investigated by David Griffeath. This rule is a very basic CA that shows competition emerging from a random initial seed. Wikipedia.
1992 Biham–Middleton–Levine traffic model A self-organizing cellular automaton traffic flow model. It consists of a number of cars represented by points on a lattice with a random starting position, where each car may be one of two types: those that only move downwards (blue), and those that only move towards the right (red). http://gollygang.github.io/ruletablerepository/downloads/bhl_traffic.png
1998 JustFriends A non-totalistic 2D binary rule by David Bell.
2001 The Photon-XOR system David Eppstein discovered this one-dimensional system whilst experimenting with the rule B25/S4. It exhibits pseudo-random walks, and can be simulated in O(n log n) time using an algorithm by Tomas Rokicki. By interpreting its walk in binary, it can be used as an (aperiodic) pseudo-random number generator. [Gabriel Nivasch's webpage]
2009 Tricky Bees A chaotic rule by Alan Tennant where each state becomes progressively more inert in which patterns are surprisingly tricky to construct. This table is actually 17 independent rules, which are combined into one rule table using an 'on' state for each rule.
2009 Maze Solver MazeSolver is a 13-state rule that solves any maze, using a flood fill method to locate the exit, before backtracking to the start to highlight the shortest possible route. MazeSolver2 is an extended version that uses the Moore neighborhood to allow diagonal filling and backtracking. The zip file contains the necessary tables, icons and colors, as well as example patterns and scripts for creating random mazes.
2009 Collatz emulator Dean Hickerson created this rule table for determining the number of iterations required for each positive integer to reach 1 in the Collatz conjecture. It is alternatively known as the 3n+1 conjecture or Ulam's conjecture. Coincidentially, Stanislaw Ulam inspired von Neumann to create cellular automata. http://gollygang.github.io/ruletablerepository/downloads/CollatzCA.png
2010 RepRoller A simple way of allowing any pattern to be replicated and triggered. http://gollygang.github.io/ruletablerepository/downloads/RepRoller.png
2010 Wave A cellular automaton by Keiji and metacell implemented within this rule.
2010 ReversibleLife Paul Nasca's Reversible Life rule, made using the second-order technique. http://gollygang.github.io/ruletablerepository/downloads/reversible_rule_paul.png
2011 Squaredance Squaredance is a rule by Dean Hickerson in which rectangles grow and shrink pseudorandomly. For more details, see readme.txt in the zip file. http://gollygang.github.io/ruletablerepository/downloads/Squaredance.png
2011 Sand A rule by Andrew Trevorrow that mimics falling sand. The zip file also contains a number of "sand guns" with various periods (thanks to Dean Hickerson). http://gollygang.github.io/ruletablerepository/downloads/Sand.png
2012 Snakes A rule by Dean Hickerson in which thin snake-like objects appear to move randomly. For more details, see README.txt in the zip file. http://gollygang.github.io/ruletablerepository/downloads/Snakes.png
2012 Ships By Alan Tennant. For construction of large 4 state ships. Based on discoveries in WWEJ3. http://gollygang.github.io/ruletablerepository/downloads/2dlkd55.png
2013 Pilot Pilot - rule with a 2-cell spaceship - it was meant to multiply by collisions and it showed up, that bigger soups are exploding. http://gollygang.github.io/ruletablerepository/downloads/Golly_Pilot_mini.png
2015 Waves Waves by Luís Câmara is a model of electromagnetic waves.
2016 Reversible World An emulator for the reversible elementary triangular partitioned cellular automaton No.0347 (ETPCA 0347) proposed by K. Morita. It is a very simple reversible CA, but yet shows complex behavior. It is computationally universal, since it can simulate reversible Turing machines.

Credits:

  • Langton's Loops, SDSR, Evoloop, Byl, Chou-Reggia 1/2: TJH used the fabulously readable implementation here: loops.java, with kind permission from Eli Bachmupsky and Hiroki Sayama. For SDSR and Evoloop, the rule tables were augmented with Java code, so the conversion routine linked-to above was used. In the Byl loop their rule table has an error: transitions 212052 and 212055 contradict each other - only the second is correct.
  • Banks, Tempesti: TJH copied the rules from their PhD theses, which you can find online
  • Codd: The XLife file linked above was the only record TJH could find. He converted it by hand. Update: He has just found a link to the scanned book (above), and it turns out that codd.r had a few crucial errors. It all works now.
  • JvN29, Nobili32, Hutton32, WireWorld: TJH started with the C++ implementations in Golly and used the conversion routine.
  • Langtons-Ant: TJH wrote by hand.
  • BBM: When TJH realised that we could emulate the Margolus neighborhood he wrote a Python script to convert from an MCell specification string to a .table file.
  • HPP: TJH was all set to make an emulated-Margolus rule for the HPP gas (since MCell has the specification) but then he came across a much nicer way of implementing it directly in a von Neumann neighborhood CA, so he followed that instead. He had to create reflection states, so it ended up with 34 states in total.
  • Perrier: Gianluca Tempesti sent TJH the rule table - thanks!
  • MRM: APG converted this rule from Paul Chapman's website.
  • WWE1, WWE2, WSwitch, Tricky Bees & Ships by Alan Tennant.
  • WWEJ and WWEJ2 by Mark Jeronimus.
  • WWEJ3 by Alan Tennant and Mark Jeronimus.
  • Emulators: Thanks to Andrew Trevorrow for cleaning up the files to work on case-sensitive file systems.
  • Codd-ICRA: Adam P. Goucher copied this rule from the .pdf document, amended and updated it.
  • Bak-Tang-Wiesenfeld sandpile model: created by Paul Nasca
  • MilhinSA by Milkhin Sergei
You can’t perform that action at this time.