# A Fully Operational Framework for Handling Cellular Automata Templates

Authors: Mauricio Verardo; Pedro P. B. de Oliveira
Journal: Complexity
 (2019)

---

## Abstract

Cellular automata are fully discrete, computational, or dynamical systems, characterised by a local, totally decentralised action. Although extremely simple in structure, they are able to represent arbitrarily complex phenomena. However, due to the very big number of rules in any nontrivial space, finding a local rule that globally unfolds as desired remains a challenging task. In order to help along this direction, here we present the current state of cellular automatatemplates, a data structure that allows for the representation of sets of cellular automata in a compact manner. The template data structure is defined, along with processes by which interesting templates can be built. In the end, we give an illustrative example showcasing how templates can be used to explore a very large cellular automaton space. Although the idea itself of template has been introduced before, only now its conceptual underpinnings and computational robustness rendered the notion effective for practical use.


---

## Body

## 1. Introduction

Cellular automata (CAs) can be regarded as both fully discrete computational and dynamical systems, characterised by a local, totally decentralised action. What makes them an attractive object of study is the fact that, in spite of their extremely simple structure, they may present arbitrarily complex behaviour, depending on the local rule chosen to govern the system [1]. The rule acts by changing the discrete state of every position (a cell) of a regular grid, according to its current state and those of its neighbouring cells.The set of all possible one-dimensional CAs can be partitioned using two important parameters: the number of states the CA allows a cell to take on at any given time step and the size of its neighbourhood, defined by the number of neighbours a cell has to check in order to decide which state it will be at the next time step. Each resulting block of the partition defines a CA space or family.Except for the small elementary space (made up of only 256 one-dimensional rules, with 2 states per cells and 3 cells in the neighbourhood), whenever there is the necessity of searching for CAs with a given behaviour in a given space, one is overwhelmed by the very high number of possibilities to check. This is why many applications end up revolving around the elementary rules, as in [2].The approaches used to perform searches in larger spaces have usually been made automatic by means of search algorithms, especially evolutionary, designed to look for rules that would have particular emergent features, such as those that can be associated with the solution of particular computational problems [3], or the direct attempt to analyse constrained CA spaces, defined by required properties of the rule tables or the expected behaviour to be observed [4, 5]. In order to escape from the arbitrariness of the latter, different representational tools sometimes are employed, most notably the DeBruijn graphs, used in [6], to explore the parity problem’s solvability for CAs in different spaces, and the conditionally matching rules, explored in [7].Regardless of the case, the fact is that the possibility of representing families of CA rules in a compact way would be greatly beneficial, both theoretically and for practical applications. A particularly powerful representational tool in this context is thetemplate. First introduced in [8], templates are data structures which represent potentially extremely large sets of CAs, further allowing to combine and manipulate them with operations such as the intersection, before effectively enumerating the whole set.Even though the idea itself of template has been introduced before, only now its conceptual underpinnings and computational robustness rendered the notion effective for practical use. In tune with that, the idea has now been crystallised into an open-source package for the WolframMathematica system [9] calledCATemplates [10]. The explanations provided in this paper are partially based on the implementations used inCATemplates.Although cellular automata can be defined in any number of dimensions, here we focus on the one-dimensional case, first because the major benchmarking problems from the literature are one-dimensional and second because this is the case implemented inCATemplates.The rest of this paper is organised as follows. Section2 is a brief overview of cellular automata and their inner workings, Section 3 defines a cellular automata template, and Section 4 provides explanations about the operations applicable to them. Section 5 then presents examples of template builder functions, Section 6 discusses a sample application of templates to find rules that share both totality and captivity in extremely large CA spaces, and Section 7 closes the paper with some concluding remarks and ideas for future work.


## 2. Cellular Automata

Cellular automata are dynamical, decentralised systems, governed by simple, local rules. Given the relative simplicity of CAs, they serve as a good model to analyse how the interaction among simple components can give rise to complex behaviour in dynamical systems, in particular, how solutions to global problems like the density classification task arise [11].CAs are composed of a regular lattice of finite automata (thecells), whose states change with time, following a predetermined local rule. The lattice can be arranged in any number of dimensions and can have a finite or infinite number of cells. From now on, whenever a CA is mentioned, we always mean one-dimensional CAs (whose lattices are arranged as a line), each cell can take on a discrete state value, and the update is parallel, at discrete time steps.A CA’s cell state is usually represented by numbers in the[0,k-1] interval, or a colour from a set of k colours previously defined. The local rule of a CA acts on each cell’s neighbourhood, which is a set composed of the cell itself together with its 2r adjacent cells, with r being theradius of the rule, that is, the number of cells at each side. The fractional value .5 for r indicates that the neighbourhood is asymmetric, as in r=1.5, meaning that the center cell has 2 neighbours on one side and 1 on the other (inCATemplates, by convention, the left-hand side contains the larger number of neighbours).By defining a value fork and r, a space (or family) of CAs is established. Theelementary space is currently one of the most extensively studied CA families, as it is composed of only 256 rules, even though displaying a rich phenomenology [1].The size of a CA space is a function ofk and r. In the one-dimensional case, this means s(k,r)=kk⌊2r+1⌋. As a consequence, the increase of k or r quickly leads to exponentially large space sizes; for instance, the space of binary CAs with radius 2 is composed of 232 rules.Every CA’s temporal evolution is governed by a local rule. This local rule is usually represented as a rule table, consisting of state transitions that point every possible neighbourhood to an output state. At every time step, every cell in the lattice is updated according to its neighbourhood, following its state transition table.Since a rule table has to cover all possible neighborhoods in the lattice, it consists ofk⌊2r+1⌋ state transitions ordered using Wolfram’s lexicographic order, in which the first transition is the one corresponding to the neighbourhood formed only by cells in the k-1 state, and the last one is the transition corresponding to the neighbourhood of zeros. To illustrate the point, the rule table for elementary CA 184 is shown in Table 1.Table 1
Rule table for the elementary CA 184.
(1,1,1) 1  (1,1,0) 0  (1,0,1) 1  (1,0,0) 1  (0,1,1) 1  (0,1,0) 0  (0,0,1) 0  (0,0,0) 0It is possible to compress the rule table by using itsk-ary representation. By discarding Table 1’s first column, we are left with the outputs of each transition: (1,0,1,1,1,0,0,0). Since we are still following Wolram’s convention, we can switch freely between both representations. If interpreted as a binary number, this representation can be converted to its decimal form, 184, which is referred to as the rule (Wolfram) number.The nature of thes(k,r) function represents a great challenge when searching for specific sets of CAs. One of the employed strategies for this kind of search is to restrict these very large spaces into smaller ones, usingstatic properties of CAs. The template framework described in this paper aims to automate this process. Static properties are those we can draw directly from the rule table, instead of looking at the temporal evolution. This means that they determine specific ways a rule table should be built, so that the resulting rule would possess them. As will be detailed in Section 5, template builder functions use this idea in order to create templates representing specific subsets of CA spaces.


## 3. Cellular Automata Templates

