1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to CS.SE! It's hard for me to tell what you are asking. What do you want to know? You ask how they work, but then it sounds like you have a good understanding of how they work. I'm not sure what "what it says actually?' is asking. Can you edit your question to add more context, share with us your current understanding, and identify what specifically you are confused about? Perhaps you might find the following background interesting: mathworld.wolfram.com/CellularAutomaton.html. $\endgroup$ – D.W.♦ Jul 8 '17 at 17:51
  • $\begingroup$ The problem is that I can't analyze and interpret the binary sequence of a 2DCA rule number. I can't understand how should implement a 2DCA when we have the rule number. $\endgroup$ – meshkati Jul 8 '17 at 18:06
  • 1
    $\begingroup$ Actually, you just want to know what is the numeration order for cells, don't you? $\endgroup$ – rus9384 Jul 8 '17 at 18:59
  • $\begingroup$ Which bit position corresponds to which cell is just a convention. There are multiple reasonable conventions one could use. I don't know if there's a standard convention. Does it matter? $\endgroup$ – D.W.♦ Jul 8 '17 at 19:08
  • $\begingroup$ So there isn't a unique implementation of a rule number and it depends on the rule convention? $\endgroup$ – meshkati Jul 8 '17 at 19:46
3
$\begingroup$

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)
Improve this answer
$\endgroup$

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.