# Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata

Authors: Martin Biehl; Olaf Witkowski
Journal: Complexity
 (2021)

---

## Abstract

Over the years, the field of artificial life has attempted to capture significant properties of life in artificial systems. By measuring quantities within such complex systems, the hope is to capture the reasons for the explosion of complexity in living systems. A major effort has been in discrete dynamical systems such as cellular automata, where very few rules lead to high levels of complexity. In this paper, for every elementary cellular automaton, we count the number of ways a finite region can transform an enclosed finite region. We discuss the relation of this count to existing notions of controllability, physical universality, and constructor theory. Numerically, we find that particular sizes of surrounding regions have preferred sizes of enclosed regions on which they can induce more transformations. We also find three particularly powerful rules (90, 105, 150) from this perspective.


---

## Body

## 1. Introduction

### 1.1. Artificial Life

Artificial life studies “life as it could be” [1]. One approach to this is to start at the level of physics and look at artificial systems—usually dynamical systems—as artificial universes and study properties of life within them. This approach still faces fundamental problems including the lack of a formal definition of life for such systems. However, numerous metrics have been proposed in order to identify artificial universes that for one reason or another may be more suitable for life than others. Examples include measures of complexity and computational capabilities.First restricting ourselves to discrete dynamical systems such as cellular automata, along the line of von Neumann’s work on self-reproducing automata [2], builds a ladder for tackling the intricacy of living systems (see, for example, Beer [3] and Adams et al. [4]). As pointed out by Janzing [5], it also makes the problem more accessible to the computer science community and honors the lesson learned from quantum information theory that translating physics into computer scientific language can provide a new perspective and new paradigms.Since life—and in particular evolution—is often seen as a creative force, one relevant property might be the number of ways that things can be turned into other things within a given system. More specifically, we are interested in the number of different ways in which configurations of one region of space can alter the future consequences of another region of space. We anticipate that systems where this number is high may guarantee a combinatorial explosion of context-dependent possibilities, increasing the probability of life.In this preliminary investigation, we look at a quantification of this notion for the set of elementary cellular automata (ECA). Next, we explain our quantification in more detail and justify design choices. We then discuss the relation of our quantification to existing ideas in the literature.


### 1.2. Approach: Number of Functions

We use the following notation for cellular automata. The setX is the alphabet and Xℤ is the set of configurations, i.e., bi-infinite binary sequences. If we look at a region R⊂ℤ, we write xR∈XR for its configuration.One of the main properties of our quantification is that it looks at the local dynamics within a cellular automaton. We consider a finite regionE called the environment, which can be of any shape in general, and another region V called the volume. We then want to see in how many ways the environment can influence the future of the volume. In other words, how many transforming functions on the cells in the volume V the cells in the environment E induce. The future of the volume is its future light cone in the space-time diagram of the cellular automaton. This future light cone is also influenced by cells outside the environment and volume itself. Without fixing these external cells, what will happen in the future light cone is undetermined.Even if we were to fix the external configuration, computing the influence on the entire future light cone is intractable. We therefore pick a ball (in the appropriate way for the dimensionality of theCA) C=E∪V and only compute the configurations of all cells in the inverse light cone ILC which is the subset of the space-time diagram future cells that are completely determined by the configuration of C (see Figure 1 for an illustration of the inverse light cone for a 1D cellular automaton).Figure 1
Diagram displaying an example of the inverted light coneILC of the input set of cells C. The input includes volume V (in red) and environment E (in light green). The output O (in orange) contains the cells within the future light cone of C that are in the Moore neighborhood of a cell outside of ILC. The combination of yellow and orange cells denotes the future light cone of volume V within ILC. The red line shows the border between the environment's inverted light cone and the future lightcone of the volume. The vertical dashed lines show the future of the volume, and the horizontal dashed line shows the limit of computation considered at some time t, in Janzing’s approach [5].We also arbitrarily choose the environment region to be the surrounding sphere around the volume regionV. Clearly, this environment and volume combination is not the only interesting one. One other possibility would be to choose the environment adjacent to but not enclosing the volume. If we see the environment as a machine that transforms the volume, then this would simplify the use of such a machine.Each environmentE then induces a function from the set of initial volume configurations to the configurations of the future light cone of the volume V that is within the inverse light cone of C. It would be possible to then count the number of different functions of this kind. However, we do not want to count two such functions as different if their difference cannot escape the inverse light cone. Intuitively, such differences only have an ephemeral effect that does not make a lasting difference. This means we only count functions as different if their effect could (at least in principle) last forever. We therefore count only the different functions from volume configurations to those cells whose effect can escape the inverse light cone. We call those cells the output cells O.To summarize, we can say that we count the number of not provably ephemeral (i.e., possibly eternal) transformations that different environments can achieve on the volume.There are two relevant limits of the number of functions we propose to compute. The first is the maximum number of functions that an environmentE of width E cells can induce. Since there are only XE configurations of such an environment, there can never be more than XE such functions (here we have X=2). As we will see there are ECAs where the number of functions that environments of various sizes can induce exhausts this limit.The second is the number of functions from the volume to the output cells. This number isXOXV. An environment that could compute all of those functions could be called transformationally complete for the volume V. However, since the output cells we consider here grow with the environment sizes, this is impossible for V>1 or E>1. A different choice of output cells, e.g., choosing the same cells as the (initial) volume cells at a later timestep like in the theory of physical universality [5], however, could be interesting as well. In that case, there may be transformationally complete finite environments.


