Introduction to A Unified Model of Cellular Automata

Rodrigo A. Obando, Columbus State University

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

This is an introduction to a unified model of Cellular Automata in which a rule is represented not by a single function but by a vector of functions we call genes. These functions can be ordered so that they maintain the same order regardless of the rule space where they are realized. This order allows the vectors to be normalized and positions all rules in a unit hypercube. There are operations on the rules that are simple to implement in the normalized space such as Modulo-Additive Equivalent rules, known as complement in the binary k value case. We also introduce the concept of symmetry index based on the number of symmetric genes that make up the rule. We also show the concept of canonical rule which is the rule number for the minimum value of r where the rule can be realized. There are many other functions that are introduced such as genetic trees, equation trees, evolution trees and canonical trees among others. There are also functions to perform reflection, reversibility, monotonicity and symmetry tests. Also, measures such as Langton’s Lambda, Delta parameter and symmetry index are implemented.

Introduction

Given the allocated time for this talk there are only certain parts of the unified model that can be explained. There is a paper under consideration in the Journal of Cellular Automata where the theoretical details are given. This talk will concentrate in illustrating some of the functions available in the paclet named Obando`CAGenetics. The paclet does not have a lot of documentation yet but it will be updated. Here is the link.
 https://resources.wolframcloud.com/PacletRepository/resources/Obando/CAGenetics/

At the very heart of this model lies the decomposition of cellular automata rules into gene functions or simply genes. Each cellular automata rule can be decomposed into k number of genes, where k is the number of values in the cells of the cellular automata. For the case of k = 2, we may express the functions that describes the cellular automat rule as follows,

(Subscript[f, (Subscript[a, 0])])=(OverBar[(Subscript[a, 0])]) (Subscript[g, 0])+(Subscript[a, 0]) (Subscript[g, 1])

where (Subscript[a, 0]) is the value of the central cell, (Subscript[g, 0]) is the gene function active when (Subscript[a, 0]) = 0 and (Subscript[g, 1]) is the gene function active when (Subscript[a, 0]) =1.

(Subscript[f, (Subscript[a, 0])])=(KroneckerDeltaSeq[0,(Subscript[a, 0])]) (Subscript[g, 0])+(KroneckerDeltaSeq[1,(Subscript[a, 0])]) (Subscript[g, 1])

where (KroneckerDeltaSeq[0,(Subscript[a, 0])]) is the KroneckerDelta function.
For general case of the equation, when k > 2, the following form is used.

(Subscript[f, (Subscript[a, 0])])=((KroneckerDeltaSeq[0,(Subscript[a, 0])]) (Subscript[g, 0])+(KroneckerDeltaSeq[1,(Subscript[a, 0])]) (Subscript[g, 1])...)+(KroneckerDeltaSeq[k-1,(Subscript[a, 0])]) (Subscript[g, k-1])=(∑_(i=0)^(k-1))(KroneckerDeltaSeq[i,(Subscript[a, 0])]) (Subscript[g, i])

Gene function sets

For each value of r, there is a set of gene functions available to make up the rules of the cellular automata rule space. Let’s consider the sets when k = 2.

For r = 0, we only have constants for the genes.

Table[PrintableEquation[GeneEquation[n,2,0]],{n,0,1}]//MatrixForm

For r = 1/2, we have the following genes.

Table[PrintableEquation[GeneEquation[n,2,1/2]],{n,0,3}]//MatrixForm

For r = 1, we have the following genes.

Table[PrintableEquation[GeneEquation[n,2,1]],{n,0,15}]//MatrixForm

These last gene functions are the ones used to create the Elementary Cellular Automata rule space (ECA.)
We can create a table of all rule equations for a given rule space, in fact, there is a way to organize the genes so that each rule equation will be placed in the same relative space.

Rule function spaces

For r = 0, this is a display of its rule equations. The second table is the display of the rule numbers.

Outer[PrintableEquation[RuleEquation[FromGenes[{#2,#1},2,0],2,0]]&,Reverse[OffsetGeneSet[2,0]],GeneSet[2,0]]//MatrixForm
Outer[FromGenes[{#2,#1},2,0]&,Reverse[OffsetGeneSet[2,0]],GeneSet[2,0]]//MatrixForm

For r = 1/2, this is a display of its rule equations. The second table is the display of the rule numbers.

Outer[PrintableEquation[RuleEquation[FromGenes[{#2,#1},2,1/2],2,1/2]]&,Reverse[OffsetGeneSet[2,1/2]],GeneSet[2,1/2]]//MatrixForm
Outer[FromGenes[{#2,#1},2,1/2]&,Reverse[OffsetGeneSet[2,1/2]],GeneSet[2,1/2]]//MatrixForm

Cellular Automata Vector Space

Since every rule may be expressed using its genes, we encode it as a vector of genes. The function RuleGenes extracts the genes from a rule.

{#,RuleGenes[#,2,1]}&/@{110,30,90,45}//MatrixForm

{#,RuleGenes[#,3,1]}&/@{4747164123374,468286498833,5729678464557,3883928323719}//MatrixForm

There is also the function FromGenes that takes k number of genes and returns a rule.

FromGenes[{10,7},2,1]
FromGenes[{15045,12883,1267},3,1]

Normalized Space

The rule space for r = 0 is contained in the rule space for r = 1/2 and in turn this one is contained in the rule space for r = 1. The only issue is that the rule numbers are different depending on the rule space. If we use the relative position of each gene function in the lists shown before, we may normalize each gene and then encode each rule with the relative positions within a hypercube.
The functions ToNormalSpace and FromNormalSpace do this transformation between the regular spaces and the normalized space. The normalized space contains all rules for a given value of k.

{#,ToNormalSpace[#,2,1]}&/@{110,30,90,45}//MatrixForm

{FromNormalSpace[#,2,1],#}&/@{{(1/5),(8/15)},{(2/5),(2/3)},{(2/5),(3/5)},{(3/5),(2/3)}}//MatrixForm

The rules shown above exist in r = 3/2 but they have a different number. Each of those rules whether they are in r = 1 or r =3/2 have the same normalized vector and this transformation can be used to find them by simply transforming them to the normal space and then transforming them back into regular space with r = 3/2 or any other r > 1.

{#,FromNormalSpace[ToNormalSpace[#,2,1],2,3/2],FromNormalSpace[ToNormalSpace[#,2,1],2,2]}&/@{110,30,90,45}//MatrixForm

Canonical Rule

The previous section presents the opportunity to introduce the concept of Canonical Rule. A Canonical Rule is the rule that is realizable from a normalized rule at the minimum value of r. Taking a normalized rule we can compute what is the minimum value of r for which the rule can be realized in the normal space. Let’s take the rule 1023163644 in k = 2, r = 2 and find its Canonical Rule from normal space.

nr=ToNormalSpace[1023163644,2,2]
CanonicalRule[nr]

The minimum value of r for rule 1023163644 for k=2, r = 2 is 110 for k = 2, r = 1.
Let’s now take the rule 468286498833 in k = 3, r = 1 and find its canonical rule.

nr = ToNormalSpace[468286498833,3,1]
CanonicalRule[nr]

Symmetry Index

Symmetry in rule evolution has been explored from a long time. When we looked at the rule space for k = 2, r = 1, we defined symmetric rules, semisymmetric rules and asymmetric rules. When we work with rules where k > 2, we find that this characterization is too broad since in the set of semisymmetric rules we find many levels of semi symmetry. We define symmetry index σ as follows.

σ=s/k

where s is the number of symmetric genes in the rule and k is the number of values in the cells of the rule.
Let’s take various rules from different spaces and find their symmetry indices.

SymmetryIndex[110,2,1]
SymmetryIndex[30,2,1]
SymmetryIndex[90,2,1]
SymmetryIndex[171922294,2,2]
SymmetryIndex[762546394,2,2]
SymmetryIndex[72324848056,3,1]
SymmetryIndex[3195553370759,3,1]
SymmetryIndex[,7,1]

This concept makes it easier to find random rules with various levels of symmetry. The following function does just that.

RandomSymmetricRule[3,2]
RandomAsymmetricRule[4,1]
RandomSemiAsymmetricRule[5,1,2/5]

Modulo-Additive Equivalent Rules

Without going into too much detail, modulo-additive equivalent rules are rules that are equivalent because one behaves the same as the other except that their output is shifted with respect to the other for shifted input. We know those rules in k = 2 as the complement rules which are a special case or subset of modulo-additive equivalency.

MAERule[110,2,1,1]
MAERule[30,2,1,1]
MAERule[90,2,1,1]

GraphicsGrid[{{CAPlot[110,2,1,{{1},0},110],CAPlot[MAERule[110,2,1,1],2,1,{{0},1},MAERule[110,2,1,1]]}}]

GraphicsGrid[{{CAPlot[1875598986365,3,1,{{1},0},1875598986365],CAPlot[MAERule[1875598986365,3,1,1],3,1,{{2},1},MAERule[1875598986365,3,1,1]],CAPlot[MAERule[1875598986365,3,1,2],3,1,{{0},2},MAERule[1875598986365,3,1,2]]}}]

The operation of modulo-additive equivalency is easy to perform in the normalized space. Once you have the normalized vector all you need to do is shift its elements a given number of times and then transform the normalized vector rule back to normal space.

Genetic trees and other types of trees

The use of gene functions also allows use to look at the rules in many more ways. One of those is by creating a genetic tree where the root is the rule and its children are its genes, the children of the genes and their children, so on and so forth.

GraphicsGrid[{{CAGeneticTree[110,2,1],CAGeneticTree[30,2,1]},{CAGeneticTree[90,2,1],CAGeneticTree[75,2,1]}}]

CAGeneticTree[1875598986365,3,1]

Along the same line, we have equation trees. Using the same rules used above, here are their equation trees.

GraphicsGrid[{{CAEquationTree[110,2,1],CAEquationTree[30,2,1]},{CAEquationTree[90,2,1],CAEquationTree[75,2,1]}}]

CAEquationTree[1875598986365,3,1]

The equation trees make use of the genetic trees by simply applying the RuleEquation and GeneEquation functions to the genetic trees.
Worth mentioning are the evolution trees which are obtained from the genetic trees by using TreeMap and applying the display of the of the rule evolutions.

CAEvolutionTree[110,2,1]

There are also canonical trees, normal trees, monotoneQ trees, and symmetry index trees.

Special Functions

There are many other functions such as identity rule, inverse rule, negate rule, reverse rule, gene rule, and reflect rule. For example, the identity rule returns the rule number for the identity rule for a given value of k and r.

IdentityRule[2,1]
IdentityRule[2,3]
IdentityRule[3,1]
IdentityRule[4,1/2]

The gene rule returns a rule that is made from the identity rule but replacing a gene with the one supplied at a particular position in the rule vector. We get the normalized rule to see this effect.

GeneRule[13,1,3,1]
ToNormalSpace[GeneRule[13,1,3,1],3,1]

The reflect rule returns the reflected rule of the one provided. This is performed by reflecting each gene and returning it back as an integer.

ReflectRule[110,2,1]
ReflectRule[30,2,1]
ReflectRule[90,2,1]
ReflectRule[75,2,1]

Test functions

There are also test functions such as reflection test, reversibility test, monotonicity test, and symmetry test. The reflection test checks whether a rule is self-reflective. The symmetry test check whether a rule is symmetric.

Various functions

Along the symmetry index, there exist the often used and cited Langton’s Lambda parameter and a new parameter named Delta.
There are also functions such as gene splice, rule splice and canonical genes. Rule splice takes a rule from a given space in k, r and splices it into a rule for a larger k and/or larger r. Effectively, you may take a rule from k = 2, r = 1 and create a rule from splicing it into a rule in space k = 3, r = 1.

sr=RuleSplice[110,2,1,IdentityRule[3,1],3,1]
CAPlot[sr,3,1,{{1},0},sr]
RuleEquation[110,2,1]
ModulusPFunction[110,2,RuleVariables[1]]
RuleEquation[sr,3,1]

Conclusion

This unified model of Cellular Automata allows for the exploration of the rule spaces in a way that may have not been possible before. There are still many other functions that can be written that will come from the investigation of the model. Perhaps we may find properties we were not aware of and we may take advantage of the new findings.
The paclet will be updated with new functionality and documentation.