Registered: Oct 2003
Posts: 167

I'm posting this here in the hope of getting others half as excited as I am by the discoveries to be found in some of these rules. After 27 years experimenting with cellular automata and other discrete systems, nothing else even gets close.

Some background. Around the turn of the millennium, Mirek Wójtowicz developed the MCell and MJCell cellular automata software in which he introduced the Generations rule family, seemingly as a generalisation from some previously known rules. Generations are totalistic Moore neighbourhood rules which make a singular extension to the widely used born/survives system of naming such rules in a two colour plane. (Conway's Life is b3s23.) Generations adds more colours, but in a very simple way which I have come to think off as dying states. When the neighbour count of a live cell determines that it does not survive, instead of going directly to the off/empty state, it first cycles through however many other colours are specified, in those states ignoring and being ignored by its neighbours.

At the time, Mirek clearly worked through many rules, identifying and naming quite a number he found interesting on his Generations page. In late 2008, support for Generations was added in Golly 2.0. and a cursory look at Mirek's site had his name "LivingOnTheEdge" (LOTE) grabbing my attention. Seventeen months later, much of it running LOTE 100,000 or more iterations from small seeds on three computers, I have a fresh take on the relationship between order and chaos, but that is another story. Early last month while searching for more context for that telling of that other story, I found myself back at the above-linked Generations page and opted for a quick look at the rule Mirek called "Star Wars" and was particularly enthusiastic about.

Within hours I had accepted that my life was not going to be long enough to do justice to Star Wars. It is the first rule I have worked with where testing Kauffman's notion of spontaneous catalytic closure might be conceivable. And while it is not my area of interest, the possibilities for engineering with Star Wars are far more obvious than they are for LOTE (although it also has a much stronger inclination to runaway growth to contend with). One quickly found, but to me still extreme, case sees a reaction between two common small objects producing three potentially useful mechanisms, more than enough to justify recording an animation.

One thing I can't get my head around is translating the compact and human readable Generations rule numbering convention into Mathematica. The rule numbers are actually in the form survives/born/colours where survives and born can be any number of the digits 0-8 and colours any number > 2. This structure also makes the idea of "adjacent" rules meaningful, something I've explored extensively for LOTE and minimally for Star Wars, yet enough to conclude that Mirek and a handful of others' original work identifying interesting rules had been substantial.

Star Wars is 345/2/4
LOTE is 345/3/6

The only seed I am occasionally running on with Star Wars is based on a very common growing diamond but modified to eliminate the normal double symmetry and thus quadruple the results obtained per computer cycle (paste the following lines into Golly):

x = 12, y = 7, rule = 345/2/4
ABC$ABC.A$2.ABCBA$3.ABCBA$5.ABCBA$7.A.CBA$9.CBA!

I've been of the opinion for a while that LOTE is comfortably beyond the threshold of emergent productivity that Wolfram's hypothesised fundamental rule needs. Star Wars ups that level considerably. It now seem weird that only 18 months ago I had no expectation that cellular automata would ever provide more than simplified demonstrations of emergent possibility. That has proven to be just plain wrong, although I'm still confident that, if there is a fundamental discrete mechanism at the bottom of the world we find ourselves in, it will not be a mechanism that can be efficiently represented as a CA.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The simplest way is to use a general function because in general these are not outer totalistic. For states 0 and 1 the rule is similar but for states >1 they do not affect the firing of neighboring cells, and themselves transition 2->3->4...->max->0.

E.g. the Star Wars rule is CellularAutomaton[{Switch[#[[2, 2]], 
0, Count[#, 1, {2}] /. {2 -> 1, _ -> 0},
1, Count[#, 1, {2}] /. {3 | 4 | 5 -> 1, _ -> 2}, 2, 3, _, 0] &,
{}, {1, 1}}, {RandomInteger[3, {10, 10}], 0}, 20]

and the LOTE is CellularAutomaton[{Switch[#[[2, 2]], 
0,Count[#, 1, {2}] /. {3 -> 1, _ -> 0},
1, Count[#, 1, {2}] /. {3 | 4 | 5 -> 1, _ -> 2}, 2, 3, 3, 4, 4, 5, _, 0] &,
{}, {1, 1}}, {RandomInteger[5, {10, 10}], 0}, 20]

starting from a random 10x10 block for 20 steps. Attached are such evolutions out to 150 steps.

Todd Rowland has attached this image:

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Thanks for that, Todd.

Would you be able to do a hopefully quick enough bench mark to show whether or not Mathematica's inherent overheads make it too slow to do much useful work with this class of cellular automata?

With the LOTE rule, instead of starting with RandomInteger[3, {10, 10}] could you instead use the ubiquitous "natural" seed:
0 0 0 1 1 1
0 0 0 1 2 1
0 0 0 1 1 1
1 1 1 0 0 0
1 2 1 0 0 0
1 1 1 0 0 0
Using Golly 2.1 running at step size 8^1 with my custom version of goto.pl, this takes 100 seconds to run 10,000 iterations on my aging 2.16 GHz 24 inch iMac with 2Gb RAM running Snow Leopard and with all my usual applications active in the background. (Viable LOTE patterns typically start to get more interesting either side of 100,000 iterations.)

At 10,000 iterations, the pattern above has a population of 96,560 live+dying cells.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 4

Hi Tony,

I guess Brian's Brain http://en.wikipedia.org/wiki/Brian%27s_Brain
is one of these 'generations' type of CA?

It is interesting that the complexity is certainly a step up from the standard 'Life' CA.

The reason why I mention Brian's Brain is that the analogy of the extra states ('dying') is with the 'refractory' period of a neuron after the firing, hence the 'brain'. This interested me to ask the question: Is the refractory period of neurons essential to create complexity in biological Brains? From the brief reading I have done about this, it seems like this question isn't considered. I think it is assumed that a refractory period is there because a neuron needed time to rest and recharge. However this might be the wrong way to look at it....for surely if neural networks performed better without refractory periods then evolution would have found a way for neuron not to 'need' this rest!?

If this hypothesis is correct - that refractory periods in neural networks are key to the type of complex behaviour they display, and not (just) a biological necessity - then we should incorporate this 'state' into our simplifed neural network models...Looking into the literature, I don't think this is done currently!?

This could lead to new far more powerful neural network software..unfortunately I don't have the ability to take these ideas forward....

All the best

Dave

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Dave, as far as I can read the history it appears that the Generations rule family was conceived as a generalisation of Brian's Brain in particular.

Generations seems to me to be a naturalistic way to expand the rule space a bit more productively than just increasing the number of colours and looking at the much larger space of all possible rules.

Clearly the neural refractory period is an informative analogy, but it is far from unique in that respect amongst biological processes. The idea that a site which ceased to be active would need a period out of play before it could be reactivated even applies to the likes of wildfire,

There is quite a bit in common between Brian's Brain and Star Wars as both are B2 rules. The difference is a result of S345 giving Star Wars the ability to build persistent structures of live cells, corners of which often provide sites for glider guns. I'm running the originally mentioned seed on from time to time, having recently reached 46,000 iterations with no sign as yet that the structures may eventually join up sufficiently to divide the universe into separate cells.

The growing diamond shapes are common to both rules and can be minimally seeded by a single domino. One thing I did quickly find that may be peculiar to Brian's Brain were common enough diagonal ships which move at (c/4, c/4):
x = 3, y = 4, rule = /2/3
2.A$.2B$A.A$B!
being produced by guns moving at c and thus forming into lines with slopes of 1 in 5 or 1 in 3. Diagonally symmetric patterns in LOTE have a particular mechanism which often forms ships in a (pair of) 1 in 3 sloping line(s) but I can't recall seeing anything similar at 1 in 5, though that could just be my aging neurons.

I suspect there might be a few more complex possibilities hidden away in the Generations rule space, as well as a lot to be learnt by long iteration runs of particularly interesting rules, though I don't recommend anybody tries to tackle LOTE from scratch without at least an order of magnitude more computing capacity than I've been able to throw at it. A couple of suggestions for anyone so inclined:

• start with asymmetric seeds, at least until you can afford the 2/4/8 times effective reduction of results per computer cycle that symmetry brings
  
• snapshot at generation numbers based on powers of two rather than the powers of ten I slipped into by default as it should make presentations based on Maps tiling technology a bit easier
  
• and maybe try to be a bit more consistent than I've been able to be in your method of defining the zeroth generation of a seed, most of mine being collision products

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Not Yet
Posts: N/A

Thank you so much for this information and useful clarification

Report this post to a moderator | IP: Logged