## 1.1. Artificial Life

Artificial life studies “life as it could be” [1]. One approach to this is to start at the level of physics and look at artificial systems—usually dynamical systems—as artificial universes and study properties of life within them. This approach still faces fundamental problems including the lack of a formal definition of life for such systems. However, numerous metrics have been proposed in order to identify artificial universes that for one reason or another may be more suitable for life than others. Examples include measures of complexity and computational capabilities.First restricting ourselves to discrete dynamical systems such as cellular automata, along the line of von Neumann’s work on self-reproducing automata [2], builds a ladder for tackling the intricacy of living systems (see, for example, Beer [3] and Adams et al. [4]). As pointed out by Janzing [5], it also makes the problem more accessible to the computer science community and honors the lesson learned from quantum information theory that translating physics into computer scientific language can provide a new perspective and new paradigms.Since life—and in particular evolution—is often seen as a creative force, one relevant property might be the number of ways that things can be turned into other things within a given system. More specifically, we are interested in the number of different ways in which configurations of one region of space can alter the future consequences of another region of space. We anticipate that systems where this number is high may guarantee a combinatorial explosion of context-dependent possibilities, increasing the probability of life.In this preliminary investigation, we look at a quantification of this notion for the set of elementary cellular automata (ECA). Next, we explain our quantification in more detail and justify design choices. We then discuss the relation of our quantification to existing ideas in the literature.


## 1.2. Approach: Number of Functions

We use the following notation for cellular automata. The setX is the alphabet and Xℤ is the set of configurations, i.e., bi-infinite binary sequences. If we look at a region R⊂ℤ, we write xR∈XR for its configuration.One of the main properties of our quantification is that it looks at the local dynamics within a cellular automaton. We consider a finite regionE called the environment, which can be of any shape in general, and another region V called the volume. We then want to see in how many ways the environment can influence the future of the volume. In other words, how many transforming functions on the cells in the volume V the cells in the environment E induce. The future of the volume is its future light cone in the space-time diagram of the cellular automaton. This future light cone is also influenced by cells outside the environment and volume itself. Without fixing these external cells, what will happen in the future light cone is undetermined.Even if we were to fix the external configuration, computing the influence on the entire future light cone is intractable. We therefore pick a ball (in the appropriate way for the dimensionality of theCA) C=E∪V and only compute the configurations of all cells in the inverse light cone ILC which is the subset of the space-time diagram future cells that are completely determined by the configuration of C (see Figure 1 for an illustration of the inverse light cone for a 1D cellular automaton).Figure 1
Diagram displaying an example of the inverted light coneILC of the input set of cells C. The input includes volume V (in red) and environment E (in light green). The output O (in orange) contains the cells within the future light cone of C that are in the Moore neighborhood of a cell outside of ILC. The combination of yellow and orange cells denotes the future light cone of volume V within ILC. The red line shows the border between the environment's inverted light cone and the future lightcone of the volume. The vertical dashed lines show the future of the volume, and the horizontal dashed line shows the limit of computation considered at some time t, in Janzing’s approach [5].We also arbitrarily choose the environment region to be the surrounding sphere around the volume regionV. Clearly, this environment and volume combination is not the only interesting one. One other possibility would be to choose the environment adjacent to but not enclosing the volume. If we see the environment as a machine that transforms the volume, then this would simplify the use of such a machine.Each environmentE then induces a function from the set of initial volume configurations to the configurations of the future light cone of the volume V that is within the inverse light cone of C. It would be possible to then count the number of different functions of this kind. However, we do not want to count two such functions as different if their difference cannot escape the inverse light cone. Intuitively, such differences only have an ephemeral effect that does not make a lasting difference. This means we only count functions as different if their effect could (at least in principle) last forever. We therefore count only the different functions from volume configurations to those cells whose effect can escape the inverse light cone. We call those cells the output cells O.To summarize, we can say that we count the number of not provably ephemeral (i.e., possibly eternal) transformations that different environments can achieve on the volume.There are two relevant limits of the number of functions we propose to compute. The first is the maximum number of functions that an environmentE of width E cells can induce. Since there are only XE configurations of such an environment, there can never be more than XE such functions (here we have X=2). As we will see there are ECAs where the number of functions that environments of various sizes can induce exhausts this limit.The second is the number of functions from the volume to the output cells. This number isXOXV. An environment that could compute all of those functions could be called transformationally complete for the volume V. However, since the output cells we consider here grow with the environment sizes, this is impossible for V>1 or E>1. A different choice of output cells, e.g., choosing the same cells as the (initial) volume cells at a later timestep like in the theory of physical universality [5], however, could be interesting as well. In that case, there may be transformationally complete finite environments.


## 2. Background

### 2.1. Constructor Theory

Constructor theory [6] conceives of physical laws as statements that rule out the possibility of particular kinds of transformations. Our investigation here then investigates physical laws that hold not for constructors in general but for the transformations that particular kinds of finite constructors can achieve in finite time on finite substrates. The (finite) environments we are investigating are the constructors and the (also finite) volumes are the substrate. We compute all possible transformations that an environment can induce on a volume. Any transformations that we do not find are therefore impossible. This means each such impossible transformation corresponds to a resource constrained physical law in the sense of constructor theory.


### 2.2. Controllability

