Chasing Class Transitions in Cellular Automata Rule Spaces

Rodrigo A. Obando, Columbus State University

ABSTRACT

Since the 1980’s, when Stephen Wolfram classified the behavior of the evolution of cellular automata into four classes, we have investigated and studied individual classes or groups of classes. Using the primitives defined in Partioning of Cellular Automata Rule Spaces published in 2015, we define the rule spaces and provide direction in navigating them searching for class transitions. We find that the space has large regions of rules of the same class and there are particular transitions between those regions. We start this project with the Elementary Cellular Automata and layout the foundation to explore bigger spaces. According to the research we find that the layout is based on partially-ordered lattices which may explain why these regions are not easily defined under other alternative orderings. Just as it is with phase transitions, traversing the space and trying to move from one class to another may circunvent regions depending on how you traverse the space. We will show Manipulate statements to explore the Elementary Cellular Automata.

Introduction

Cellular Automata have been used to model and study systems that vary from simple to complex. The behavior of a particular cellular automata is governed by a series of simple rules. These rules are deterministic but some of them may present random or complex global behavior. The Elementary Cellular Automata (ECA) are defined as 2-color, 1-neighbor at each side and the total number of rules are 256. When we increase the number of colors and the number of neighbors the number grows exponentially. The number of rules in a rule space is given by this equation:

NumberOfRules[k_, r_]:= k^k^(2r+1)

NumberOfRules[2,1]
NumberOfRules[2,2]
NumberOfRules[3,1]

Parametrization of Rules

The large sizes of these rule spaces call for a way to explore them in a structured manner. There have been many ways to parametrize the rules in order to determine the type of behavior that they may have once they are evolved. One of the most known parametrization is Langton’s Lambda. It is a parameter that ranges from 0 to 1. If we consider the value 0 of a cell as the quiescent state then lambda is the number of 1’s in the rule divided by the number of bits in the rule.

The parameter proved to be useful but it does not give a good measure of the activity in the evolution of the rule. Depending on how you traverse the space you may find that the values may go from 0 to 1 but there may not be a good correlation between the value of lambda and the global behavior of the rule, i.e., the class to which it belongs.

Parametrization of rule primitives

Partitioning of Cellular Automata Rule Spaces gave a different parametrization of the rules by first splitting them into primitives. These primitives are the portion of the rules that affect the output depending on the state of the cell. There are as many primitives as there are colors in the rule.

RulePlot[CellularAutomaton[30]]

Primitive 0 is the subset where the central cell is 0 and Primitive 1 is the subset where the central cell is 1.

Functions in the Primitives

Rule 204 is the identity rule, the output does not change.

RulePlot[CellularAutomaton[204]]

Rule 51 is the complement rule, the output is the complement of its state.

RulePlot[CellularAutomaton[51]]

Functions in the Primitives

We may name or label each one of these functions and these functions exist only when there is a change in the value of the central cell. For primitive 0, if both neighbors are 0 then the function is labeled create, when the left cell is 0 and the right cell is 1 it is a left, when the right cell is 0 and the right cell is 1 it is a right and when both neighboring cells are 1 it is a merge. Primitive 1 has similar functions and they can obtained by complementing the descriptions above. Rule 51 contains all functions in both primitives whereas rule 204 contains none.

Activity[51]

Activity[204]

Looking Back

At the second NKS conference in 2004 I presented a preliminary view of the ECA rule space using the primitives and parametrization later on presented in Partitioning the Cellular Automata Rule Spaces published in Complex Systems.

Updated View

Using the functions presented above, I show here an updated view with a reordering of the primitives.