A cellular automaton template (referred to simply astemplate from here on) is a data structure that allows for the representation of a (potentially large) subset of a CA’s family in a compact manner.Template builder functions are defined as a means to create templates of interesting subsets of CAs, usually following a well defined static property derived from CA’s rule tables. They are explained in detail in Section5.Two main operations are defined over templates: Expansion and Intersection. Expansion is used to convert a template into the rule set it represents, and Intersection is applied to two templates to generate a third, representing the rule set of the resulting intersection. Both operations are detailed in Section4.The template concept was first described in [8, 12] and has gone through significant improvements since then. For instance, the template’score, essentially what was described as the template itself in the original papers, is now a part of a tuple composed by important attributes, as shown in the definition below.Also, new template builder algorithms have been developed, the concept of expansion modifier functions has been implemented, and the intersection operation, at that time implicitly couched in terms of a superseded “composition” operation—which was just a part of the original template builder algorithms described in the original papers—has been made explicit and evolved into a generalised operation.Furthermore, the original work was totally restricted to binary rules, which no longer is the case; the code was completelyad hoc (and therefore, private to the authors), with no internal structure that would allow it to grow toward a usable and useful system, beyond its original conception; and only two rule properties have been accounted for (additional information about these two properties is given later in the paper).So, in its origin, there was a still immature but promising idea that was conveyed at the time to two distinct audiences: the early technical details of the implementation toMathematica users [8] and the actual idea and its prospects as a short communication to the cellular automata community [12]. From then on, the work developed, until reaching the required degree of maturation that it deserved, as embodied in the present report. All the further developments are now consolidated as a fully functional open-source implementation in the form of theCATemplates package [10], within WolframMathematica software [9].Armed with this framework, one can efficiently build and manipulate templates as needed and avoid the expensive enumeration of the sets they stand for until a template is obtained, representing a small enough rule set.Definition 1 (template).
A template is the tuple(k,r,c,e), where k and r are the number of states and the neighbourhood radius, respectively, of the cellular automata rules of the space that is being represented, c is the template core, and e is an expansion modifier function.Thecore is by far the most important part of a template. It is essentially a rule table in k-ary form with a twist: every output of this rule table is allowed to be a function of the other outputs. This is achieved by introducing variables semantically bounded across all transitions of the classical rule-table representation. By means of the core, a template is able to represent a set of CAs. The following template (T1) is an example:(1)T1=2,1.0,0,1-x1,0,1,x3,1,x1,0,IdentityMapper.TheIdentityMapper and other expansion modifier functions will be explained in more detail in Section 4.Remark. In theCATemplates package, k, r, and e may be omitted, in which case, the default values of k=2, r=1.0, and e=IdentityMapper are assumed; similarly, but for the sake of simplicity, from now on in this paper whenever we refer to a template’s core in isolation, say, c(T1), the reader should assume the same previous default values for the corresponding template (T1).We indicate the state transitions of the template’s core by an index, starting at 0, on the right-most position, up tok⌊2r+1⌋-1, on the left-most, so as to mirror their correspondence to the neighborhoods they represent. As such, whenever T1’s transition 0 is mentioned, we are referring to the first 0 that appears in T1’s core, from right to left. Transition 1 refers to x1, and so on.T 1’s transition 0 is a sample of afixed output. This means any CA with a value different from 0 on its rule table’s first transition—which is the same as the state transition (0,0,0) leading to 1—is not an element of the set represented by T1.T 1’s transition 1 is a sample of afree variable (x1). A free variable is assumed to represent any value in the range [0,k-1]. As a convention, free variables are indexed following the transition where they first appear. Were we to consider only T1’s first two transitions, we could say it represents the set {(0,0),(1,0)}, since the first transition is fixed and the second is a free variable.Transition 6 is a sample of afunction. As T1 is a binary template (since k=2), the expression 1-x1 means this transition will always be evaluated to the opposite of the value of transition 1. It is important to note that we could use any algebraic expression here, potentially referring to any other variable in the template, and we would still be able to derive the set this template represents. This is actually done in some template builder functions, as will be seen in Section 5.It follows from the previous observations thatT1 actually corresponds to the binary rule set {(0,1,0,1,0,1,0,0),(0,1,0,1,1,1,0,0),(0,0,0,1,0,1,1,0), (0,0,0,1,1,1,1,0)}, which could also be written as {22,30,84,92}, following Wolfram’s numbering convention.A template whose core is made of only free variables is called aBase Template and essentially represents the whole CA space given by k and r; for instance, theBase Template for the elementary CAs is(2)2,1.0,x7,x6,x5,x4,x3,x2,x1,x0,IdentityMapper.Base templates are often used by template builder functions as a starting point.


## 4. Template Operations

Currently, templates’ processing supports two operations: expansion (E) and intersection (I). This section presents details on how they work.


### 4.1. Expansion

Every template represents a setR of k-ary rule tables. This set is obtained by means of the expansion operation.Thei-th expansion of template T, denoted as Ei(T), begins with the extraction of all variables present in the template’s core, in a total of m variables. For instance, given the template’s core c(T1)=(0,1-x1,0,1,x3,1,x1,0), the ordered list of extracted variables would be (x3,x1), ordered by the variable’s index, in decreasing order. Next, i is converted to base k, padded with zeros to the left, up to achieving m digits. For i=2, we would have the ordered list of digits (1,0), since 10 is 2 in binary. We then pair the extracted variables with the digits in order and replace every occurrence of the variable with the corresponding value, like (0,1-0,0,1,1,1,0,0). Any algebraic expression left in the core is then resolved, resulting in E2(T1)=(0,1,0,1,1,1,0,0).With the process to find thei-th expansion defined, it is only a matter of mapping it over every number in the interval [0,km-1], and we have the set R of CA rule tables represented by the template. This is how the full expansion E(T) is implemented.Still consideringT1, since m=2, we only have k2=4 possible expansions for this template. By performing the expansion procedure with i∈{0,1,2,3}, we end up with the set R={(0,1,0,1,0,1,0,0),(0,1,0,1,1,1,0,0),(0,0,0,1,0,1,1,0), (0,0,0,1,1,1,1,0)}.Upon expansion, templates can generate invalid results; for instance, let us consider the template’s corec(Tinvalid)=(0,0,0,0,2-x3,1,1,1).Sincem=1 and k=2, this template has 2 possible expansions, namely, E(Tinvalid)={(0,0,0,0,2,1,1,1),(0,0,0,0,1,1,1,1)}; however, the set contains an invalid state transition, as it leads to the 2-state, which is not in the [0,k-1] range.Expansion modifier functions can be used as a mechanism by which the template provides auxiliary information for the expansion operation, in terms of some details it should abide by.Every template has at least one expansion modifier function defined. Whenever the expansion operation is performed on thei-th expansion, its result is passed on to the template’s expansion modifier function, which is defined by the template builder function.This means that every template itself is able to define specific behaviours to the expansion operation, deciding how to deal with unwanted results.Expansion modifier functions are currently divided into two categories:Mappers andFilters.


#### 4.1.1. Mappers

AMapper is a function that receives the i-th expansion result and performs some kind of transformation on it. So far, we have identified the need for two expansion modifier functions of the Mapper kind:ModKMapper andIdentityMapper.(i)
IdentityMapper simply receives the expansion and leaves it untouched.(ii)
ModKMapper performs the modulus operation on each transition of the expansion result using the template’s k as divisor, thus obtaining a valid expansion.As an example of the latter, let us defineTmodk as a variation of Tinvalid that usesModKMapper instead of theIdentityMapper:(3)Tmodk=2,1.0,0,0,0,0,2-x3,1,1,1,ModKMapper.Now, the result of expandingTmodk becomes(4)ETmodk=0,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1.


#### 4.1.2. Filters

AFilter is a function that checks the expansion result and decides whether it is an acceptable result for the given template. If it finds an unacceptable expansion candidate, it filters out this result, by removing it from the set R. So far, we have identified the need for two expansion modifier functions of the Filter kind:FilterKOutOfRange andFilterVariableAssignments.(i)
FilterKOutOfRange simply removes any invalid expansion. For instance, by defining TfilterK as a variation of Tinvalid that usesFilterKOutOfRange instead of theIdentityMapper, and this results in E(TfilterK)={(0,0,0,0,1,1,1,1)}.(ii)
FilterVariableAssignments serves a different kind of need. It allows for templates to define annotations on its core’s variables, which dictate the values from the [0,k-1] range the variable is allowed to have.The annotation referred to inFilterVariableAssignments is expressed with a special syntax on the template’s core. Consider the following template Tva and its i=0 expansion:(5)Tva=2,1.0,0,0,0,0,x3∈1,1,1,1,FilterVariableAssignments.The process should result in the expansion candidate (0,0,0,0,0∈{1},1,1,1). But since 0∈{1} is false,FilterVariableAssignments detects this as unacceptable and removes it from R.In the binary case,FilterVariableAssignments is seldom needed, since the expression xfree∈{0,1} is equivalent to a free variable xfree, and the expression xfixed∈{0} is equivalent to the fixed value 0.Therefore, this expansion modifier function becomes useful whenk>2, for various reasons. For further clarification, Section 5.2 discusses an application of this filter.