Note that we are not computing the amount of (open or closed loop) control the environment has over the future light cone of the volume.Open-loop controllability would mean to compute how many different configurationsxO of the output cells O the different environment configurations xE can achieve or induce. Formally, this can be expressed as the following set cardinality:(1)xO∈XO:∃xE∈XEs.t.∀xV∈XV,fCAxE,xVO=xO.HerefCAxE,xV is the function (induced by the particular cellular automaton rule) mapping a pair of environment configuration xE and volume configuration xV to their inverse light cone. fCAxE,xVO then denotes the restriction of the inverse light cone to the output cells. At most there are 2O such output cell configurations. Unlike for our measure, for open-loop control, it is not important how many different functions can be induced by the environment configurations since multiple functions can be used to achieve the same output configuration. For example, take three environment configurations, where the function induced by the first maps all volume states to output state xO, the function of the second maps all output states to yO, and the function of the third maps some of the states to xO and some of the states to yO. So, the third environment configuration does not add any new achievable output configurations to those achievable by the other two environments and should not contribute positively to a measure of control. However, in our measure, since the third function is different from the other two, it does so. We count the amount of possible transformations, i.e., the transformability, of regions by other regions.In closed-loop control, the environment is “allowed to know” the volume statexV. In this case, what counts is how many different input-output pairs can be induced if the environment can be chosen for a given volume (this is not the same as the number of input-output relations that a set of environments induces since we can use a different environment for each given input to induce functions that are not induced by a single environment). Formally, this can be expressed as the following set cardinality:(2)xV,xO∈XV×XO:∃xE∈XEs.t.fCAxE,xVO=xO.Then, any set of environment functions which contains for every input-output pair one environment pair that maps the input to the output is sufficient. So, we would need at most as many functions as there are input output pairs, i.e., in our case,2O∗2V functions. To see this, note that for each pair, we never need more than one function to map input to output. We also always need at least one, but one function can possibly be reused for other transitions. The example we used for the open-loop case also applies for the closed-loop one. The third function can be induced by selecting either the first or second appropriately for each input so that it does not contribute positively to the closed-loop controllability either.


### 2.3. Physical Universality

Physical universality is defined by Janzing [5].Definition (universal induction of bijections): ACA is said to allow for universal induction of bijections if for every finite region V⊂C and every bijective map π:XR⟶XR there is a configuration xC\R∈XC\R of the complement of R and a time t such that fCAtxRR=πxR∀xR∈XR.As noted by Janzing [7], dropping bijectivity from this definition does not lead to a stronger notion of (general) universality since for every non-bijective function on a region R, there is a bijective function on a larger region R∪R¯ which induces the non-bijective function on R. However, if we are interested in a resource-constrained notion of physical universality (e.g., for a given rule do environments of finite size n exhaust their control capacities on finite volumes of size m within finite time intervals Δt), then a rule that allows the induction of all bijective functions on the finite volume will not necessarily allow the induction of all functions on this finite volume.We therefore should consider the set of all functions for a resource-constrained version of physical universality. For a degree of universality of control of a finite environment on a finite volume within a finite time, we could then compute the fraction of all functions on the finite volume that is induced within a finite time interval.Note that the number of functions on a finite volumeV of V cells is 2V2V. If an environment E can induce all of these functions within time Δt on V, we could say that this environment is physically universal forVwithinΔt.The number of functions on a finite volume grows faster withV than the capacity of the environment to induce different functions within time interval Δt grows with E. The latter is Δt2E. To see this, note that for a fixed number E of cells of an environment, there are 2E environment states. For a fixed time t and set Ot of output cells, there is then only one function that each environment state can induce. This means that for Δt output times, we get at most Δt2E functions that environments of this size can ever induce within Δt. If we find a set of cells that in fact induce this many functions on some volume V, then we say that E exhausts its control capacity on V.


### 2.4. Perception

We can also take the perspective of the volume rather than that of the environment. Consider the output cells as the future state of the volume. We can then see the number of functions as the number of equivalence classes on the set of environment configurationsXE created by the equivalence relation:(3)xE∼yE⇔∀xV∈XV:fCAILxE,xVO=fCAILyE,xVO.This considers environment configurations as equivalent if they have the same influence on the transitions from volume configuration to output cell configuration. The number of such equivalence classes is identical to the number of functions we count here. This construction of equivalence classes has been used to capture perception of a stochastic process agent model in [8]. Note however that it is not clear in how far the output cells can be seen as the future state of an agent whose current state is the volume state. So, while the construction is in some sense the same, the purpose and interpretations are different. Note that the same construction of equivalence classes can also be found in [9] where it is used to coarse-grain the influence form one random variable on the transition between two others.


## 2.1. Constructor Theory

Constructor theory [6] conceives of physical laws as statements that rule out the possibility of particular kinds of transformations. Our investigation here then investigates physical laws that hold not for constructors in general but for the transformations that particular kinds of finite constructors can achieve in finite time on finite substrates. The (finite) environments we are investigating are the constructors and the (also finite) volumes are the substrate. We compute all possible transformations that an environment can induce on a volume. Any transformations that we do not find are therefore impossible. This means each such impossible transformation corresponds to a resource constrained physical law in the sense of constructor theory.


## 2.2. Controllability