Manipulate[GraphicsGrid[Outer[Tooltip[ECAPlot[BuildRule[{#2,#1}],init,46],Activity[BuildRule[{#2,#1}]]]&,{15,14,13,11,7,12,10,6,9,5,3,8,4,2,1,0},{0,8,4,2,1,12,10,9,6,5,3,14,13,11,7,15}]],{{init,random},{{{1},0}->"Single One",{{0},1}->"Single Zero",random->"Random"}}, SynchronousUpdating->False, ContinuousAction->False]

View by Row

We may explore the space row by row.

Manipulate[GraphicsGrid[Outer[Tooltip[ECAPlot[BuildRule[{#2,#1}],init,46],Activity[BuildRule[{#2,#1}]]]&,{p1},{0,8,4,2,1,12,10,9,6,5,3,14,13,11,7,15}]],{{init,random},{{{1},0}->"Single One",{{0},1}->"Single Zero",random->"Random"}},{p1,{15,14,13,11,7,12,10,6,9,5,3,8,4,2,1,0},SetterBar}, SynchronousUpdating->False, ContinuousAction->False]

Subsets

These are some subsets of the space.

Manipulate[GraphicsGrid[Outer[Tooltip[ECAPlot[BuildRule[{#2,#1}],init, 100],Activity[BuildRule[{#2,#1}]]]&,{15,7,5,3,1,0},{0,8,12,10,14,15}]],{{init,random},{{{1},0}->"Single One",{{0},1}->"Single Zero",random->"Random"}}, SynchronousUpdating->False, ContinuousAction->False]

Subsets

This is the complement of the previous subset.

Manipulate[GraphicsGrid[Outer[Tooltip[ECAPlot[BuildRule[{#2,#1}],init,100],Activity[BuildRule[{#2,#1}]]]&,{15,14,10,12,8,0},{0,1,3,5,7,15}]],{{init,random},{{{1},0}->"Single One",{{0},1}->"Single Zero",random->"Random"}}, SynchronousUpdating->False, ContinuousAction->False]

Peek into a bigger space

This Manipulate allows us to take a peek into the 2^32 rule space, where r=2.

Manipulate[GraphicsGrid[{{LayeredGraphPlot[Flatten[Map[Outer[#1->#2&,{#},Variations[#,0],1]&, Table[IntegerDigits[n,2,4],{n,0,14}]],2],VertexShapeFunction->(Inset[EvolutionOnR1[p1,#2,init],#]&),EdgeShapeFunction->(EventHandler[{Blue,Arrow[#1,0.1]},"MouseClicked":>(fromRule=BuildRule[{FromDigits[#2[[1]],2],p1}];toRule=BuildRule[{FromDigits[#2[[2]],2],p1}];)]&)],LayeredGraphPlot[Flatten[Map[Outer[#1->#2&,{#},Variations[#,0],1]&, Table[IntegerDigits[n,2,4],{n,0,14}]],2],VertexShapeFunction->(Inset[EvolutionOnR2[fromRule,toRule,#2,init],#]&)]}}], {{init,{{1},0}},{{{1},0}->"Single One",{{0},1}->"Single Zero",random->"Random"}},{p1,{15,14,13,11,7,12,10,6,9,5,3,8,4,2,1,0},SetterBar},{fromRule,204},{toRule,205}, SynchronousUpdating->False, ContinuousAction->False]

Conclusion

We find that this parametrization of the cellular automata rules provides a good way to arrange the rules in the space in such a way as to cluster rules of similar behavior. We are able to see the class behavior transitions in the space. We see that if a rule has no functions or activity in one of its primitives the class behavior is Class 1. We note that there is an order in the space that allows a direction to follow in its exploration.
It seems that this order is also found in the bigger spaces such as in r = 2 space. Some experiments has been ran, not shown in this presentation, in the space for k = 3 that seems to have similar structure.
One of the next steps is to create a way to explore the bigger spaces to confirm that they also preserve this structure. Perhaps a good way is to create a Paclet that contains the tools for this exploration.

GetWolframClass[rule_]:=Module[{classes={{0,4,8,12,13,32,36,40,44,64,68,69,72,76,77,78,79,92,93,96,100,104,128,132,136,140,141,160,164,168,172,192,196,197,200,202,203,204,205,206,207,216,217,218,219,220,221,222,223,224,228,232,233,234,235,236,237,238,239,248,249,250,251,252,253,254,255},{1,2,3,5,6,7,9,10,11,14,15,16,17,19,20,21,23,24,25,26,27,28,29,31,33,34,35,37,38,39,41,42,43,46,47,48,49,50,51,52,53,55,56,57,58,59,61,62,63,65,66,67,70,71,73,74,80,81,82,83,84,85,87,88,91,94,95,97,98,99,103,107,108,109,111,112,113,114,115,116,117,118,119,121,123,125,127,130,131,133,134,138,139,142,143,144,145,148,152,154,155,156,157,158,159,162,163,166,167,170,171,173,174,175,176,177,178,179,180,181,184,185,186,187,188,189,190,191,194,198,199,201,208,209,210,211,212,213,214,215,226,227,229,230,231,240,241,242,243,244,245,246,247},{18,22,30,45,60,75,86,89,90,101,102,105,106,120,122,126,129,135,146,149,150,151,153,161,165,169,182,183,195,225},{54,110,124,137,147,193}}},
Do[If[MemberQ[classes[[n]],rule],Return[n]],{n,1,Length[classes]}]];
ECAPlot[rule_,init_,size_]:=ArrayPlot[CellularAutomaton[{rule,2,1},init,{100,All}],PlotLabel->rule,ColorRules-> {0->White,1->colors[[GetWolframClass[rule]]],_->Black}, ImageSize->{size,1.5 size}];
BreakRule[rule_,r_: 1]:=Module[{splitRule=Partition[IntegerDigits[rule,2,2^(2 r+1)],2 r]},Map[FromDigits[#,2]&,{Flatten[splitRule[[Table[n,{n,2,Length[splitRule],2}]]]],Flatten[splitRule[[Table[n,{n,1,Length[splitRule],2}]]]]}]];
BuildRule[prims_,r_: 1]:=FromDigits[Flatten[Thread[{Partition[IntegerDigits[prims[[2]],2,2^(2 r)],2 r],Partition[IntegerDigits[prims[[1]],2,2^(2 r)],2 r]},List,All]],2];
Activity[rule_]:=Module[{primitives=BreakRule[rule]},Flatten[{{(Subscript[Global`m, 0]),(Subscript[Global`r, 0]),(Subscript[Global`l, 0]),(Subscript[Global`c, 0])}[[Flatten[Position[IntegerDigits[primitives[[1]],2,4],1]]]],{(Subscript[Global`m, 1]),(Subscript[Global`r, 1]),(Subscript[Global`l, 1]),(Subscript[Global`c, 1])}[[Flatten[Position[Reverse[IntegerDigits[primitives[[2]],2,4]],0]]]]}]];
colors={Green,Blue,Purple,Red};
random=Table[RandomInteger[1],{n,1,100}];
Variations[init_,dummy_]:=Module[{positions, variations},
positions=Flatten[Position[init,dummy]];
variations=Map[ReplacePart[init,#->FromDigits[1-IntegerDigits[dummy,2,1],2]]&,positions]
];
EvolutionOnR1[p1_,splice_,init_]:=Module[{rule=BuildRule[{FromDigits[splice,2],p1}]},ArrayPlot[CellularAutomaton[{rule,2,1},init,{100,All}], PlotLabel->Style[MatrixForm[{rule,Activity[rule], splice}],Tiny],ColorRules-> {0->White,1->colors[[GetWolframClass[rule]]],_->Black},ImageSize->50]];
CloneBit[bitValue_]:={bitValue,bitValue};
SetAttributes[CloneBit,Listable];
CloneList[list_]:=Flatten[{list,list}];
NextRadiusPrim[prim_,radius_]:=FromDigits[CloneList[Flatten[CloneBit[IntegerDigits[prim,2,2^(2 radius)]]]],2];
NextRadiusRule[rule_,radius_]:=Module[{prims=BreakRule[rule,radius]},prims[[1]]=NextRadiusPrim[prims[[1]],radius];
prims[[2]]=NextRadiusPrim[prims[[2]],radius];
BuildRule[prims,radius+1]];
PositionsOfDifferences[from_,to_]:=Flatten[Position[to-from,1]];
FindMappingPrim[primFrom_,primTo_,range_:1]:=PositionsOfDifferences[IntegerDigits[primFrom,2,2^(2range)],IntegerDigits[primTo,2,2^(2range)]];
Substitute[primitive_,gene_,splice_]:=ReplacePart[primitive,Map[gene[[#]]->splice[[#]]&,Range[Length[gene]]]];
Lambdas[rule_, r_: 1] := Module[{primitives=Map[IntegerDigits[#,2,2^(2r+1)/2]&,BreakRule[rule,r]]},{Count[primitives[[1]],1],Count[primitives[[2]],0]}];
GetCycles[hist_,numberToDrop_]:=Length[Union[Drop[hist,numberToDrop]]];
Classifier[hist_]:=Module[{shifts=Table[RotateRight[hist[[-3]],n],{n,-5,5}],compare,theClass},compare=Flatten[Position[Table[shifts[[n]]==hist[[-1]],{n,1,Length[shifts]}],True]];
If[Length[compare]==0,theClass=3,If[MemberQ[compare,6],theClass=1,theClass=2]];
theClass];
Detangler[class_,cycles_]:=If[cycles==1,1,If[cycles≤512,2,If[class==2,class,If[class==3 &&cycles>512,class,2]]]];
EvolutionOnR2[fromRule_,toRule_,splice_,init_]:=Module[{fromPrims=BreakRule[NextRadiusRule[fromRule,1],2],toPrims=BreakRule[NextRadiusRule[toRule,1],2],mappedRule,longHistory,shortHistory},
mappedRule=BuildRule[{FromDigits[Substitute[IntegerDigits[fromPrims[[1]],2,16],FindMappingPrim[fromPrims[[1]],toPrims[[1]],2],splice],2],toPrims[[2]]},2];
longHistory=CellularAutomaton[{mappedRule,2,2},init,{1000,All}];
shortHistory =CellularAutomaton[{mappedRule,2,2},init,{100,All}];
ArrayPlot[shortHistory, PlotLabel->Style[MatrixForm[{mappedRule,Lambdas[mappedRule,2], splice}],Tiny],ColorRules-> {0->White,1->colors[[Detangler[Classifier[longHistory],GetCycles[longHistory,50]]]],_->Black},ImageSize->50]];
NumberOfRules[k_, r_]:= k^k^(2r+1);