### 4.2. Intersection

Template intersection is a function of two templates, which results in a template whose associated setR is equivalent to intersecting the R sets of the two templates received as arguments. In another form,(6)IT1,T2=T3⇐ET3=ET1∩ET2.Template intersection initially consists of building an equation system with the template’s cores received as operands. The equation system is then submitted toMathematica’s Solve function [9], which solves it for the variables that admit a solution, and elicits the relations among the remaining variables. The resulting set of variable values and relations is then applied to any of the two operands, and the outcome is a new template representing only the intersection between both of the input templates.If the system has no solution, this means both templates represent disjointR sets and, by definition, do not intersect.As an example, consider the template coresc(T1)=(x7,0,x5,0,1,0,x2,x0) and c(T2)=(1,0,1-x1,1-x3,x3,0,x1,0). The associated equation system thus becomes (7)x7=10=0x5=1-x10=1-x31=x30=0x1=x1x0=0.The solution set of the equation system, as given byMathematica’s Solve, is S={x0=0,x3=1,x2=x1,x5=1-x1,x7=1}. We can then substitute the variables in c(T1) using this set, thus rendering the template’s core (1,0,1-x1,0,1,0,x1,0). Notice that the same result would be achieved had we applied the substitutions to c(T2).If a template’s core has variable restrictions, a second step is needed to guarantee that the solution found will not violate them.For instance, consider the templates’ coresc(Tr1) and c(Tr1), both with restricted variables: c(Tr1)=(x7,0,x5,0,1,0,x2∈{0,1},x0) and c(Tr2)=(1,0,1-x1,1-x3,x3,0,x1∈{0},0). To intersect Tr1 and Tr2, we first extract the variable restriction expressions and then build and solve the system as usual. This time, however, the substitutions are applied to both arguments, therefore resulting in the set {(1,0,1-x1,0,1,0,x1∈{0,1},0),(1,0,1-x1,0,1,0,x1∈{0},0)}.Now, we extract variable restriction expressions and create a second equation system, whose solutions indicate which values the variables may have. In the example, the set of expressions{x1∈{0,1},x1∈0} would be extracted, thus yielding the equation system: (8)x1=1∨x1=0x1=0By solving this system, the solution set S={x1=0} can finally be applied to c(Tr1), yielding (1,0,1,0,1,0,0,0) as the result.


## 4.1. Expansion

Every template represents a setR of k-ary rule tables. This set is obtained by means of the expansion operation.Thei-th expansion of template T, denoted as Ei(T), begins with the extraction of all variables present in the template’s core, in a total of m variables. For instance, given the template’s core c(T1)=(0,1-x1,0,1,x3,1,x1,0), the ordered list of extracted variables would be (x3,x1), ordered by the variable’s index, in decreasing order. Next, i is converted to base k, padded with zeros to the left, up to achieving m digits. For i=2, we would have the ordered list of digits (1,0), since 10 is 2 in binary. We then pair the extracted variables with the digits in order and replace every occurrence of the variable with the corresponding value, like (0,1-0,0,1,1,1,0,0). Any algebraic expression left in the core is then resolved, resulting in E2(T1)=(0,1,0,1,1,1,0,0).With the process to find thei-th expansion defined, it is only a matter of mapping it over every number in the interval [0,km-1], and we have the set R of CA rule tables represented by the template. This is how the full expansion E(T) is implemented.Still consideringT1, since m=2, we only have k2=4 possible expansions for this template. By performing the expansion procedure with i∈{0,1,2,3}, we end up with the set R={(0,1,0,1,0,1,0,0),(0,1,0,1,1,1,0,0),(0,0,0,1,0,1,1,0), (0,0,0,1,1,1,1,0)}.Upon expansion, templates can generate invalid results; for instance, let us consider the template’s corec(Tinvalid)=(0,0,0,0,2-x3,1,1,1).Sincem=1 and k=2, this template has 2 possible expansions, namely, E(Tinvalid)={(0,0,0,0,2,1,1,1),(0,0,0,0,1,1,1,1)}; however, the set contains an invalid state transition, as it leads to the 2-state, which is not in the [0,k-1] range.Expansion modifier functions can be used as a mechanism by which the template provides auxiliary information for the expansion operation, in terms of some details it should abide by.Every template has at least one expansion modifier function defined. Whenever the expansion operation is performed on thei-th expansion, its result is passed on to the template’s expansion modifier function, which is defined by the template builder function.This means that every template itself is able to define specific behaviours to the expansion operation, deciding how to deal with unwanted results.Expansion modifier functions are currently divided into two categories:Mappers andFilters.


### 4.1.1. Mappers

AMapper is a function that receives the i-th expansion result and performs some kind of transformation on it. So far, we have identified the need for two expansion modifier functions of the Mapper kind:ModKMapper andIdentityMapper.(i)
IdentityMapper simply receives the expansion and leaves it untouched.(ii)
ModKMapper performs the modulus operation on each transition of the expansion result using the template’s k as divisor, thus obtaining a valid expansion.As an example of the latter, let us defineTmodk as a variation of Tinvalid that usesModKMapper instead of theIdentityMapper:(3)Tmodk=2,1.0,0,0,0,0,2-x3,1,1,1,ModKMapper.Now, the result of expandingTmodk becomes(4)ETmodk=0,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1.


### 4.1.2. Filters

AFilter is a function that checks the expansion result and decides whether it is an acceptable result for the given template. If it finds an unacceptable expansion candidate, it filters out this result, by removing it from the set R. So far, we have identified the need for two expansion modifier functions of the Filter kind:FilterKOutOfRange andFilterVariableAssignments.(i)
FilterKOutOfRange simply removes any invalid expansion. For instance, by defining TfilterK as a variation of Tinvalid that usesFilterKOutOfRange instead of theIdentityMapper, and this results in E(TfilterK)={(0,0,0,0,1,1,1,1)}.(ii)
FilterVariableAssignments serves a different kind of need. It allows for templates to define annotations on its core’s variables, which dictate the values from the [0,k-1] range the variable is allowed to have.The annotation referred to inFilterVariableAssignments is expressed with a special syntax on the template’s core. Consider the following template Tva and its i=0 expansion:(5)Tva=2,1.0,0,0,0,0,x3∈1,1,1,1,FilterVariableAssignments.The process should result in the expansion candidate (0,0,0,0,0∈{1},1,1,1). But since 0∈{1} is false,FilterVariableAssignments detects this as unacceptable and removes it from R.In the binary case,FilterVariableAssignments is seldom needed, since the expression xfree∈{0,1} is equivalent to a free variable xfree, and the expression xfixed∈{0} is equivalent to the fixed value 0.Therefore, this expansion modifier function becomes useful whenk>2, for various reasons. For further clarification, Section 5.2 discusses an application of this filter.


## 4.1.1. Mappers

AMapper is a function that receives the i-th expansion result and performs some kind of transformation on it. So far, we have identified the need for two expansion modifier functions of the Mapper kind:ModKMapper andIdentityMapper.(i)
IdentityMapper simply receives the expansion and leaves it untouched.(ii)
ModKMapper performs the modulus operation on each transition of the expansion result using the template’s k as divisor, thus obtaining a valid expansion.As an example of the latter, let us defineTmodk as a variation of Tinvalid that usesModKMapper instead of theIdentityMapper:(3)Tmodk=2,1.0,0,0,0,0,2-x3,1,1,1,ModKMapper.Now, the result of expandingTmodk becomes(4)ETmodk=0,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1.


