Equivalence of codes in k-color totalistic cellular automaton​
​by Keith Stendall
Introduction​
​This post is a simple expression of my recreational exploration of all things related to k-color one dimensional totalistic cellular automata.​
​It doesn't carry an intellectually high burden and I hope it will be of interest to a wide spread of the Wolfram community.​
​I would appreciate any feedback, good or bad.​
​​
​Topics explored​
​For one dimensional totalistic cellular automata it can be shown that the 16 codes for 2-color totalistic CA have equivalent codes of 3-color and 4-color totalistic CA that produce identical results as shown in the grid below.
In[21]:=
Grid[{{2color,3color,4color},{0,0,0},{1,1,1},{2,3,4},{3,4,5},{4,9,16},{5,10,17},{6,12,20},{7,13,21},{8,27,64},{9,28,65},{10,30,68},{11,31,69},{12,36,80},{13,37,81},{14,39,84},{15,40,85}},FrameAll]
Out[21]=
2color
3color
4color
0
0
0
1
1
1
2
3
4
3
4
5
4
9
16
5
10
17
6
12
20
7
13
21
8
27
64
9
28
65
10
30
68
11
31
69
12
36
80
13
37
81
14
39
84
15
40
85
The values of the equivalent codes in the grid can be validated by manipulating the following three RulePlot figures for 2, 3 and 4-color 1-D totalistic CA
​
In[13]:=
Manipulate[RulePlot[CellularAutomaton[{c,{2,1}}],ColorRules{0White,1Gray}],{c,0,15,1}]
Out[13]=
​
c
In[14]:=
Manipulate[RulePlot[CellularAutomaton[{c,{3,1}}],ColorRules{0White,1Gray,2Red}],{c,0,2186,1}]
Out[14]=
​
c
In[15]:=
Manipulate[RulePlot[CellularAutomaton[{c,{4,1}}],ColorRules{0White,1Gray,2Red,3Black}],{c,0,1048575,1}]
Out[15]=
​
c
For example, the following 3 plots demonstrate that the 2-color code 9 generates the same results as the 3-color code 28 and the 4-color code 65
In[31]:=
ArrayPlot[CellularAutomaton[{9,{2,1}},{{1},0},50],ColorRules{0White,1Gray}]
Out[31]=
In[13]:=
ArrayPlot[CellularAutomaton[{28,{3,1}},{{1},0},50],ColorRules{0White,1Gray,2Red}]
Out[13]=
In[14]:=
ArrayPlot[CellularAutomaton[{65,{4,1}},{{1},0},50],ColorRules{0White,1Gray,2Red,3Black}]
Out[14]=
In fact, we could have predicted which 2 and 3-color rules would be equivalent by means of a simple change of base.
First convert the 2-color decimal code number to the base 2 representation then convert this result to base 3 and base 4.
In[15]:=
BaseForm[9,2]
Out[15]//BaseForm=
1001
2
In[16]:=
3^^1001
Out[16]=
28
In[19]:=
4^^1001
Out[19]=
65
So it now becomes a simple task to determine codes for 1-D totalistic CA that produce the same results using different numbers of colors.
As an example, consider the very complex 3-color 1-D totalistic CA with code 1599 (NKS p70) that is equivalent to the 4-color 1-D totalistic CA with code 8584.
In[18]:=
BaseForm[1599,3]
Out[18]//BaseForm=
2012020
3
In[11]:=
4^^2012020
Out[11]=
8584
In[22]:=
ArrayPlot[CellularAutomaton[{1599,{3,1}},{{1},0},400],ColorRules{0White,1Gray,2Black}]
Out[22]=
In[25]:=
ArrayPlot[CellularAutomaton[{8584,{4,1}},{{1},0},400],ColorRules{0White,1Gray,2Black,3Red}]
Out[25]=
For 1-D totalistic CA in general, the outputs for all k-color codes can be reproduced by codes using more colors.
So it can be seen that the results of all 2-color 1-D totalistic CA are a subset of the results of 3-color 1-D totalistic CA that are themselves a subset of the results of 4-color 1-D totalistic CA . . .
​
By itself, this fact isn't a great deal of use to me.
If I couple this fact with an observation I have made about clustering of interesting behaviour it may have some potential.
I have noticed that across the vast empty prairies of cellular automata, interesting behaviour often appears in clusters of a dozen or so codes.
I know this isn't very scientific and I have no explanation for this clustering effect.
So I have put this to the test.
We know from work carried out in NKS that code 1599 is extremely complex.
Also there are other codes that are near neighbours to 1599 that also show interesting behaviour.
I have shown above that the 3-color code 1599 produces the same results as the 4-color code 8584.
So I ran codes 8578 to 8583 and codes 8585 to 8590 to see if I found any interesting behaviour.
Interesting behaviour was found in codes 8578, 8579, 8580,8583,8587,8588,8599.
Let's take a look at code 8588 and 8587.
Maybe I just got lucky with that particular code so lets try 3-color code 2049.
The 4-color code 10536 produces the same results.
So again I ran a range of codes centred on code 10536 looking for interesting behaviour.
Interesting behaviour was found in codes 10532 and 10540.
Let's take a look at these.
Next steps​
​I'll take this forward to discover whether I can identify those 4-color 1-D totalistic CA with interesting behaviour by leveraging the more fully documented 3-color 1-D totalistic CA.​
​I'm hoping this will save me some time and effort in searching through the 1 million + codes for 4-color 1-D totalistic CA.