RuleTableRepository

Sq3Home | RecentChanges | Preferences

Difference (from prior minor revision) (no other diffs)

Changed: 1,77c1

Rule Table Repository




There didn't seem to be a central place to find cellular automata (CA) rule tables, so I thought I'd make one. All of the rule tables here are free to use for any purpose.

Many of these rule tables are links into Golly's codebase, others exist only here. Several of these rules have never been seen as rule tables before now, in particular: JvN29, Nobili32, SDSR and Evoloop.

The Rule-Tables:




|| year || rule tables available || description || links ||
|| late 1940's || [JvN29.table] || John von Neumann's original 29-state CA. || [1] ||
|| 1968 || [Codd.table] || Edgar F. Codd simplified von Neumann's CA to 8 states. || [2][3] ||
|| 1971 || [Banks-I.table], [Banks-II.table], [Banks-III.table], [Banks-IV.table] || Edwin Roger Banks made CA that supported universal computation and construction, using fewer states than before. || ||
|| 1973 || [HPP.table] || The HPP lattice gas. || [4] ||
|| 1982 || [BBM.table] || Ed Fredkin's Billiard Ball Model. Here we are emulating the Margolus neighbourhood using a Moore neighbourhood and some extra states. || [5] ||
|| 1984 || [Langtons-Loops.table] || Chris G. Langton extended Codd's rules to allow a totally novel form of simple self-replicator - the loop. || [6] ||
|| 1986 || [Langtons-Ant.table] || Langton's other famous CA. || [7] ||
|| 1987 || [WireWorld.table] || Brian Silverman's famous CA for electronic wiring. || ||
|| 1989 || [Byl-Loop.table] || J. Byl managed to reduce the size of Langton's Loop. || ||
|| 1993 || [Chou-Reggia-1.table], [Chou-Reggia-2.table] || A further reduction of Langton's Loops - down to just five cells. || ||
|| 1994 || [Nobili32.table] || Renato Nobili's extension of von Neumann's 29-state CA to allow easier crossing of wires, leading to enormously simpler machines. || ||
|| 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". || ||
|| 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. || ||
|| 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. || ||

More Rule Tables:



|| 2008 || [Hutton32.table] || (Self-promotion alert!) This is a modification of Nobili32 that I came up with, to allow simpler construction and rotational invariance. || ModJvN ||

Submission procedure:




*Attach .table files and mail to: [tim.hutton@gmail.com].
*Ruletree (.tree) files, .icons and .colors (Golly-specific things) are very welcome.
*I'm most interested in CA that are discussed in published papers, but you can send in any rule tables of your own invention too.



About the .table format




There are other CA rule table formats out there. The simplest is just to list the transitions. Codd and Langton used this method, where e.g. 012345 stands for the transition:

1
4 0 2 ---> 5
3

The inputs are given in the order: centre, north, east, south, west, followed by the updated centre state. For CA that only use states 0-9, no separator is required, so each transition is just a sequence of 6 digits. The .table format supports this, and also the Moore neighbourhood version: C,N,NE,E,SE,S,SW,W,NW,C'. For CA with more than 10 states, commas are used to separate the entries.

Rather than list every transition, we can skip transitions that make no change to C. We can also skip transitions that are rotated or reflected versions of ones already listed. (More on this later.)

However, for more complex CA, including von Neumann's original 29-state CA, this is not sufficient. Too many transitions would have to be listed. Most CA programs get around this by hard-coding the transition tables, as C++ or Java or whatever. This is fine and good but not future-proof. If someone gave you a stack of rules for your new CA engine you'd have to carefully translate each one into your desired language.

A different problem was encountered when considering some other rule table formats: [CDL], cellang (I've never seen any details but I think it's not dissimilar) and CAXL (likewise). CDL, for example, is an entire programming language, and adding support for this to your favourite CA program would be a significant amount of work. There has to be a simpler way to encode rule tables that is both reasonably compact and easy to understand and use, for the majority of popular CA rules. And there is!

The XLife program has the .r format, e.g. [8], where square brackets are used for multiple states. E.g. 0000[45]0 stands for the transitions 0,0,0,0,4 -> 0 and 0,0,0,0,5 -> 0. This is a big leap forwards, allowing rule tables to be expressed in a reasonably compact form. The problem is that it doesn't provide enough compression.

The adopted solution can be found in Gianluca Tempesti's thesis: [9] - using variables to stand for multiple states. Then, e.g. for a={1,2,3}, the rule 1,a,3 -> a would stand for three rules at once: 1,1,3 -> 1 and 1,2,3 -> 2 and 1,3,3 -> 3. This method gives all the compression of the XLife approach and then some more on top.

Enough introduction, on to the specification:

See here: [.table format specification]

Producing rule tables




There's an reasonably easy way to produce compact rule tables in this form from an existing implementation - merging. In the XLife example above it is easy to see that the two transitions can be merged into the combined version. To convert a C++ transition function, we just have to work through all the possible inputs, merging their transitions into the growing list of rules as we go.

There is some code in the Golly distribution for achieving this: [make-ruletable.cpp]. I'm certain that it could be improved to give much better compression, so please have a look at it.



Sources:



*Langton's Loops, SDSR, Evoloop, Byl, Chou-Reggia 1/2: I used the fabulously readable implementation here: [10], 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: I copied the rules from their PhD theses, which you can find online
*Codd: The XLife file linked above was the only record I could find. I converted it by hand. Update: I've 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: I started with the C++ implementations in Golly and used the conversion routine.
*Langtons-Ant: I wrote by hand.
*BBM: When I realised that we could emulate the Margolus neighbourhood I wrote a [python script] to convert from an [MCell specification string] to a .table file.
*HPP: I was all set to make an emulated-Margolus rule for the HPP gas (since MCell has the specification) but then I came across a much nicer way of implementing it directly in a von Neumann neighbourhood CA, so I followed that instead. I had to create reflection states, so it ended up with 34 states in total.
Now hosted here: http://code.google.com/p/ruletablerepository

Now hosted here: http://code.google.com/p/ruletablerepository

Sq3Home | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited November 24, 2008 10:58 pm by Tim (diff)
Search:

Google
 
Web www.sq3.org.uk