## 4.1.2. Filters

AFilter is a function that checks the expansion result and decides whether it is an acceptable result for the given template. If it finds an unacceptable expansion candidate, it filters out this result, by removing it from the set R. So far, we have identified the need for two expansion modifier functions of the Filter kind:FilterKOutOfRange andFilterVariableAssignments.(i)
FilterKOutOfRange simply removes any invalid expansion. For instance, by defining TfilterK as a variation of Tinvalid that usesFilterKOutOfRange instead of theIdentityMapper, and this results in E(TfilterK)={(0,0,0,0,1,1,1,1)}.(ii)
FilterVariableAssignments serves a different kind of need. It allows for templates to define annotations on its core’s variables, which dictate the values from the [0,k-1] range the variable is allowed to have.The annotation referred to inFilterVariableAssignments is expressed with a special syntax on the template’s core. Consider the following template Tva and its i=0 expansion:(5)Tva=2,1.0,0,0,0,0,x3∈1,1,1,1,FilterVariableAssignments.The process should result in the expansion candidate (0,0,0,0,0∈{1},1,1,1). But since 0∈{1} is false,FilterVariableAssignments detects this as unacceptable and removes it from R.In the binary case,FilterVariableAssignments is seldom needed, since the expression xfree∈{0,1} is equivalent to a free variable xfree, and the expression xfixed∈{0} is equivalent to the fixed value 0.Therefore, this expansion modifier function becomes useful whenk>2, for various reasons. For further clarification, Section 5.2 discusses an application of this filter.


## 4.2. Intersection

Template intersection is a function of two templates, which results in a template whose associated setR is equivalent to intersecting the R sets of the two templates received as arguments. In another form,(6)IT1,T2=T3⇐ET3=ET1∩ET2.Template intersection initially consists of building an equation system with the template’s cores received as operands. The equation system is then submitted toMathematica’s Solve function [9], which solves it for the variables that admit a solution, and elicits the relations among the remaining variables. The resulting set of variable values and relations is then applied to any of the two operands, and the outcome is a new template representing only the intersection between both of the input templates.If the system has no solution, this means both templates represent disjointR sets and, by definition, do not intersect.As an example, consider the template coresc(T1)=(x7,0,x5,0,1,0,x2,x0) and c(T2)=(1,0,1-x1,1-x3,x3,0,x1,0). The associated equation system thus becomes (7)x7=10=0x5=1-x10=1-x31=x30=0x1=x1x0=0.The solution set of the equation system, as given byMathematica’s Solve, is S={x0=0,x3=1,x2=x1,x5=1-x1,x7=1}. We can then substitute the variables in c(T1) using this set, thus rendering the template’s core (1,0,1-x1,0,1,0,x1,0). Notice that the same result would be achieved had we applied the substitutions to c(T2).If a template’s core has variable restrictions, a second step is needed to guarantee that the solution found will not violate them.For instance, consider the templates’ coresc(Tr1) and c(Tr1), both with restricted variables: c(Tr1)=(x7,0,x5,0,1,0,x2∈{0,1},x0) and c(Tr2)=(1,0,1-x1,1-x3,x3,0,x1∈{0},0). To intersect Tr1 and Tr2, we first extract the variable restriction expressions and then build and solve the system as usual. This time, however, the substitutions are applied to both arguments, therefore resulting in the set {(1,0,1-x1,0,1,0,x1∈{0,1},0),(1,0,1-x1,0,1,0,x1∈{0},0)}.Now, we extract variable restriction expressions and create a second equation system, whose solutions indicate which values the variables may have. In the example, the set of expressions{x1∈{0,1},x1∈0} would be extracted, thus yielding the equation system: (8)x1=1∨x1=0x1=0By solving this system, the solution set S={x1=0} can finally be applied to c(Tr1), yielding (1,0,1,0,1,0,0,0) as the result.


## 5. Template Builders

So far we have seen how templates can be built in order to represent specific subsets of CA families. We can now go about making evident the true power of templates, by considering template builder functions.Template builder functions are algorithms tailored to generate templates for specific subsets of CAs that share a given static property.Currently, six template builders for static properties are implemented, associated to rules of the following kinds: captive; totalistic; outer-totalistic; number conserving; colorblind; and maximum internal symmetry values (see [1]) for reflection, conjugacy, and their composition. The latter two are not discussed herein partly because we have already discussed them previously (see [8]), and, at least in the context number conservation, the corresponding template builder simply did not change since its conception. However, the builder for rule table symmetries has undergone a generalisation that now allows for any value of symmetry to be accounted for, not only maximum. As such, theCATemplates package contains theSymmetryTemplate builder, fully available for use, including its corresponding documentation, but we decided not to include it in the paper because it cannot yet handle arbitrary number of states in the case of conjugation.So, this section discusses builder functions for totalistic, outer-totalistic, captive, and colorblind templates.


### 5.1. Template Builder for Totalistic and Outer-Totalistic CAs

Definition 2 (totality).
A totalistic CA—or, alternatively, a CA that presents the totality property—is one whose state transitions only depend on the sum of the state values of the cells in a given neighbourhood.Formally, letf be the local transition function of a CA, defined over the set N of possible neighborhoods for the CA’s space. Let n be the size of a neighbourhood of N. Let A=(α1,…,αn) and B=(β1,…,βn) be neighborhoods of N. A CA is said to be totalistic if and only if the following condition is true:(9)∀A,B∈N,∑i=1nαi=∑j=1nβj⇔fA=fB.Since totality is a static property, we can derive a general algorithm to find all rule tables of CAs that share thetotality property, given a value for k and r.The algorithm receives as arguments the values ofk and r for which the template will be generated. It then proceeds to enumerate all possible neighborhoods of the defined space and calculates their sum.Now, for every sum value found in the previous step, the algorithm picks the neighbourhood representing the smallestk-ary number and assigns a variable corresponding to that neighbourhood’s decimal value to all of the state transitions that shared a result with it. For instance, let us consider all neighborhoods of the elementary space whose states sum equals 2: {(1,1,0),(1,0,1),(0,1,1)}. Since the smallest neighbourhood in this set is (0,1,1), which is decimal 3, we assign to their respective transitions the result x3.The template’s core for the elementary space becomes(10)cTtotalisticES=x7,x3,x3,x1,x3,x1,x1,x0.Upon expansion, this template yields the rule tables of the 16 totalistic elementary CAs. Notice that this template’s core is composed of only free variables and references to other free variables. This being the case, every expansion of this template shall yield a valid result, excluding the need to define any expansion modifier function other thanIdentityMapper.Fork=3 and r=1, the resulting template would be(11)Ttot31=3,1.0,x26,x17,x8,x17,x8,x5,x8,x5,x2,x17,x8,x5,x8,x5,x2,x5,x2,x1,x8,x5,x2,x5,x2,x1,x2,x1,x0,IdentityMapper.Upon expansion, this template yields the2187 totalistic rules of the referred space.Definition 3 (outer-totality).
An outer-totalistic CA—or, alternatively, a CA that presents the outer-totality property—is one whose local rule considers the sum of the state values of the external cells of a neighbourhood (i.e., those except the center cell), in addition to the state value of the center cell itself.Formally, letf be the local transition function of a CA, defined over the set N of possible neighborhoods for the CA’s space. Let n be the size of a neighbourhood of N, and let m=⌈n/2⌉ be the index of the cell that is meant to undergo a state change (i.e., the center cell when n is an odd number). Let A=(α1,…,αm,…,αn) and B=(β1,…,βm,…,βn) be neighborhoods of N. A CA is said to be outer-totalistic if and only if the following condition is true:(12)∀A,B∈N,∑i=1m-1αi+∑i=m+1nαi=∑j=1m-1βj+∑j=m+1nβj∧αm=βm⇔fA=fB.The algorithm for outer-totalistic templates is almost the same as the one for totalistic rules, with the exception that it considers the sum of external cells in the neighbourhood instead of its entirety.The algorithm’s output for the elementary space is(13)cTouter-totalisticES=x7,x3,x5,x1,x3,x2,x1,x0.Upon expansion, this template generates the 64 outer-totalistic elementary CAs.For reference, here is the result fork=3 and r=1 which, after expansion, would yield the 14,348,907 outer-totalistic rules of the space, since 15 distinct variables are present in the template:(14)Touter-tot31=3,1.0,x26,x17,x8,x23,x14,x5,x20,x11,x2,x17,x8,x7,x14,x5,x4,x11,x2,x1,x8,x7,x6,x5,x4,x3,x2,x1,x0,IdentityMapper.