Note that we are not computing the amount of (open or closed loop) control the environment has over the future light cone of the volume.Open-loop controllability would mean to compute how many different configurationsxO of the output cells O the different environment configurations xE can achieve or induce. Formally, this can be expressed as the following set cardinality:(1)xO∈XO:∃xE∈XEs.t.∀xV∈XV,fCAxE,xVO=xO.HerefCAxE,xV is the function (induced by the particular cellular automaton rule) mapping a pair of environment configuration xE and volume configuration xV to their inverse light cone. fCAxE,xVO then denotes the restriction of the inverse light cone to the output cells. At most there are 2O such output cell configurations. Unlike for our measure, for open-loop control, it is not important how many different functions can be induced by the environment configurations since multiple functions can be used to achieve the same output configuration. For example, take three environment configurations, where the function induced by the first maps all volume states to output state xO, the function of the second maps all output states to yO, and the function of the third maps some of the states to xO and some of the states to yO. So, the third environment configuration does not add any new achievable output configurations to those achievable by the other two environments and should not contribute positively to a measure of control. However, in our measure, since the third function is different from the other two, it does so. We count the amount of possible transformations, i.e., the transformability, of regions by other regions.In closed-loop control, the environment is “allowed to know” the volume statexV. In this case, what counts is how many different input-output pairs can be induced if the environment can be chosen for a given volume (this is not the same as the number of input-output relations that a set of environments induces since we can use a different environment for each given input to induce functions that are not induced by a single environment). Formally, this can be expressed as the following set cardinality:(2)xV,xO∈XV×XO:∃xE∈XEs.t.fCAxE,xVO=xO.Then, any set of environment functions which contains for every input-output pair one environment pair that maps the input to the output is sufficient. So, we would need at most as many functions as there are input output pairs, i.e., in our case,2O∗2V functions. To see this, note that for each pair, we never need more than one function to map input to output. We also always need at least one, but one function can possibly be reused for other transitions. The example we used for the open-loop case also applies for the closed-loop one. The third function can be induced by selecting either the first or second appropriately for each input so that it does not contribute positively to the closed-loop controllability either.


## 2.3. Physical Universality

Physical universality is defined by Janzing [5].Definition (universal induction of bijections): ACA is said to allow for universal induction of bijections if for every finite region V⊂C and every bijective map π:XR⟶XR there is a configuration xC\R∈XC\R of the complement of R and a time t such that fCAtxRR=πxR∀xR∈XR.As noted by Janzing [7], dropping bijectivity from this definition does not lead to a stronger notion of (general) universality since for every non-bijective function on a region R, there is a bijective function on a larger region R∪R¯ which induces the non-bijective function on R. However, if we are interested in a resource-constrained notion of physical universality (e.g., for a given rule do environments of finite size n exhaust their control capacities on finite volumes of size m within finite time intervals Δt), then a rule that allows the induction of all bijective functions on the finite volume will not necessarily allow the induction of all functions on this finite volume.We therefore should consider the set of all functions for a resource-constrained version of physical universality. For a degree of universality of control of a finite environment on a finite volume within a finite time, we could then compute the fraction of all functions on the finite volume that is induced within a finite time interval.Note that the number of functions on a finite volumeV of V cells is 2V2V. If an environment E can induce all of these functions within time Δt on V, we could say that this environment is physically universal forVwithinΔt.The number of functions on a finite volume grows faster withV than the capacity of the environment to induce different functions within time interval Δt grows with E. The latter is Δt2E. To see this, note that for a fixed number E of cells of an environment, there are 2E environment states. For a fixed time t and set Ot of output cells, there is then only one function that each environment state can induce. This means that for Δt output times, we get at most Δt2E functions that environments of this size can ever induce within Δt. If we find a set of cells that in fact induce this many functions on some volume V, then we say that E exhausts its control capacity on V.


## 2.4. Perception

We can also take the perspective of the volume rather than that of the environment. Consider the output cells as the future state of the volume. We can then see the number of functions as the number of equivalence classes on the set of environment configurationsXE created by the equivalence relation:(3)xE∼yE⇔∀xV∈XV:fCAILxE,xVO=fCAILyE,xVO.This considers environment configurations as equivalent if they have the same influence on the transitions from volume configuration to output cell configuration. The number of such equivalence classes is identical to the number of functions we count here. This construction of equivalence classes has been used to capture perception of a stochastic process agent model in [8]. Note however that it is not clear in how far the output cells can be seen as the future state of an agent whose current state is the volume state. So, while the construction is in some sense the same, the purpose and interpretations are different. Note that the same construction of equivalence classes can also be found in [9] where it is used to coarse-grain the influence form one random variable on the transition between two others.


## 3. Methods

### 3.1. Cellular Automata

