7
$\begingroup$

Where can I find documentation of the rule number convention for CellularAutomaton for higher than 1 dimension?

I understand the convention for elementary 1D automata, but I don't understand even why Conway's Game of Life is 224 am not certain how to calculate the number (even if the number is very big) for, say, a certain 7-state 2D automaton that depends only on a weird neighborhood.


Edit:

I think I understand how the rule for Conway's Game of Life works now. For reference, it's {224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}}. The form for the rule is {n,{k,{wt 1,wt 2,...},rspec} (where by documentation's convention, rspec means {r 1,r 2,...}).

In this case, we have the rspec as {1,1} which means that each cell depends on the (2*1+1)x(2*1+1) neighborhood of it (the standard 3x3 box). The lone {2,{{ tells us that there are two states, which are implicitly 0 and 1.

The matrix {{2,2,2},{2,1,2},{2,2,2}} tells us how each cell in the neighborhood is weighted: if the center cell is state 1 it adds 1*1=1 to the total, and if a surrounding cell is state 1 it adds 1*2=2 to the total.

Luckily, the new state depends only on this weighted total: If there are two surrounding 1s and the center is 1, the total is 5, which means survive. If there are three surrounding 1s and the center is 0, the total is 6, which means birth. If there are three surrounding 1s and the center is 1, the total is 7, which means survive. If the total is 4, there are two surrounding 1s and the center is 0 then the center stays dead. If the total is more than 7 or less than 4, there are more than three or less than two surrounding 1s, and that means the center cell will become dead (state 0).

Therefore, for all possible totals between 0 and 8*2+1=17, the new states are 0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0. Since 0 will always be the least possible total, it's a nice convention to reverse this list and treat it as the binary number 000000000011100000, which in base 10 happens to be 224.


I would still like to know for sure how this generalizes to more states (higher base?), and how this is calculated for "neighbors at specified offsets".

$\endgroup$
6
$\begingroup$

Short answer

Understand how the neighborhood cells are ordered. In many cases RulePlot helps. Take for example an obscure 2-color outer totalistic Moore rule:

RulePlot[CellularAutomaton[{110, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}]]

enter image description here

Read single cells, white as 0, black as 1s, in order:

top->bottom left->right, or columns left->right

enter image description here

You get your number

FromDigits[{0, 0, 0, 1, 1, 0, 1, 1, 1, 0}, 2]

110

For Game of Life (GoL), the same schema works like:

RulePlot[CellularAutomaton[{224, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}]]

enter image description here

FromDigits[{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0}, 2]

224

Long answer

This actually also depends on the type of neighborhood, not only dimensionality: Moore or Von Neumann, and also on whether rule is totalistic, outer-totalistic or general. For GoL you got 2D outer-totalistic CA with Moore neighborhood.

But independently of all these characteristics it all comes down to how you order your tuples. CellularAutomaton follows CA's conventions described in NKS book, with 1D case clearly stated on page 53

enter image description here

To generalize to higher dimensions lets first recreate this with this 1D case of CellularAutomaton function, and then generalize the schema to 2D.

First get Tuples - important - watch the order {1,0} to correspond NKS convention (see image above, 1s are black):

Tuples[{1, 0}, 3]
ArrayPlot[{#}, Mesh -> All, ImageSize -> 30] & /@ %

{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}, {1, 0, 0}, {0, 1, 1}, {0, 1, 0}, {0, 0, 1}, {0, 0, 0}}

enter image description here

Evolve each neighborhood 1 step and get central cells using rule 30:

CellularAutomaton[30, #][[2]] & /@ Tuples[{1, 0}, 3]

{0, 0, 0, 1, 1, 1, 1, 0}

and that is 30's binary representation:

FromDigits[{0, 0, 0, 1, 1, 1, 1, 0}, 2]

30

or vice versa:

IntegerDigits[30, 2, 8]

{0, 0, 0, 1, 1, 1, 1, 0}

There is a beautiful recent V11 function RulePlot:

RulePlot[CellularAutomaton[30]]

enter image description here

And that should help you to understand how tuples are ordered in higher dimensions. Actually, going from 1D to 2D should help you to understand tuples ordering. A general 2D rule with Moore neighborhood:

RulePlot[CellularAutomaton[{23571113171923, 2, {1, 1}}]]

enter image description here

So now when you know how 2D tuples are ordered you can work out the same rule number from binary as we did for 1D case. It works so well it is mesmerizing, just watch the rule number reappear. Start from Tuples - magic of it is - Tuples order very properly the neighborhood. Get all 2D 3x3 Moore neighborhoods and check a few firs and last ones:

tup = Tuples[{1, 0}, {3, 3}];
ArrayPlot[#, Mesh -> All, ImageSize -> 30] & /@ tup[[;; 13]]
ArrayPlot[#, Mesh -> All, ImageSize -> 30] & /@ tup[[-13 ;;]]

enter image description here

So it is exactly in the order shown by RulePlot above. Now the magic:

rule=23571113171923;

recover=FromDigits[CellularAutomaton[{rule,2,{1,1}},#][[2,2]]&/@
Tuples[{1,0},{3,3}],2]

rule===recover

23571113171923

True

So that's your method to figure out any case.

Remember RulePlot, it works with a bunch of cool stuff, like, for example, a totalistic two-dimensional cellular automaton with hexagonal neighbors:

RulePlot[CellularAutomaton[{56, {2, {{1, 1, 0}, {1, 1, 1}, 
{0, 1, 1}}}, {1, 1}}], Appearance -> "Hexagons"]

enter image description here

or Turing machines:

RulePlot[TuringMachine[{596440, 2, 3}]]

enter image description here

etc. - probably will be expanded in future.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your detailed answer. Ruleplot (and its documentation) help a lot. To make this a definitive reference, could you add information about how the encoding works for "more states" (I understand this), for dimensions higher than 2 where ruleplot won't help (I have an educated guess), how this is calculated for "neighbors at specified offsets" (I think I could guess), and how to handle more general rules that are not based on adding up a weighted total? I could probably experiment and submit my own answer addressing these, but I figure you get priority and explained the basics well. $\endgroup$ – Mark S. Aug 10 '17 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.