### 5.2. Template Builder for Captive CAs

Definition 4 (captivity [13]).
A CA is said to be captive—or, alternatively, to have the captivity static property—when every transition of its rule table outputs a state that appears in the corresponding neighbourhood.Formally, iff is the local transition function of a CA, A=(α1,…,αm,…,αn) is a neighbourhood of size n, out of all possible neighborhoods N, and β is an arbitrary state, a CA is said to be captive if and only if the following condition is true:(15)∀A∈N,fα1,…,αn=β⇔β∈α1,…,αn.In the binary case, this naturally simplifies to the fact that every CA withf(01,02,…,0n)=0 and f(11,12,…,1n)=1 is captive, for any radius r.As a static property, a general algorithm to find templates of captive CAs for a given space does exist. As such, the algorithm receives the values fork and r and starts by generating all possible neighborhoods for the space.It then uses the following simple rules to decide how to transform this neighbourhood in a template output:(i)
If the neighbourhood is homogeneous, like1,1,1, the transition should output the only state that appears in the neighbourhood 1.(ii)
If the neighbourhood is composed of all of the values in the interval[0,k-1], like (1,2,0) for k=3 and r=1, the transition should output a free variable, indexed by the decimal value of the neighbourhood, namely, x15 (since 120 in base k=3 corresponds to the decimal 15).(iii)
If the neighbourhood is composed of only some of the possible states, the states of the interval[0,k-1], like (0,2,0) for k=3 and r=1, the output should be a variable indexed by the neighbourhood, this time restricted by the present values (x6∈{0,2}). This type of neighbourhood only appears when k>2.Note that since this template uses restricted variables, it must use theFilterVariableAssignments expansion modifier function.As a result of all the latter, the captivity template for the elementary space becomes(16)Tcaptive=2,1.0,1,x6,x5,x4,x3,x2,x1,0,FilterVariableAssignments,while, for k=3 and r=1, the template is(17)Tcaptive31=3,1.0,2,x25∈1,2,x24∈0,2,x23∈1,2,x22∈1,2,x21,x20∈0,2,x19,x18∈0,2,x17∈1,2,x16∈1,2,x15,x14∈1,2,1,x12∈0,1,x11,x10∈0,1,x9∈0,1,x8∈0,2,x7,x6∈0,2,x5,x4∈0,1,x3∈0,1,x2∈0,2,x1∈0,1,0,FilterNotAllowed.


### 5.3. Template Builder for Colorblind CAs