We use the reduction of the 256 ECA rules to the 88 non-equivalent ones as defined in ([10]; Table 1) and apply them to a finite and contiguous set of cells. We only consider the part of the future that is determined by the initial cells, i.e., the inverse light cone as shown in Figure 1.Table 1
Classification of the rules into four classes, corresponding to the analysis of our results.
TypeNumberRulesClass A (monotonic and quasi-constant)310, 1, 2, 3, 4, 5, 8, 10, 12, 15, 19, 29, 30, 32, 34, 37, 41, 42, 50, 51, 54, 62, 76, 106, 108, 110, 132, 138, 170, 200, 204Class B (monotonic and not quasi-constant)437, 9, 11, 13, 14, 18, 22, 23, 24, 25, 28, 33, 35, 36, 38, 43, 44, 45, 46, 58, 60, 72, 73, 77, 78, 94, 104, 122, 126, 134, 136, 140, 142, 146, 152, 154, 156, 164, 168, 172, 178, 184, 232Class C (exhibit local maxima and not exceptional)146, 26, 27, 40, 56, 57, 74, 128, 130, 160, 162Class D (exceptional)390, 105, 150We writeC=1,…,2n+m for the index set of the initial cells where n∈ℕ is called the environment thickness and m∈ℕ is the volume size. For computational reasons, we only look at 0<n,m≤7. The set XC with X=0,1 is the set of initial configurations and an initial configuration xC∈XC is a binary vector of length C. The set E∈C is the subset of cells belonging to the environment and we write xE∈XE for (initial) environment configurations. The set V=C\E is the set of (initial) volume cells and xV∈XV is a volume. For any set C of initial cells, we write ILC⊂ℕ×ℕ for the set of indices of the cells in the inverse light cone of C. An index t,j∈ILC then refers to the cell j∈C after t applications of the ECA dynamics. The output cells O⊂ILC are defined as the cells within the future light cone of the volume cells C that are in the Moore neighborhood of a cell that is not in ILC. We then write xO∈XO for an output configuration (see Figure 1). Starting from an initial configuration xC=xE,xV, we write fCAxE,xV for the configuration of the cells within the ILC that result from the application of the ECA rule to xC. Note that we write xE,xV for an initial configuration even though the environment cells enclose the volume cells so that xEl,xV,xEr with El,Er the cells on the left and right respectively would be more accurate. We also write fCAILxC=fCAILxE,xV for the spatiotemporal configuration of the entire inverse light cone (including time t=0) resulting from applying fCA iteratively to xC=xE,xV. This lets us write fCAILxE,xVO for the configuration of the output cells when the initial configuration is xE,xV.Our algorithm then counts for eachn,m the number of different functions from the set XV of initial volume configurations to the set of output cell configurations XO, i.e., it computes the number of functions(4)g:XV⟶XO:∃xE∈XEs.t.fCAILxE,xVO=gxV.See Algorithm1 for how this can be computed.Algorithm 1:Calculation of the number of functions from volume configurations to output cells.
Data:CA dimension d, CA alphabet X=0,1, finite region indices C⊂ℕd, volume cell indices V⊂C, environment cell indices E⊂C such that E∩V=∅,E∪V=C, spatiotemporal inverse light cone indices ILC⊆ℕ×C, spatiotemporal output cell indices O⊂ILC, and CA induced inverse light cone function fCAIL:XC⟶XO.Result: number r of functions g inducedinitializeG← empty set of maps g:XV⟶XOforeachinitial environment statexE0∈XEdoinitializegxE0:XV⟶XOforeachinitial volume statexV0∈XV0dogxE0xV0←fCAxE0,xV0endG←G∪gxE0; //only add gxE0 to G if it is different from all previous onesendreturnG


## 3.1. Cellular Automata

We use the reduction of the 256 ECA rules to the 88 non-equivalent ones as defined in ([10]; Table 1) and apply them to a finite and contiguous set of cells. We only consider the part of the future that is determined by the initial cells, i.e., the inverse light cone as shown in Figure 1.Table 1
Classification of the rules into four classes, corresponding to the analysis of our results.
TypeNumberRulesClass A (monotonic and quasi-constant)310, 1, 2, 3, 4, 5, 8, 10, 12, 15, 19, 29, 30, 32, 34, 37, 41, 42, 50, 51, 54, 62, 76, 106, 108, 110, 132, 138, 170, 200, 204Class B (monotonic and not quasi-constant)437, 9, 11, 13, 14, 18, 22, 23, 24, 25, 28, 33, 35, 36, 38, 43, 44, 45, 46, 58, 60, 72, 73, 77, 78, 94, 104, 122, 126, 134, 136, 140, 142, 146, 152, 154, 156, 164, 168, 172, 178, 184, 232Class C (exhibit local maxima and not exceptional)146, 26, 27, 40, 56, 57, 74, 128, 130, 160, 162Class D (exceptional)390, 105, 150We writeC=1,…,2n+m for the index set of the initial cells where n∈ℕ is called the environment thickness and m∈ℕ is the volume size. For computational reasons, we only look at 0<n,m≤7. The set XC with X=0,1 is the set of initial configurations and an initial configuration xC∈XC is a binary vector of length C. The set E∈C is the subset of cells belonging to the environment and we write xE∈XE for (initial) environment configurations. The set V=C\E is the set of (initial) volume cells and xV∈XV is a volume. For any set C of initial cells, we write ILC⊂ℕ×ℕ for the set of indices of the cells in the inverse light cone of C. An index t,j∈ILC then refers to the cell j∈C after t applications of the ECA dynamics. The output cells O⊂ILC are defined as the cells within the future light cone of the volume cells C that are in the Moore neighborhood of a cell that is not in ILC. We then write xO∈XO for an output configuration (see Figure 1). Starting from an initial configuration xC=xE,xV, we write fCAxE,xV for the configuration of the cells within the ILC that result from the application of the ECA rule to xC. Note that we write xE,xV for an initial configuration even though the environment cells enclose the volume cells so that xEl,xV,xEr with El,Er the cells on the left and right respectively would be more accurate. We also write fCAILxC=fCAILxE,xV for the spatiotemporal configuration of the entire inverse light cone (including time t=0) resulting from applying fCA iteratively to xC=xE,xV. This lets us write fCAILxE,xVO for the configuration of the output cells when the initial configuration is xE,xV.Our algorithm then counts for eachn,m the number of different functions from the set XV of initial volume configurations to the set of output cell configurations XO, i.e., it computes the number of functions(4)g:XV⟶XO:∃xE∈XEs.t.fCAILxE,xVO=gxV.See Algorithm1 for how this can be computed.Algorithm 1:Calculation of the number of functions from volume configurations to output cells.
Data:CA dimension d, CA alphabet X=0,1, finite region indices C⊂ℕd, volume cell indices V⊂C, environment cell indices E⊂C such that E∩V=∅,E∪V=C, spatiotemporal inverse light cone indices ILC⊆ℕ×C, spatiotemporal output cell indices O⊂ILC, and CA induced inverse light cone function fCAIL:XC⟶XO.Result: number r of functions g inducedinitializeG← empty set of maps g:XV⟶XOforeachinitial environment statexE0∈XEdoinitializegxE0:XV⟶XOforeachinitial volume statexV0∈XV0dogxE0xV0←fCAxE0,xV0endG←G∪gxE0; //only add gxE0 to G if it is different from all previous onesendreturnG


