A Guided Tour of the ECA and Beyond

Rodrigo A. Obando, Ph.D.
TSYS School of Computer Science
Columbus State University

Join the Conversation #WolframTechConf

Abstract

We have studied the Elementary Cellular Automata rule space for many decades. Ever since Langton’s Lambda, we have associated the number of 1s in a rule to indicate that some kind of dynamic behaviour is introduced in the evolution of the rule. We know that Langton’s Lambda helped at that time but it was not always indicative of the amount of dynamic behaviour in the evolution of a given cellular automata rule.

If we were to follow that idea, rule 0 would not introduce any kind of change in the evolution. The fact is that it does introduce change at the very beginning of the evolution: after one step all cells are 0. Rule 255 is the counterpart of rule 0, it introduces change at the very beginning and the output of the rule is all cells are 1 after the first evolution step.

Obando introduced a different way of describing the rules in a paper in Complex Systems. The mapping allowed for defining a different set of Lambdas instead of just one Lambda as in the case of Langton’s. This allowed to partially-order the rules from no dynamic behaviour to the maximum possible. The rule that has no dynamic behavior is the identity rule, rule 204. The rule what would have the maximum change possible is the complement rule, rule 51. We can display all rules in the ECA, from 204 to 51 using a series of lattices.

We can use the same layout to explore the space between two connected rules in the ECA that are mapped onto the rule space with radius 2. Using this technique, we can explore, for example, the space between rule 206 and rule 110 by mapping those rules to the rule space with radius 2. We can then continue on and explore another part of the space in the rule space with radius 3, radius 4 and so on.

An interesting finding in one of these experiments is that, in rule space radius 2, we find a rule that is visually similar to 110 but it seems that rule 110 is a blurred version of that rule.

Partitioning the Cellular Automata Rule Space

The start of this work goes back to NKS Conference 2004 and NKS Summer School 2004. This is a stroll into the Computational Universe brought by NKS.
We partition the Cellular Automata Rule Space using the notion of primitives introduced by Obando. The rule is partitioned into k number of primitives where k is the number of states or colors of the cells.For the case of k = 2, we have two primitives,namely p0 and p1. For the Elementary Cellular Automata Rule Space (ECA,) where the rule is 8-bits, we have that each primitive is composed of 4 bits. p0 contains the bits that determines the cell’s next state when the state of the cell is 0. p1 contains the bits that determines the cell’s next state when the state of the cell is 1.

primitives = Map[BreakRule, {10, 30, 110,27,45,90}]
rules = Map[BuildRule, primitives]

The number of 1’s in p0 indicates the dynamic behavior of the rule when the cell value is 0. The number of 0’s in p1 indicates the dynamic behavior of the rule when the cell value is 1. We can order the primitives by the number of 1’s in p0 and the number of 0’s in p1. The more of those respectively the more change is introduced in the rule. The previous idea of just counting the number of 1’s in the rule does not really indicate the dynamics of the rule since a 1 in p1 does not introduce change in the state of the cell, only a 0 would introduce change in p1. So, the number of 1’s in p0 is called lambda0 and the number of 0’s in p1 is called lambda1. This idea should not be confused with Langton’s lambda which strictly counted the number of 1’s in the entire rule. We then could order the primitives by how much change they introduce but we find that they cannot be strictly-ordered but they are a partially ordered set and they can be placed in a lattice.