In order to fully grasp the notion of colorblind rules, let us first discuss the meaning of permutations in the context of CAs.Definition 5 (colour permutation (π)).
Let frameworkK be the set of possible states for a CA in the range [0,k-1]. A colour permutation π is a bijective function of K to itself, which can be written as a set of rules of the form ki→kj, meaning that a cell in state ki should be switched to state kj when this permutation is applied.For instance, a valid permutation for the case whereK={0,1,2} is π1={0→1,1→2,2→0}.It is important to notice that every colour permutation can be represented by an algebraic function that interpolates the points defined by the permutation. For instance,π1 could be written as π1(x)=1+(1-3/2(-1+x))x.Definition 6 (symmetric group (SK)).
The symmetric groupSK, of a set K, is the set of all possible permutations over K.For instance, the symmetric group forK={0,1,2} is(18)SK=0→0,1→1,2→2,0→0,1→2,2→1,0→1,1→0,2→2,0→1,1→2,2→0,0→2,1→0,2→1,0→2,1→1,2→0.Definition 7 (neighbourhood permutation (ρ(π))).
Letπ be a colour permutation and let N be the set of all possible neighborhoods for a given CA. The neighbourhood permutation ρ(π) is a permutation N that uses π to transform ni∈N into neighbourhood nj∈N, by applying π to every cell of ni.For instance, withK={0,1,2}, r=1, and π1={(0,1,2)}, a valid transformation due to ρ(π1) would be (0,2,2)→(1,0,0). The other transformations can be derived by applying the same reasoning to all of the neighborhoods of N.Definition 8 (cycle notation of a permutation).
A permutation can be written by means of a cycle notation, formed by a set of vectors that represent cycles associated with the permutation.For instance, the colour permutationπ2={0→1,1→0,2→2} can be written as π2={(0,1),(2)}, where each vector has the form (xi1,xi2,…,xij), 1≤j≤k, and represents a cycle due to the permutation, namely, the two-step cycle 0→1→0, and the self-loop 2→2. Similarly, The previous π1 permutation would be written in cycle notation as π1={(0,1,2)}.As for neighbourhood permutations,ρ(π1), for example, would be represented as follows:(19)ρπ1=0,2,2,1,0,0,2,1,1,0,2,1,1,0,2,2,1,0,0,2,0,1,0,1,2,1,2,0,1,2,1,2,0,2,0,1,0,1,1,1,2,2,2,0,0,0,1,0,1,2,1,2,0,2,0,0,2,1,1,0,2,2,1,0,0,1,1,1,2,2,2,0,0,0,0,1,1,1,2,2,2.With the previous characterisations, we can now define color blindness.Definition 9 (color blindness [14]).
A CA whose cells can be in any of the states of the setK is said to be colorblind—or, alternatively, to possess the color blindness property—if its space-time evolution does not change, unless by a colour change, after applying any neighbourhood permutation ρ(π),π∈SK, to all state transitions that define its rule table.Notice that, for a CA to be invariant toρ(π1), its rule table’s outputs oi should be consistent with the cycles formed by the application of ρ(π1) over its neighborhoods bi, i being the index of the state transition on the CA’s rule table.In other words, for a rule to be invariant toπ1, the output of, say, neighbourhood (0,2,2), should be equal to the application of π1 to the output of neighbourhood (1,0,0), since (0,2,2) is transformed into (1,0,0) due to π1; for the same reason, the output of (1,0,0) should be equal to the application of π1 to the output of neighbourhood (2,1,1). The same happens, analogously, for the remaining cycles of ρ(π1).Now, in order to generate a template representing CAs that are invariant to the neighbourhood permutationρ(π1), we need to assign an output to every neighbourhood and derive a rule table that could be turned into a template.So that outputs followρ(π1), we use its cycle notation representation to assign to every cycle start a free variable, indexed by its corresponding neighbourhood’s decimal representation, ending up with a tuple formed by neighbourhood and output. The (0,2,2) neighbourhood, being a cycle start, is turned into the tuple ((0,2,2),x8), for instance.For every remaining neighbourhood in a cycle, we now applyπ1 to the free variable found in the previous step d times, d being the distance from this neighbourhood to the start of the cycle. The cycle ((0,2,2),(1,0,0),(2,1,1)) is turned into (((0,2,2),x8),((1,0,0),π1(x8)),((2,1,1),π1(π1(x8)))), for instance.Applying this procedure to every cycle ofπ1, we obtain the set:(20)0,2,2,x8,1,0,0,π1x8,2,1,1,ππ1x8,0,2,1,x7,1,0,2,π1x7,2,1,0,ππ1x7,0,2,0,x6,1,0,1,π1x6,2,1,2,ππ1x6,0,1,2,x5,1,2,0,π1x5,2,0,1,ππ1x5,0,1,1,x4,1,2,2,π1x4,2,0,0,ππ1x4,0,1,0,x3,1,2,1,π1x3,2,0,2,ππ1x3,0,0,2,x2,1,1,0,π1x2,2,2,1,ππ1x2,0,0,1,x1,1,1,2,π1x1,2,2,0,ππ1x1,0,0,0,x0,1,1,1,π1x0,2,2,2,ππ1x0.We can now flatten a level of this set and turn it into an ordered list sorted lexicographically by neighbourhood. This procedure yields the rule table shown in Table 2.Table 2
Rule table for the template representative of CAs invariant toπ1.
(2, 2, 2) π ( π 1 ( x 0 )  (2, 2, 1) π ( π 1 ( x 2 )  (2, 2, 0) π ( π 1 ( x 1 )  (2, 1, 2) π ( π 1 ( x 6 )  (2, 1, 1) π ( π 1 ( x 8 )  (2, 1, 0) π ( π 1 ( x 7 )  (2, 0, 2) π ( π 1 ( x 3 )  (2, 0, 1) π ( π 1 ( x 5 )  (2, 0, 0) π ( π 1 ( x 4 )  (1, 2, 2) π 1 ( x 4 )  (1, 2, 1) π 1 ( x 3 )  (1, 2, 0) π 1 ( x 5 )  (1, 1, 2) π 1 ( x 1 )  (1, 1, 1) π 1 ( x 0 )  (1, 1, 0) π 1 ( x 2 )  (1, 0, 2) π 1 ( x 7 )  (1, 0, 1) π 1 ( x 6 )  (1, 0, 0) π 1 ( x 8 )  (0, 2, 2) x 8  (0, 2, 1) x 7  (0, 2, 0) x 6  (0, 1, 2) x 5  (0, 1, 1) x 4  (0, 1, 0) x 3  (0, 0, 2) x 2  (0, 0, 1) x 1  (0, 0, 0) x 0The core of a template for CAs invariant toρ(π1) can now be found by compressing this rule table into its k-ary form:(21)Tρπ1=ππ1x0,ππ1x2,ππ1x1,ππ1x6,ππ1x8,ππ1x7,ππ1x3,ππ1x5,ππ1x4,π1x4,π1x3,π1x5,π1x1,π1x0,π1x2,π1x7,π1x6,π1x8,x8,x7,x6,x5,x4,x3,x2,x1,x0Remember from Definition 5 that any permutation π can be represented by an algebraic function, which is the actual representation used by the algorithm. We use the π notation here since it is compact and serves the explanation’s purpose.The same procedure can now be repeated for every permutation of theSk set, essentially mapping each permutation of the set to a corresponding template of CAs invariant to that permutation. It is now only a matter of intersecting all of the templates found, and the result is a template that represents all colorblind rules of the space defined by k and r.When applied tok=2 and r=1, we obtain(22)Tcolourblind=1-x0,1-x1,1-x2,1-x3,x3,x2,x1,x0,whereas, for k=3 and r=1, the result becomes(23)Tcolourblind31=2,2-x1,2-2x1,2-x3,2-x4,2-x5,2-2,x3,2-2x5,2-2x4,1-2x4,1-2x3,1-2x5,1-2x1,1,1+2x1,1+2x5,1+2x3,1+2x4,2x4,2x5,2x3,x5,x4,x3,2x1,x1,0.


## 5.1. Template Builder for Totalistic and Outer-Totalistic CAs

Definition 2 (totality).
A totalistic CA—or, alternatively, a CA that presents the totality property—is one whose state transitions only depend on the sum of the state values of the cells in a given neighbourhood.Formally, letf be the local transition function of a CA, defined over the set N of possible neighborhoods for the CA’s space. Let n be the size of a neighbourhood of N. Let A=(α1,…,αn) and B=(β1,…,βn) be neighborhoods of N. A CA is said to be totalistic if and only if the following condition is true:(9)∀A,B∈N,∑i=1nαi=∑j=1nβj⇔fA=fB.Since totality is a static property, we can derive a general algorithm to find all rule tables of CAs that share thetotality property, given a value for k and r.The algorithm receives as arguments the values ofk and r for which the template will be generated. It then proceeds to enumerate all possible neighborhoods of the defined space and calculates their sum.Now, for every sum value found in the previous step, the algorithm picks the neighbourhood representing the smallestk-ary number and assigns a variable corresponding to that neighbourhood’s decimal value to all of the state transitions that shared a result with it. For instance, let us consider all neighborhoods of the elementary space whose states sum equals 2: {(1,1,0),(1,0,1),(0,1,1)}. Since the smallest neighbourhood in this set is (0,1,1), which is decimal 3, we assign to their respective transitions the result x3.The template’s core for the elementary space becomes(10)cTtotalisticES=x7,x3,x3,x1,x3,x1,x1,x0.Upon expansion, this template yields the rule tables of the 16 totalistic elementary CAs. Notice that this template’s core is composed of only free variables and references to other free variables. This being the case, every expansion of this template shall yield a valid result, excluding the need to define any expansion modifier function other thanIdentityMapper.Fork=3 and r=1, the resulting template would be(11)Ttot31=3,1.0,x26,x17,x8,x17,x8,x5,x8,x5,x2,x17,x8,x5,x8,x5,x2,x5,x2,x1,x8,x5,x2,x5,x2,x1,x2,x1,x0,IdentityMapper.Upon expansion, this template yields the2187 totalistic rules of the referred space.Definition 3 (outer-totality).
An outer-totalistic CA—or, alternatively, a CA that presents the outer-totality property—is one whose local rule considers the sum of the state values of the external cells of a neighbourhood (i.e., those except the center cell), in addition to the state value of the center cell itself.Formally, letf be the local transition function of a CA, defined over the set N of possible neighborhoods for the CA’s space. Let n be the size of a neighbourhood of N, and let m=⌈n/2⌉ be the index of the cell that is meant to undergo a state change (i.e., the center cell when n is an odd number). Let A=(α1,…,αm,…,αn) and B=(β1,…,βm,…,βn) be neighborhoods of N. A CA is said to be outer-totalistic if and only if the following condition is true:(12)∀A,B∈N,∑i=1m-1αi+∑i=m+1nαi=∑j=1m-1βj+∑j=m+1nβj∧αm=βm⇔fA=fB.The algorithm for outer-totalistic templates is almost the same as the one for totalistic rules, with the exception that it considers the sum of external cells in the neighbourhood instead of its entirety.The algorithm’s output for the elementary space is(13)cTouter-totalisticES=x7,x3,x5,x1,x3,x2,x1,x0.Upon expansion, this template generates the 64 outer-totalistic elementary CAs.For reference, here is the result fork=3 and r=1 which, after expansion, would yield the 14,348,907 outer-totalistic rules of the space, since 15 distinct variables are present in the template:(14)Touter-tot31=3,1.0,x26,x17,x8,x23,x14,x5,x20,x11,x2,x17,x8,x7,x14,x5,x4,x11,x2,x1,x8,x7,x6,x5,x4,x3,x2,x1,x0,IdentityMapper.


## 5.2. Template Builder for Captive CAs

Definition 4 (captivity [13]).
A CA is said to be captive—or, alternatively, to have the captivity static property—when every transition of its rule table outputs a state that appears in the corresponding neighbourhood.Formally, iff is the local transition function of a CA, A=(α1,…,αm,…,αn) is a neighbourhood of size n, out of all possible neighborhoods N, and β is an arbitrary state, a CA is said to be captive if and only if the following condition is true:(15)∀A∈N,fα1,…,αn=β⇔β∈α1,…,αn.In the binary case, this naturally simplifies to the fact that every CA withf(01,02,…,0n)=0 and f(11,12,…,1n)=1 is captive, for any radius r.As a static property, a general algorithm to find templates of captive CAs for a given space does exist. As such, the algorithm receives the values fork and r and starts by generating all possible neighborhoods for the space.It then uses the following simple rules to decide how to transform this neighbourhood in a template output:(i)
If the neighbourhood is homogeneous, like1,1,1, the transition should output the only state that appears in the neighbourhood 1.(ii)
If the neighbourhood is composed of all of the values in the interval[0,k-1], like (1,2,0) for k=3 and r=1, the transition should output a free variable, indexed by the decimal value of the neighbourhood, namely, x15 (since 120 in base k=3 corresponds to the decimal 15).(iii)
If the neighbourhood is composed of only some of the possible states, the states of the interval[0,k-1], like (0,2,0) for k=3 and r=1, the output should be a variable indexed by the neighbourhood, this time restricted by the present values (x6∈{0,2}). This type of neighbourhood only appears when k>2.Note that since this template uses restricted variables, it must use theFilterVariableAssignments expansion modifier function.As a result of all the latter, the captivity template for the elementary space becomes(16)Tcaptive=2,1.0,1,x6,x5,x4,x3,x2,x1,0,FilterVariableAssignments,while, for k=3 and r=1, the template is(17)Tcaptive31=3,1.0,2,x25∈1,2,x24∈0,2,x23∈1,2,x22∈1,2,x21,x20∈0,2,x19,x18∈0,2,x17∈1,2,x16∈1,2,x15,x14∈1,2,1,x12∈0,1,x11,x10∈0,1,x9∈0,1,x8∈0,2,x7,x6∈0,2,x5,x4∈0,1,x3∈0,1,x2∈0,2,x1∈0,1,0,FilterNotAllowed.


## 5.3. Template Builder for Colorblind CAs

In order to fully grasp the notion of colorblind rules, let us first discuss the meaning of permutations in the context of CAs.Definition 5 (colour permutation (π)).
Let frameworkK be the set of possible states for a CA in the range [0,k-1]. A colour permutation π is a bijective function of K to itself, which can be written as a set of rules of the form ki→kj, meaning that a cell in state ki should be switched to state kj when this permutation is applied.For instance, a valid permutation for the case whereK={0,1,2} is π1={0→1,1→2,2→0}.It is important to notice that every colour permutation can be represented by an algebraic function that interpolates the points defined by the permutation. For instance,π1 could be written as π1(x)=1+(1-3/2(-1+x))x.Definition 6 (symmetric group (SK)).
The symmetric groupSK, of a set K, is the set of all possible permutations over K.For instance, the symmetric group forK={0,1,2} is(18)SK=0→0,1→1,2→2,0→0,1→2,2→1,0→1,1→0,2→2,0→1,1→2,2→0,0→2,1→0,2→1,0→2,1→1,2→0.Definition 7 (neighbourhood permutation (ρ(π))).
Letπ be a colour permutation and let N be the set of all possible neighborhoods for a given CA. The neighbourhood permutation ρ(π) is a permutation N that uses π to transform ni∈N into neighbourhood nj∈N, by applying π to every cell of ni.For instance, withK={0,1,2}, r=1, and π1={(0,1,2)}, a valid transformation due to ρ(π1) would be (0,2,2)→(1,0,0). The other transformations can be derived by applying the same reasoning to all of the neighborhoods of N.Definition 8 (cycle notation of a permutation).
A permutation can be written by means of a cycle notation, formed by a set of vectors that represent cycles associated with the permutation.For instance, the colour permutationπ2={0→1,1→0,2→2} can be written as π2={(0,1),(2)}, where each vector has the form (xi1,xi2,…,xij), 1≤j≤k, and represents a cycle due to the permutation, namely, the two-step cycle 0→1→0, and the self-loop 2→2. Similarly, The previous π1 permutation would be written in cycle notation as π1={(0,1,2)}.As for neighbourhood permutations,ρ(π1), for example, would be represented as follows:(19)ρπ1=0,2,2,1,0,0,2,1,1,0,2,1,1,0,2,2,1,0,0,2,0,1,0,1,2,1,2,0,1,2,1,2,0,2,0,1,0,1,1,1,2,2,2,0,0,0,1,0,1,2,1,2,0,2,0,0,2,1,1,0,2,2,1,0,0,1,1,1,2,2,2,0,0,0,0,1,1,1,2,2,2.With the previous characterisations, we can now define color blindness.Definition 9 (color blindness [14]).
A CA whose cells can be in any of the states of the setK is said to be colorblind—or, alternatively, to possess the color blindness property—if its space-time evolution does not change, unless by a colour change, after applying any neighbourhood permutation ρ(π),π∈SK, to all state transitions that define its rule table.Notice that, for a CA to be invariant toρ(π1), its rule table’s outputs oi should be consistent with the cycles formed by the application of ρ(π1) over its neighborhoods bi, i being the index of the state transition on the CA’s rule table.In other words, for a rule to be invariant toπ1, the output of, say, neighbourhood (0,2,2), should be equal to the application of π1 to the output of neighbourhood (1,0,0), since (0,2,2) is transformed into (1,0,0) due to π1; for the same reason, the output of (1,0,0) should be equal to the application of π1 to the output of neighbourhood (2,1,1). The same happens, analogously, for the remaining cycles of ρ(π1).Now, in order to generate a template representing CAs that are invariant to the neighbourhood permutationρ(π1), we need to assign an output to every neighbourhood and derive a rule table that could be turned into a template.So that outputs followρ(π1), we use its cycle notation representation to assign to every cycle start a free variable, indexed by its corresponding neighbourhood’s decimal representation, ending up with a tuple formed by neighbourhood and output. The (0,2,2) neighbourhood, being a cycle start, is turned into the tuple ((0,2,2),x8), for instance.For every remaining neighbourhood in a cycle, we now applyπ1 to the free variable found in the previous step d times, d being the distance from this neighbourhood to the start of the cycle. The cycle ((0,2,2),(1,0,0),(2,1,1)) is turned into (((0,2,2),x8),((1,0,0),π1(x8)),((2,1,1),π1(π1(x8)))), for instance.Applying this procedure to every cycle ofπ1, we obtain the set:(20)0,2,2,x8,1,0,0,π1x8,2,1,1,ππ1x8,0,2,1,x7,1,0,2,π1x7,2,1,0,ππ1x7,0,2,0,x6,1,0,1,π1x6,2,1,2,ππ1x6,0,1,2,x5,1,2,0,π1x5,2,0,1,ππ1x5,0,1,1,x4,1,2,2,π1x4,2,0,0,ππ1x4,0,1,0,x3,1,2,1,π1x3,2,0,2,ππ1x3,0,0,2,x2,1,1,0,π1x2,2,2,1,ππ1x2,0,0,1,x1,1,1,2,π1x1,2,2,0,ππ1x1,0,0,0,x0,1,1,1,π1x0,2,2,2,ππ1x0.We can now flatten a level of this set and turn it into an ordered list sorted lexicographically by neighbourhood. This procedure yields the rule table shown in Table 2.Table 2
Rule table for the template representative of CAs invariant toπ1.
(2, 2, 2) π ( π 1 ( x 0 )  (2, 2, 1) π ( π 1 ( x 2 )  (2, 2, 0) π ( π 1 ( x 1 )  (2, 1, 2) π ( π 1 ( x 6 )  (2, 1, 1) π ( π 1 ( x 8 )  (2, 1, 0) π ( π 1 ( x 7 )  (2, 0, 2) π ( π 1 ( x 3 )  (2, 0, 1) π ( π 1 ( x 5 )  (2, 0, 0) π ( π 1 ( x 4 )  (1, 2, 2) π 1 ( x 4 )  (1, 2, 1) π 1 ( x 3 )  (1, 2, 0) π 1 ( x 5 )  (1, 1, 2) π 1 ( x 1 )  (1, 1, 1) π 1 ( x 0 )  (1, 1, 0) π 1 ( x 2 )  (1, 0, 2) π 1 ( x 7 )  (1, 0, 1) π 1 ( x 6 )  (1, 0, 0) π 1 ( x 8 )  (0, 2, 2) x 8  (0, 2, 1) x 7  (0, 2, 0) x 6  (0, 1, 2) x 5  (0, 1, 1) x 4  (0, 1, 0) x 3  (0, 0, 2) x 2  (0, 0, 1) x 1  (0, 0, 0) x 0The core of a template for CAs invariant toρ(π1) can now be found by compressing this rule table into its k-ary form:(21)Tρπ1=ππ1x0,ππ1x2,ππ1x1,ππ1x6,ππ1x8,ππ1x7,ππ1x3,ππ1x5,ππ1x4,π1x4,π1x3,π1x5,π1x1,π1x0,π1x2,π1x7,π1x6,π1x8,x8,x7,x6,x5,x4,x3,x2,x1,x0Remember from Definition 5 that any permutation π can be represented by an algebraic function, which is the actual representation used by the algorithm. We use the π notation here since it is compact and serves the explanation’s purpose.The same procedure can now be repeated for every permutation of theSk set, essentially mapping each permutation of the set to a corresponding template of CAs invariant to that permutation. It is now only a matter of intersecting all of the templates found, and the result is a template that represents all colorblind rules of the space defined by k and r.When applied tok=2 and r=1, we obtain(22)Tcolourblind=1-x0,1-x1,1-x2,1-x3,x3,x2,x1,x0,whereas, for k=3 and r=1, the result becomes(23)Tcolourblind31=2,2-x1,2-2x1,2-x3,2-x4,2-x5,2-2,x3,2-2x5,2-2x4,1-2x4,1-2x3,1-2x5,1-2x1,1,1+2x1,1+2x5,1+2x3,1+2x4,2x4,2x5,2x3,x5,x4,x3,2x1,x1,0.


## 6. A Detailed Example

Here we discuss a detailed application for the template framework presented in this paper, which is to find the rules that share a set of static properties. This can be achieved with the template builder functions provided withCATemplates, or one could implement custom builder functions on top of the core concepts provided by the package. What follows is a sample of how the framework can be used to conduct an experiment of this sort.More specifically, let us suppose we are interested in the rules which are both totalistic and captive. This might come from a purely theoretical interest, or motivated by the need for obtaining rules of this type for some practical application.We then start by building the templates for totalistic and captive rules of the elementary space, as shown in the previous sections (Ttotalistic and Tcaptive). By performing their intersection, we end up with a template representing all totalistic and captive rules of the elementary space, as follows:(24)Tk2r1=2,1.0,1,x3,x3,x1,x3,x1,x1,0,FilterVariableAssignments.Upon expansion, this template yields the 4 totalistic elementary CAs which are also captive:128,150,232,254. Notice that the template being expanded has only 2 variables, which means the expansion has to consider only 4 expansion candidates, which is a substantially smaller subset of the original space, which has 256 rules.Since the elementary space is a small one, let us perform the same example in larger spaces. We can generate the equivalent templates for the space defined byk=3 and r=1 and perform the intersection between them. The result is(25)Tk3r1=3,1.0,2,x17∈1,2,2,x17∈1,2,2,1,2,1,0,x17∈1,2,2,1,2,1,0,1,0,x1∈0,1,2,1,0,1,0,x1∈0,1,0,x1∈0,1,0FilterVariableAssignments.Notice that this template also has two variables:x1 and x17. This means there are only 32=9 possible expansions for this template, from which some will be filtered out because of the variable assignment annotations. After expansion, this template yields the 4 totalistic rules of the space which are also captive: {223160992,223161514,265235104,265235626}.This means that we took a space with327=7,625,597,484,987 rules and found out that only 4 of those share the totality and captivity properties, all without actually enumerating the whole space (which would be not feasible, given its size). Notice that this space could be further reduced, by intersecting this resulting template with templates from other properties, like color blindness.Extending the previous case, we may now ask the general question of up to which rule space size could we still manage to get access to totalistic and captive rules. Without templates, the rules would have to be obtained directly by scanning the rule space and selecting those having the two properties. But withk=3 this approach would already be impractical even for r=1 on a standard personal computer, since the space has ≃7.6×1012 rules. A first alternative, now using templates, could be accessing the rules, say, by first expanding the totalistic rules directly from the corresponding template and then filtering out the captive ones. This certainly helps. In fact, by doing so, progressively, starting with radius r=0.5 and increasing its value in steps of 0.5, in a standard personal computer it would hardly be possible to reach beyond r=2 (which corresponds to a space with ≃8.7×10115 rules), because of the substantial increase in computational time as we would go from a given r to its subsequent value. We omit actual values of processing time here, as this may strongly vary among different machine architectures and their software environment.However, by relying on the generation of the individual templates of each property and expanding the intersection between them, we easily access spaces up tor=4 (possibly even beyond), which contains ≃1.5×109391 rules. It turns out that, in this space, only 256 rules share the two properties, an extremely smaller space to reason about.Furthermore, the analysis of all the data generated from the previous experiment suggests that the number of rules withk=3 and the shared properties of totality and captivity seems to be given by 4r for symmetric rules (those with integer radius), whereas no rule would be present for asymmetric rules. This is quite a remarkable general result, derived from direct probing of the corresponding rule spaces that the full usage of templates allowed us.As a final note, it is worth emphasising that template expansion is only made when the actual rules represented in a template are needed, which is at the end of the process of answering which rules satisfy a given set of properties. Until then, it suffices to operate directly with the templates; this is where the conciseness of template usage lies. And although expansion may be computationally intensive, it is certainly much less than if the entire corresponding spaces would have to be manipulated directly all the way.


## 7. Concluding Remarks

Searching for cellular automata with specific behaviours (such as global problem solvers) is a daunting task for anyone looking further than the elementary space.In this paper, we presented the current state of cellular automata templates, a valuable ally in this front. We have described what templates are and how the two currently implemented operations (expansion and intersection) work, went into details of the implementations of template builder functions for captive, totalistic, outer-totalistic, and colorblind rules, and have shown a sample application of the framework established here.The sample application has led us to the discovery that only a handful of CAs share both of the properties of totality and captivity (only 64 rules on thek=3, r=3 space, for instance). This little experiment shows how the proposed framework can be used as a means to sieve through very large spaces when searching for CAs that present a given behaviour.As mentioned in distinct parts of the text, the notion of templates and the implementation of the computational system to support it underwent a long way since its origin, up to its current degree of structural maturity.The natural course from here is to develop new template builders and whichever other operations we might conceive. More concretely with respect to the latter, we should say that during the last couple of years we have been investigating the notion of “difference” between templates, an operation whose output would yield another template representing the rules that have the property associated with the first template, but not having the property associated with the second. In spite of a conference publication we have on the topic (see [15]), it is not yet mature to go into the publicly available package. But in due time, we intend to do so.As for new template builders, a generalisation of one to handle arbitrary values of symmetry by conjugation is more pressing. As mentioned earlier, we decided not to include this template builder mostly because the existing one cannot yet handle arbitrary number of states in the case of conjugation. However, noticing that the notion of color blindness is essentially the notion of rules with maximum symmetry by conjugation, generalised for anyk-state rule, using the same idea implemented for color blindness it is now possible to face the generalisation of arbitrary values of symmetry by conjugation. This is clearly future work to be done.Also, it is tempting to add completely new template builders to the present package, referring to other parameters, like those in [16]. In fact, we hope that this paper triggers collaborative participation from the cellular automata community in terms of both the system’s expansion and its use in applications. This is why we decided to keep the work in GitHub, publicly available.As for the possibility of extending the framework to support rules in higher dimensions, we would say this would be readily possible for all current properties but one: number conservation. This is due to the fact that the underlying algorithm we used to implement the corresponding template builder comes from [17], which is restricted to one-dimensional rules. In order to change that, a general algorithm would have to be used, quite likely the one described in [18]. This is certainly feasible and desirable, but we had not yet had the opportunity to go about that.



---

*Source: 6573793-2019-04-03.xml*