## 4. Results

Here, we summarize the results from the runs of the method previously described.We start by visualizing all function numbers calculated with Algorithm1. The plot in Figure 2 displays the count for those number of functions, for each volume size and environment thickness. Each color only identifies one distinct rule and does not bear any additional meaning.Figure 2
Number of functions induced by environments on enclosed volumes for environment thicknesses and volume sizes from 1 to 7. All 88 unique rules.Figure3 shows the integral of the function plotted in Figure 2, i.e., the volume under the number of functions curve. This volume corresponds, for each rule, to the total number of functions accumulated over all computed volume and environment sizes.Figure 3
Total number of functions for each of the 88 rules. The ordered list of rules in the plot is as follows: {0, 8, 32, 128, 4, 12, 136, 200, 2, 72, 51, 204, 34, 1, 3, 19, 76, 15, 170, 140, 160, 46, 29, 132, 36, 10, 13, 162, 5, 138, 35, 27, 40, 42, 44, 50, 7, 24, 38, 23, 77, 178, 232, 172, 108, 28, 130, 78, 33, 168, 11, 156, 57, 56, 14, 58, 152, 9, 60, 102, 184, 6, 62, 18, 25, 110, 54, 43, 142, 126, 73, 74, 104, 164, 154, 146, 134, 45, 122, 94, 37, 106, 41, 26, 30, 22, 90, 105, 150}.We identify four distinct classes from the aspect of the curves in Figure2, as summarized in Table 1.


### 4.1. Class A: “Quasi-Constant”

For 31 rules, the number of functions only increases with environment thickness and the controlled volume size does not influence the number of functions anymore if it contains more than 2 cells. Figure4 shows a plot of the number of functions as in Figure 2, but only with the rules that satisfy the following two conditions: firstly the number of functions for a fixed environment thickness increases from volume size 1 to volume size 2, and secondly it then remains constant for the rest of the volume sizes.Figure 4
Number of functions as in Figure2. Here we display only rules for which the number of functions for a fixed environment thickness increases from volume size 1 to volume size 2 and then remains constant for the rest of the volume sizes.


### 4.2. Class B: “Monotonic”

43 rules increase monotonically and are not constant, even for volume size other than 1 or 2. We note that they do not have local maxima either—this was true for Class A as well. We note that no rules at all are strictly monotonic for all environment thicknesses. There are some rules that are strictly monotonic for specific environment thicknesses, e.g.,13,14,28. Figure 5 plots all rules for which the number of functions induced by a fixed environment thickness increases not only from volume size 1 to 2, and never decreases when volume size increases.Figure 5
All rules for which the number of functions induced by a fixed environment thickness increases not only from volume size 1 to 2 and never decreases with increasing volume size.


### 4.3. Class C: “Local Maxima”

For 14 rules, we find local maxima of number of functions with respect to volume sizes. This means that for some fixed environment thickness, the number of functions drops after an increase, as volume size increases. In Figure6, we show the high number of maxima on a plot of the number of functions over environment thicknesses and volume sizes for rule 128.Figure 6
Number of functions over environment thicknesses and volume sizes for rule 128 (Class C). Note the many local maxima.


### 4.4. Class D: “Exceptional Rules”

For some rules among those with local maxima, we find that the maximum possible number of functions that a given environment size can induce is achieved for volume sizes larger than 2. We call these rules exceptional. In Figure7, we show the number of functions normalized by the number of environment states for the corresponding environment thickness. A value of 1 in this graph shows that each environment configuration induces a different function. In Figure 8, we show the special case of rule 90, where we can observe a pronounced maximum for environment thickness 7 and volume size 6. In Figure 9, we show the fraction of environment configurations that induce different functions on the volumes, for variable values of environment thicknesses and volume sizes from 1 to 7.Figure 7
Fraction of the number of environment configurations that induce different functions on the volumes for environment thicknesses and volume sizes form 1 to 7. Note that under some rules, each environment induces a unique function for all volume sizes from 1 to 7.Figure 8
Number of functions over environment thicknesses and volume sizes for rule 90 (Class D). This is also one of the exceptional rules. Note the pronounced maximum at environment thickness 7 and volume size 6.Figure 9
Fraction of the number of environment configurations that induce different functions as in Figure7 for rule 90 (Class D). Note the repetitive structure.


