Probabilistic Cellular Automata from Cluster Signatures

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

Join the Conversation #WolframTechConf

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 calleed 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.

Cluster Signatures

The clustering algorithm identifies the cluster by expanding ‘outward’ from a seed rule. It systematically tries paths in the partially-ordered space and identifies which bits in the rule can change and still maintain the global behavior. There is a threshold that is used to measure percentage of similarity. The particular comparison algorithm can be independently defined.
The output of the algorithm is a Cluster Signature that encapsulates information about all the rules that are in the cluster. Each bit in the rule is identified as P, N or D. P indicates that the bit introduces change in the rule, i.e., a 1 in p0 or a 0 in p1. An N indicates that the bit should anchor the behavior or not introduce change, i.e. a 0 in p0 and a 1 in p1. A D indicates that the bit can be any value, either 0 or 1. Using the cluster signature we can extract all the rules that exist in the cluster. The size of the cluster can be found as follows.

clusterSignature = {{"P","N", "N","N"},{"D","D","P","P"}}
d=Count[Flatten[clusterSignature],"D"]
clusterSize = 2^d

There are some interesting clusters we found while testing the algorithm.

Interesting Cluster Signatures

We tried finding the cluster signature around rule 90. We chose this rule because it had a recognizable global behavior for a single 1 as an input. We found the following cluster signature:

SierpinskiClusterSignature={{"N","P","P","N"},{"D","D","D","P"}}
sierpinskiRules=CreateRules[IntegerDigits[FromClusterSignature[SierpinskiClusterSignature, 1],2,2^3], ClusterToRule[SierpinskiClusterSignature, 1]]
Map[ArrayPlot[CellularAutomaton[#,{{1},0},50]]&,sierpinskiRules]

Complement Cluster Signatures

We can compute the complement of a cluster signature. Using the signature shown before we have:

ComplementSierpinskiClusterSignature={{"P","D","D","D"},{"N","P","P","N"}}
sierpinskiRules=CreateRules[IntegerDigits[FromClusterSignature[ComplementSierpinskiClusterSignature, 1],2,2^3], ClusterToRule[ComplementSierpinskiClusterSignature, 1]]
Map[ArrayPlot[CellularAutomaton[#,{{0},1},50]]&,sierpinskiRules]

Notice that we also complemented the input so that the output would be consistent. This is also indicative of the importance of how change is introduced in a rule or a primitive.
These two signatures show how all these Sierpinski triangle rules are all related to each other showing that the partitioning fo the rule space is coherent.

Mixed/Non-Uniform Cellular Automata

Cellular automata uses a single rule for each one of its cells. This is called uniform cellular automata and it is the most used mode. A mixed cellular automata, or Non-Uniform,  is a cellular automata where each cell may have a different rule. Evolution of these automata will depend on the rules used in each one of the cells and without clear guidelines it becomes a wide open field for their evolutions. We looked at creating mixed cellular automata and restricting the rules to come from a given cluster signature. The evolution of such systems looked, in general, very similar to any of the rules in the cluster. Given that we chose the rules at the beginning and we do not change the rules afterwards, this cellular automata is still deterministic.

Probabilistic Cellular Automata

Changing the rule for each cell at every evaluation step is equivalent to making a probabilistic cellular automaton where the rule is the cluster signature and the random portion is provided by the D’s in the signature. In this case, the rule is the cluster signature but since some of the portions of the rules are selected randomly, this becomes a probabilistic cellular automaton. 
Given these parameters there are a total of 6561 rules based on the ECA.

totalPCAs=3^8

We believe that the global behavior of these cellular automata is structurally stable.

Triangles with tendrils:  PCAs: PPPN, NDDD and complement DDDN, NPPP Input: DETERMINISTIC
Rips from top in triangles: PDDP, NPPP and complement PPPN, PDDP input: DETERMINISTIC
Rips on a veil: PDDD, NDDP and PDDN, DDDP (complements) Input: STOCHASTIC
Seashell patterns: DNNP, NPPP and complement PPPN, PNND Input: STOCHASTIC
Other seashell patterns: NPPN, DDDP and complement PDDD, NPPN Input: STOCHASTIC
Roots or lightning: DDDD, NDDD and complement DDDN, DDDD  Input: STOCHASTIC

Code for presentation

RulePartition[radius_: 1, colors_: 2] := Table[Table[n, {n, m, colors^(1 + radius), colors}], {m, colors, 1, -1}];

BreakRule[rule_, radius_: 1, colors_: 2] := Module[{
	digitPartition = RulePartition[radius, colors], 
	tempRule}, 
		tempRule = IntegerDigits[rule, colors^(colors^radius), colors^(1 + radius)];
		Table[FromDigits[tempRule[[digitPartition[[m]]]], colors^(colors^radius)], {m, 1, colors}]];

Digitize[prim_, radius_: 1, colors_: 2] := IntegerDigits[prim, colors^(colors^radius), colors^(1 + radius)/colors];

SetAttributes[Digitize, Listable];

BuildRule[prims_, radius_: 1] := Module[{
	colors = Length[prims],
	tempPrims,
	tempRule = {}},
		tempPrims = Digitize[prims, radius, colors];
    	Do[tempRule = Append[tempRule, (tempPrims[[m]])[[n]]], {n, 1, Length[tempPrims[[1]]]}, {m, Length[tempPrims], 1, -1}];
    	FromDigits[tempRule, colors^(colors^radius)]];

(*Function that takes in a binary number and a cluster id as a mask to produce all the possible numbers according to the mask.*)
CreateRules[in_,mask_]:=FromDigits[#,2]&/@Module[{p=Position[mask,"D"]},ReplacePart[in,Rule@@@Transpose[{p,#}]]&/@Tuples[{0,1},Length@p]]

(*Function that takes in a cluster id or rule, then returns a binary form of that cluster id.*)
FromClusterSignature[sig_, radius_:1] := 
Module[{temp = {}, id = sig},
id[[1]]=sig[[1]]/.{"P"-> 1}/.{"N"-> 0}/.{"D" :>  RandomInteger[1]};
id[[2]]=sig[[2]]/.{"P"-> 0}/.{"N"-> 1}/.{"D":>  RandomInteger[1]};
Table[
AppendTo[temp,Take[id[[2]],{pos, pos + (2^radius - 1)}]];
AppendTo[temp,Take[id[[1]],{pos, pos + (2^radius - 1)}]],
{pos,1,2^(2 radius + 1)/2,2^radius}];
Return[FromDigits[Flatten[temp],2]]]

ClusterToRule[sig_, radius_:1] := 
Module[{temp = {}},
Table[
AppendTo[temp,Take[sig[[2]],{pos, pos + (2^radius - 1)}]];
AppendTo[temp,Take[sig[[1]],{pos, pos + (2^radius - 1)}]],
{pos,1,2^(2 radius + 1)/2,2^radius}];
Return[Flatten[temp]]]