How 2d cellular automata rules works?

Question

How 2D Cellular Automata rules sequences works? For example, in elementary cellular automata, when we look at the binary sequence of the rule number, we understand that first bit says if all neighbors are white, and the cell itself is white, the cell in next step is black or white ( depend on the value of the bit ).

But how should I analyze and interpret the binary sequence of rule number? How should I implement the 2D CA when I have the rule number, for example when we have rule number 22369621 with r = 2 ( 25 neighbors ) how can I understand the behavior of this 2D CA to implement that?

Answer 1

When we interpret CA rules in a canonical form bijective with the naturals, it's convienient to think in terms of a lookup table array indexed by a neighborhood into the next cell state, or rather a truthtable with a variable from each of the neighborhood cells.

This works when the number of states is a power of two. If not a power of two, you need to use a mixed-radix encoding to remain bijective with the naturals.

The choice of 22369621 as an example rule hints that you haven't fully grasped how many potential rules there are with a neighborhood of 25 binary state cells mapping into the next binary state center cell. I assume this rule was chosen because its length up to the most significant one is 25, which shows you might be thinking that it only requires 25 bits to fully encode any rule from this type.

However, 25 (2-state) neighbors -> 1 (2-state) center cell requires in the worst case 2^25 bits, not 25.

Let's take a more simple example from the von Neumann neighboorhood: 5 (2-state) neighbors -> 1 (2-state) center. This requires at most 32 (2^5) bits.

So now let's take a random number within 32 bits, such as 3427859663.

In binary this is 11001100010100001111110011001111. We can intrepret these 32 bits as the next cell lookup for each of the configurations those 5 cells in the neighborhood can be in:

  a        *
b c d -> * f *
  e        *

~a ~b ~c ~d ~e ->  f
~a ~b ~c ~d  e ->  f
~a ~b ~c  d ~e -> ~f
~a ~b ~c  d  e -> ~f
~a ~b  c ~d ~e ->  f
~a ~b  c ~d  e ->  f
~a ~b  c  d ~e -> ~f
~a ~b  c  d  e -> ~f
~a  b ~c ~d ~e -> ~f
~a  b ~c ~d  e ->  f
~a  b ~c  d ~e -> ~f
~a  b ~c  d  e ->  f
~a  b  c ~d ~e -> ~f
~a  b  c ~d  e -> ~f
~a  b  c  d ~e -> ~f
~a  b  c  d  e -> ~f
 a ~b ~c ~d ~e ->  f
 a ~b ~c ~d  e ->  f
 a ~b ~c  d ~e ->  f
 a ~b ~c  d  e ->  f
 a ~b  c ~d ~e ->  f
 a ~b  c ~d  e ->  f
 a ~b  c  d ~e -> ~f
 a ~b  c  d  e -> ~f
 a  b ~c ~d ~e ->  f
 a  b ~c ~d  e ->  f
 a  b ~c  d ~e -> ~f
 a  b ~c  d  e -> ~f
 a  b  c ~d ~e ->  f
 a  b  c ~d  e ->  f
 a  b  c  d ~e ->  f
 a  b  c  d  e ->  f

Besides the approach of luts for CA, there are other data structures (or canonical numberings) that tend to remove the redundancies found in the most relevant designed rules that utilize large neighborhoods and especially non-power-of-two states. A good resource for more information about these techniques can be found at the Golly webpage.

http://golly.sourceforge.net/Help/formats.html

Some techniques listed there are:

• Rule tables
• Rule trees (also known as n-ary decision diagrams)