#### 4.4.1. Comparison with Other Classifications

We compared the classification described above with all classifications presented in Martinez [10], numbering the classification as in the paper. The results are shown in Figure 10. For each classification, we compare each of our classes with each of its classes, by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules. Also note that classification 11b is not formally a classification.Figure 10
Comparison to known classifications of ECA rules. For each classification, we compare each of our four classes (rows A–D downward) with each of the classes in Martinez [10], by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)This includes the four classes identified by Wolfram [11], as summarized in Table 2. Within Wolfram Class 4 (WC 4) rules, none has any local maximum. All four rules in Class 4 belong to our Class A: monotonic and mostly constant function numbers. We note that all of the exceptional rules (Class D) are in Class 3. Interestingly, although the three rules in Class D (90, 105, 150) all have local maxima, no other Class 3 rule does.Table 2
Comparison of classes described above (Classes A to D, in rows) with the Wolfram classes (WC 1 to 4, in columns).
WC 1WC 2WC 3WC 4Class A0, 8, 321, 2, 3, 4, 5, 10, 12, 15, 19, 29, 34, 37, 42, 50, 51, 62, 76, 108, 132, 138, 170, 200, 2043041, 54, 106, 110Class B136, 1687, 9, 11, 13, 14, 23, 24, 25, 28, 33, 35, 36, 38, 43, 44, 46, 58, 72, 73, 77, 78, 94, 104, 134, 140, 142, 152, 154, 156, 164, 172, 178, 184, 23218, 22, 45, 60, 122, 126, 146—Class C40, 128, 1606, 26, 27, 56, 57, 74, 130, 162——Class D——90, 105, 150—


## 4.1. Class A: “Quasi-Constant”

For 31 rules, the number of functions only increases with environment thickness and the controlled volume size does not influence the number of functions anymore if it contains more than 2 cells. Figure4 shows a plot of the number of functions as in Figure 2, but only with the rules that satisfy the following two conditions: firstly the number of functions for a fixed environment thickness increases from volume size 1 to volume size 2, and secondly it then remains constant for the rest of the volume sizes.Figure 4
Number of functions as in Figure2. Here we display only rules for which the number of functions for a fixed environment thickness increases from volume size 1 to volume size 2 and then remains constant for the rest of the volume sizes.


## 4.2. Class B: “Monotonic”

43 rules increase monotonically and are not constant, even for volume size other than 1 or 2. We note that they do not have local maxima either—this was true for Class A as well. We note that no rules at all are strictly monotonic for all environment thicknesses. There are some rules that are strictly monotonic for specific environment thicknesses, e.g.,13,14,28. Figure 5 plots all rules for which the number of functions induced by a fixed environment thickness increases not only from volume size 1 to 2, and never decreases when volume size increases.Figure 5
All rules for which the number of functions induced by a fixed environment thickness increases not only from volume size 1 to 2 and never decreases with increasing volume size.


## 4.3. Class C: “Local Maxima”

For 14 rules, we find local maxima of number of functions with respect to volume sizes. This means that for some fixed environment thickness, the number of functions drops after an increase, as volume size increases. In Figure6, we show the high number of maxima on a plot of the number of functions over environment thicknesses and volume sizes for rule 128.Figure 6
Number of functions over environment thicknesses and volume sizes for rule 128 (Class C). Note the many local maxima.


## 4.4. Class D: “Exceptional Rules”

For some rules among those with local maxima, we find that the maximum possible number of functions that a given environment size can induce is achieved for volume sizes larger than 2. We call these rules exceptional. In Figure7, we show the number of functions normalized by the number of environment states for the corresponding environment thickness. A value of 1 in this graph shows that each environment configuration induces a different function. In Figure 8, we show the special case of rule 90, where we can observe a pronounced maximum for environment thickness 7 and volume size 6. In Figure 9, we show the fraction of environment configurations that induce different functions on the volumes, for variable values of environment thicknesses and volume sizes from 1 to 7.Figure 7
Fraction of the number of environment configurations that induce different functions on the volumes for environment thicknesses and volume sizes form 1 to 7. Note that under some rules, each environment induces a unique function for all volume sizes from 1 to 7.Figure 8
Number of functions over environment thicknesses and volume sizes for rule 90 (Class D). This is also one of the exceptional rules. Note the pronounced maximum at environment thickness 7 and volume size 6.Figure 9
Fraction of the number of environment configurations that induce different functions as in Figure7 for rule 90 (Class D). Note the repetitive structure.


### 4.4.1. Comparison with Other Classifications

We compared the classification described above with all classifications presented in Martinez [10], numbering the classification as in the paper. The results are shown in Figure 10. For each classification, we compare each of our classes with each of its classes, by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules. Also note that classification 11b is not formally a classification.Figure 10
Comparison to known classifications of ECA rules. For each classification, we compare each of our four classes (rows A–D downward) with each of the classes in Martinez [10], by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)This includes the four classes identified by Wolfram [11], as summarized in Table 2. Within Wolfram Class 4 (WC 4) rules, none has any local maximum. All four rules in Class 4 belong to our Class A: monotonic and mostly constant function numbers. We note that all of the exceptional rules (Class D) are in Class 3. Interestingly, although the three rules in Class D (90, 105, 150) all have local maxima, no other Class 3 rule does.Table 2
Comparison of classes described above (Classes A to D, in rows) with the Wolfram classes (WC 1 to 4, in columns).
WC 1WC 2WC 3WC 4Class A0, 8, 321, 2, 3, 4, 5, 10, 12, 15, 19, 29, 34, 37, 42, 50, 51, 62, 76, 108, 132, 138, 170, 200, 2043041, 54, 106, 110Class B136, 1687, 9, 11, 13, 14, 23, 24, 25, 28, 33, 35, 36, 38, 43, 44, 46, 58, 72, 73, 77, 78, 94, 104, 134, 140, 142, 152, 154, 156, 164, 172, 178, 184, 23218, 22, 45, 60, 122, 126, 146—Class C40, 128, 1606, 26, 27, 56, 57, 74, 130, 162——Class D——90, 105, 150—