halves=BreakRule[124]
binaryHalves = Map[IntegerDigits[#,2,4]&,halves]
lambdas={Count[binaryHalves[[1]],1],Count[binaryHalves[[2]],0]}

Partially-Ordered Primitives

The ECA has the following set of primitives:

ECAPrimitives= Table[n, {n,0,15}]

LayeredGraphPlot[{0->1,0->2,0->4,0->8,1->3,1->5,1->9,2->3,2->6,2->10,4->5,4->6,4->12,8->9,8->10,8->12,3->7,3->11,5->7,5->13,6->7,6->14,9->11,9->13,10->11,10->14,12->13,12->14,7->15,14->15,13->15,11->15},VertexLabeling->True]

If we arrange each ‘dimension’ of our space using this lattice, we can partially-order the entire space where we can move from no-change rule 204 (identity) to total-change rule 51 (complement.) Huffman created a rule space crawler to navigate this space and visualize the neighboring rules. We found that adjacent rules exhibit similar global behavior. We decided to create an algorithm that would find the neighboring rules that would be similar in global behavior.

The lattices of the ECA (r=1)

Manipulate[Graphics[Map[{Inset[Tooltip[ArrayPlot[CellularAutomaton[{#,2,1},init,{100,All}]],ArrayPlot[CellularAutomaton[{#,2,1},init,{200,All}],PlotLabel->{#,BreakRule[#],{BreakRule[#][[1]],FromDigits[1-IntegerDigits[BreakRule[#][[2]],2,4],2]}}]],TranslateCoordinates[#, flip],{0,0},{1,1}]}&, Table[n,{n, 0, 255}]]], {init,{{{1},0},{{0},1}},SetterBar},{flip,{False,True},SetterBar},SaveDefinitions->True]

Immediate Neighbors

Manipulate[Graph[Flatten[{{sRule},Predecessors[sRule],Successors[sRule]}],Flatten[{Map[#->sRule&,Predecessors[sRule]],Map[sRule->#&,Successors[sRule]]}],VertexShapeFunction->(Inset[ArrayPlot[CellularAutomaton[{#2,2,1},{{1},0},{100,All}],PlotLabel->#2],#]&),GraphLayout->"LayeredDigraphEmbedding"],{{sRule,204},0,255,1},{eRule,Successors[sRule],SetterBar},SaveDefinitions->True]

The rules within the space (r=2)

Manipulate[Graphics[Map[{Inset[Tooltip[ArrayPlot[CellularAutomaton[{GeneTherapy[NextRadiusRule[ECAFromRule,1],2,FindMapping[ECAFromRule,ECAToRule],Map[IntegerDigits[#,2,4]&,BreakRule[#]]],2,2},init,100]],ArrayPlot[CellularAutomaton[{GeneTherapy[NextRadiusRule[ECAFromRule,1],2,FindMapping[ECAFromRule,ECAToRule],Map[IntegerDigits[#,2,4]&,BreakRule[#]]],2,2},init,500],PlotLabel->GeneTherapy[NextRadiusRule[ECAFromRule,1],2,FindMapping[ECAFromRule,ECAToRule],Map[IntegerDigits[#,2,4]&,BreakRule[#]]]]],TranslateCoordinates[#,flip],{0,0},{1,1}]}&, Table[n,{n, 0, 255}]]],{{ECAFromRule,236},0,255,1},{{ECAToRule,110},Successors[ECAFromRule],SetterBar},{init,{{{1},0},{{0},1}},SetterBar},{flip,{False,True},SetterBar},SaveDefinitions->True]

High Definition Evolution of Rule ‘110’ (Simple Input)

Manipulate[GraphicsGrid[{{ArrayPlot[CellularAutomaton[{1023163644,2,2},{{1},0},steps], PlotLabel->1023163644]},{ArrayPlot[CellularAutomaton[{1023212796,2,2},{{1},0},2steps],PlotLabel->1023212796],ArrayPlot[CellularAutomaton[{1022950652,2,2},{{1},0},2steps],PlotLabel->1022950652],ArrayPlot[CellularAutomaton[{1023211772,2,2},{{1},0},2steps],PlotLabel->1023211772],ArrayPlot[CellularAutomaton[{1022949628,2,2},{{1},0},2steps],PlotLabel->1022949628]},{ArrayPlot[CellularAutomaton[{1023196412,2,2},{{1},0},2steps],PlotLabel->1023196412],ArrayPlot[CellularAutomaton[{1023180028,2,2},{{1},0},2steps],PlotLabel->1023180028],ArrayPlot[CellularAutomaton[{1010580508,2,2},{{1},0},2steps],PlotLabel->1010580508],ArrayPlot[CellularAutomaton[{1895576828,2,2},{{1},0},4steps],PlotLabel->1895576828],ArrayPlot[CellularAutomaton[{1895578876,2,2},{{1},0},4steps],PlotLabel->1895578876]}}],{steps,10,1000,10},SaveDefinitions->True]

High Definition Evolution of Rule ‘110’ (Random Input)

Manipulate[GraphicsGrid[{{ArrayPlot[CellularAutomaton[{1023163644,2,2},random,{steps,All}], PlotLabel->1023163644]},{ArrayPlot[CellularAutomaton[{1023212796,2,2},Flatten[Map[{#,#}&, random]],{2steps,All}],PlotLabel->102229497628],ArrayPlot[CellularAutomaton[{1023212796,2,2},Flatten[Map[{#,#}&, random]],{2steps,All}],PlotLabel->1023212796]},{ArrayPlot[CellularAutomaton[{1022950652,2,2},Flatten[Map[{#,#}&, random]],{2steps,All}],PlotLabel->1022950652],ArrayPlot[CellularAutomaton[{1023211772,2,2},Flatten[Map[{#,#}&, random]],{2steps,All}],PlotLabel->1023211772]}}],{steps, 10,500,10},SaveDefinitions->True]

Conclusion

This characterization of the rules provides a way to study the rule spaces and how the behavior is distributed in the space. The layout allows for a systematic study of the rules and provides an avenue to delve deeper in the study of the rules using the ECA as a starting point for a framework to go into bigger spaces. A simple exploration made possible finding the higher resolution rules that behave like rule 110 in the ECA.

References

1- R. Obando, ‘Partitioning of Cellular Automata Rule Spaces,’ Complex Systems, Vol. 24, Number 1, pp. 27-48, 2015.

Code for presentation

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];
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}]]]]}]];
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]];
coordinates={{-3.`,0},{-1.5`,1.5`},{-1.5`,0.5`},{0.`,2.5`},{-1.5`,-0.5`},{0.`,1.5`},{0.`,0.5`},{1.5`,1.5`},{-1.5`,-1.5`},{0.`,-0.5`},{0.`,-1.5`},{1.5`,0.5`},{0.`,-2.5`},{1.5`,-0.5`},{1.5`,-1.5`},{3.`,0}};
TranslateCoordinates[rule_,flip_:False]:=Module[{p,p0,p1,temp},p=BreakRule[rule]; p0=p[[1]];p1=FromDigits[1-IntegerDigits[p[[2]],2,4],2];
If[flip,temp=p1;p1=p0;p0=temp];
(*p1=p[[2]];*)
coordinates[[p1+1]] 1.5+coordinates[[p0+1]] 9.0]
GeneTherapy[rule_,range_,gene_,splice_]:=Module[{seed=Map[IntegerDigits[#,2,2^(2range)]&,BreakRule[rule,range]]},
seed={ReplacePart[seed[[1]],Map[gene[[1,#]]->splice[[1,#]]&,{1,2,3,4}]],ReplacePart[seed[[2]],Map[gene[[2,#]]->splice[[2,#]]&,{1,2,3,4}]]};
BuildRule[Map[FromDigits[#,2]&,seed],range]
]
Variations[init_,dummy_]:=Module[{positions, variations},
positions=Flatten[Position[init,dummy]];
variations=Map[ReplacePart[init,#->FromDigits[1-IntegerDigits[dummy,2,1],2]]&,positions]
]
Successors[rule_]:= Module[{primitives=BreakRule[rule],p0,p1,tuples},
p0=IntegerDigits[primitives[[1]],2,4];
p1=IntegerDigits[primitives[[2]],2,4];
tuples=Tuples[{Variations[p0,0],Variations[p1,1]}];
Map[BuildRule[Map[FromDigits[#,2]&,#]]&,tuples]
]
Predecessors[rule_]:= Module[{primitives=BreakRule[rule],p0,p1,tuples},
p0=IntegerDigits[primitives[[1]],2,4];
p1=IntegerDigits[primitives[[2]],2,4];
tuples=Tuples[{Variations[p0,1],Variations[p1,0]}];
Map[BuildRule[Map[FromDigits[#,2]&,#]]&,tuples]
]
FindMapping[ruleFrom_,ruleTo_]:=Module[{ruleToExpanded,ruleFromExpanded},
ruleToExpanded=Map[IntegerDigits[#,2,16]&,BreakRule[NextRadiusRule[ruleTo,1],2]];
ruleFromExpanded=Map[IntegerDigits[#,2,16]&,BreakRule[NextRadiusRule[ruleFrom,1],2]];
{Flatten[Position[ruleToExpanded[[1]]-ruleFromExpanded[[1]],1]],Flatten[Position[ruleFromExpanded[[2]]-ruleToExpanded[[2]],1]]}
]
random=Table[RandomInteger[1],{n,1,100}];