How to calculate CellularAutomaton rule numbers in higher dimensions?

Question

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".

Answer 1

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}}]]

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

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

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}}]]

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

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}}

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]]

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}}]]

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 ;;]]

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"]

or Turing machines:

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

etc. - probably will be expanded in future.

Answer 2

I had the same question, even after reading Vitaliy Kaurov's extremely long answer. I found a publication on stephenwolfram.com with this text:

A cellular automaton consists of a regular lattice of sites. Each site takes on $k$ possible values [...]

Here we often consider the special class of totalistic rules, in which the value of a site depends only on the sum of the values in the neighborhood: $$ a^{(t+1)}_{i,j} = f[a^{(t)}_{i,j} + a^{(t)}_{i,j+1} + a^{(t)}_{i+1,j} + a^{(t)}_{i,j-1} + a^{(t)}_{i-1,j}] \qquad\textrm{(1.3)} $$ These rules are conveniently specified by a code: $$ C = \sum_n f(n)k^n \qquad\textrm{(1.4)} $$ We also consider outer totalistic rules, in which the value of a site depends separately on the sum of the values of sites in a neighborhood, and on the value of the site itself: $$ a^{(t+1)}_{i,j} = \tilde{f}(a^{(t)}_{i,j}, a^{(t)}_{i,j+1} + a^{(t)}_{i+1,j} + a^{(t)}_{i,j-1} + a^{(t)}_{i-1,j}) \qquad\textrm{(1.5)} $$ Such rules are specified by a code $$ \tilde{C} = \sum_n \tilde{f}[a,n]k^{kn+a} \qquad\textrm{(1.6)} $$

(The mismatching of square and round brackets is in the original. Also I believe equation 1.6 should have $a,n$ in the subscript, where it currently has only $n$.)

So for the Game of Life, we would set $k=2$ and

$ \qquad \tilde{f}(0,3) = 1 \\ \qquad \tilde{f}(1,2) = 1 \\ \qquad \tilde{f}(1,3) = 1 $

which means

$ \qquad \tilde{C} = 2^{2\cdot 3+0} + 2^{2\cdot 2+1} + 2^{2\cdot 3+1} \\ \qquad \tilde{C} = 2^6 + 2^5 + 2^7 = 224 $

So the Game of Life can be described in Wolfram's notation as an "outer totalistic CA with code $\tilde{C} = 224$." However, this is utterly different from a "totalistic CA with code $C = 224$"! And there are many other ways to describe the Game of Life, too; for example, the one you posted with the big curly-braced matrix.