## 4.4.1. Comparison with Other Classifications

We compared the classification described above with all classifications presented in Martinez [10], numbering the classification as in the paper. The results are shown in Figure 10. For each classification, we compare each of our classes with each of its classes, by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules. Also note that classification 11b is not formally a classification.Figure 10
Comparison to known classifications of ECA rules. For each classification, we compare each of our four classes (rows A–D downward) with each of the classes in Martinez [10], by taking the ratio of the number of rules in intersection of the classes to the number of rules in the union of the classes. This gives a number between 0 and 1 which is represented by gray scale here where black is equal to one. A ratio of one indicates that two classes contain exactly the same rules and thus the other classification identifies exactly the same set of rules as a single class. A value of zero means that no rule is in both classes. Note that rules 11, 12, and 16 contain classes that coincide with our class of exceptional rules.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)This includes the four classes identified by Wolfram [11], as summarized in Table 2. Within Wolfram Class 4 (WC 4) rules, none has any local maximum. All four rules in Class 4 belong to our Class A: monotonic and mostly constant function numbers. We note that all of the exceptional rules (Class D) are in Class 3. Interestingly, although the three rules in Class D (90, 105, 150) all have local maxima, no other Class 3 rule does.Table 2
Comparison of classes described above (Classes A to D, in rows) with the Wolfram classes (WC 1 to 4, in columns).
WC 1WC 2WC 3WC 4Class A0, 8, 321, 2, 3, 4, 5, 10, 12, 15, 19, 29, 34, 37, 42, 50, 51, 62, 76, 108, 132, 138, 170, 200, 2043041, 54, 106, 110Class B136, 1687, 9, 11, 13, 14, 23, 24, 25, 28, 33, 35, 36, 38, 43, 44, 46, 58, 72, 73, 77, 78, 94, 104, 134, 140, 142, 152, 154, 156, 164, 172, 178, 184, 23218, 22, 45, 60, 122, 126, 146—Class C40, 128, 1606, 26, 27, 56, 57, 74, 130, 162——Class D——90, 105, 150—


## 5. Discussion

Our results indicate that the amount of functions that environments induce on volume differs strongly among the ECA rules.Within the range of variables investigated, increasing the environment size appears to always increase the number of induced functions. To see that this is not trivially obvious consider the following argument. For a fixed volume sizem, every environment configuration xE1 at a given environment thickness n1 will be a partial environment configuration at any larger environment thickness n2. This also means that any function f1:XV⟶XO1 induced by E1 is still implemented by the partial environment. However, for the larger environment thickness n2, we count function from V to the output cells O2≠O1 which have moved further outward in the future light cone. This means that two different induced functions f1,g1:XV⟶XO that differ for a smaller environment thickness do not guarantee the existence of two different functions f2,g2:V⟶XO2 for the larger environment thickness n2.The existence of local maxima shows that, in general, certain environments can transform volumes of particular sizes in more ways than others. This indicates a preferred relation between the scales of environment and volume. The exceptional rules show that it is possible for environments to exhaust their transformational capacity for nontrivial volume sizes of close to half the environment size (environment size is double the environment thickness). Note that the exceptional rules all show local maxima/preferred scales as well. On the other hand, it is compatible with our results that there is a minimal volume size (increasing with environment thickness) after which a given environment exhausts its transformational capacity (e.g., Figure8, which also shows a repetitive pattern). The fact that only 3 rules are exceptional is itself interesting. These rules more than others allow the environments to transform volumes in many ways.We do not however reach a conclusive explanation for the number of functions in dependence on environment thickness and volume sizes presented in Results Section.The preferred relation between scales of environment and volume is itself an interesting effect, which may bear significance on the nature of complexity growth in the study of living systems. Under certain conditions, environments may rapidly exhaust their transformational capacity over volumes they enclose, in turn limiting the realm of possibilities to implement functions connected to the living state. In later studies, this approach may need to be extended to study how different volume shapes and contact surfaces between environments and volumes can affect the number of induced functions.Note that in case we made the choice to limit the number of functions by not counting functions which do not allow an additional input-output pair, i.e., pair of volume cells to output cells configuration, to be realized, the number of functions would come to capture a measure of controllability. In that case, the drop of induced functions for the exceptional rules would signify a loss of control from the environment, in spite of the device’s volume increasing in size. This relates to the trade-off between stability and controllability that Janzing [5] calls lower bound of entropy influx. This means that the ability of environment cells to control degrees of freedom of a given volume conflicts with the ability to isolate the target control region. In future work, we would like to pursue this way further to tackle questions of control, controllability, and thermodynamics.



---

*Source: 7501405-2021-06-29.xml*