Registered: May 2006
Posts: 4

Hi This is my first post on here so I'm a bit embarrassed to be asking for hardcore info....

What it is is that I am investigating the rule shapes in a 2 by 3, 6 cell neighbourhood, trying to asses whether the overall complexity of a rule shape follows some pattern (the 'no-incest condition', but more on this in later posts!)

Anyway, for example there are 15 ways to create 4-cell 'parent' CAs out of the 6 cell block. And each of these 15 shapes have 65536 binary CAs associated with them. So I am looking for an algoithm, or even better, code that can give me a rough measure of the complexity of each CA, so that I can get a fairly good relative measure of a rule-shape's complexity. Currently I have been doing this by eye but because of the CA space size of course I've only been able to take a sample (500 for each of the 15).

Can anyone please help with some tasty programming advice!

All the best,
Dave Jones

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Welcome.

I'm afraid what you have said so far is not remotely clear enough to address your question. I'll guess about what you are trying to do and then you can correct me if I am wrong.

I get that you have a space of rules that depend on a six cell neighborhood. I presume by "2 by 3" you mean this is a 1D system that depends on nearest neighbors and the current and previous step in time. In the Mathematica scheme of things, that means a k=2, r=1, s=2 CellularAutomaton. S being an optional fourth argument to the first argument of the CellularAutomaton function, allowing dependence on prior steps in time.

When you say "rule shape", I assume you mean some sort of pattern satisfied by different slices through the whole space of such rules. The whole space is 2^2^6 rules, which is about 1.8x10^19 rules all told. Clearly that is far too large a space to look at them all, so whatever you do you will be sampling. Any large subset of that large a space will have its own variety rather than one specific complexity class etc.

So that other people have some idea what we are talking about, here are a few lines of Mathematica for looking at these -

numrules = 2^(2^6);

With[{rule = RandomInteger[numrules - 1]}, 
 ArrayPlot[CellularAutomaton[{rule, 2, 1, 2}, {{{1}, {1}}, 0}, 
{{-1, 100}, All}], PlotLabel -> rule]]


That evolves a random one of these from the simple initial condition of 2 steps of {1} in a field of 0s, for 100 steps. Notice the form of the last argument, with the steps to be returned starting at -1 - that let's us see the whole initial condition as the first 2 lines.

From random initial conditions you would instead use -

With[{rule = RandomInteger[numrules - 1], 
  randominit = Table[RandomInteger[{0, 1}, 100], {2}]}, 
 ArrayPlot[CellularAutomaton[{rule, 2, 1, 2}, randominit, 
{{-1, 100}, All}],   PlotLabel -> rule]]

One additional test or display method I like to use is to see the time series you get by treating 1s as +1 and 0s as -1 and totaling across each line of the array, as Wolfram does in his stock model. The idea is that class 2 behavior shows up very clearly in such a "reduced mapping", and one can see the sort of "noise" the system gives. Here is a way to do that in Mathematica terms -

series[table_]:= (# - First[#]) &[Total /@ (table /. (0 -> -1))]

With[{rule = RandomInteger[{0, numrules - 1}], 
  randominit = RandomInteger[{0, 1}, 100]},
    Row[{ArrayPlot[
    Take[#, -100], PixelConstrained -> 3, PlotLabel -> rule], 
    ListLinePlot[series[#], ImageSize -> 300]}]&
        [ CellularAutomaton[{rule, 2, 1, 2},  
          randominit, {{-1, 200}, All}]
    ]
]

Where I've taken only the last 100 steps for the ArrayPlot, to keep the image similar in size to the time series representation.

Just as a side note, these are funky, I like them. Most seem to do complicated things, with a smattering of class 2s.

Report this post to a moderator | IP: Logged

Registered: Oct 2005
Posts: 403

I think also what Mr. Jones is looking for is: what's the state of the art in terms of mechanical classification of systems into various buckets based on complexity level?

For people running a whole bunch of systems whose rules have a certain shape, or people looking at sets of systems with some other set of characteristics, we'd like to be able to mechanically classify the generated system output by complexity, to make it possible to programmatically search for characteristics of rules that lead to systems of a certain complexity...or to mechanically verify theories about the relationships between characteristics of rules and the systems they're likely to generate, or capable of generating.

Can folks here advise about the state of the art of such mechanical classification?

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 4

Hi Jason,
Sorry that my previous post was not very clear and thanks very much
for your reply – it was very useful. I can see that the 'reduced
mapping' idea might be what I'm looking for. It gives a sequence of
numbers that should have properties that will roughly be able to sort
out a group of CAs in order of complexity.

A first thought I had was this: produce some CA with random initial
conditions in a grid say 150 by 150. Then sum across rows in the way
you suggest (0s as -1 and 1s as +1). So now there is a sequence of 150
numbers, some negative some positive: s1,…., s150. Now take the mean,
M. Then form a new sequence s1-M, s2-M,...., s150-M. Now take the
modulus and sum: |s1-M|+|s2-M|+....+|s150-M| - this figure should be a rough measure of complexity because it's a rough measure of variance of the rows. This figure should be (very often) smallest for simple CAs higher for class 2 and highest for class 3s and 4s (all with
random initial conditions, with a grid 'stitched' together at the sides).
This may be a rough measure but might be all I need (have tried this
in Excel and it seems to work reasonably well on a 150by150 grid; will post examples soon perhaps).

--------------

Thanks for the Mathematica Code but I wonder whether Mathematica can
set up the kind of rule-shapes I have in mind (below)?…..

As you say, I think of rule-shapes as being slices through the whole
rule-space. And of course no one slice will have all one class of complexity. But is it interesting to find that some rule-shapes have significantly more complex-looking CAs than others?

e.g why should the 'Y' shape have more complex CAs than this 'diamond' shape.?? (See picture below; the black squares are 'parents' to green square 'offspring') Because I've found that this 'Y' shape is very much more complex than the 'diamond' shape….I mean by this that when you look at the 256 CAs of each shape one set just looks VERY much more complex on the
whole.

All the best, and once again many thanks,
Dave

Dave has attached this image:

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 4

...you put it alot clearer than me....

Report this post to a moderator | IP: Logged