11institutetext: L’École normale supérieure de Paris

# Unsupervised Learning in Complex Systems

Hugo Cisneros

(15 Mai 2022)

## Résumé

Résumé

Dans cette thèse, nous explorons l’utilisation de systèmes complexes pour
étudier l’apprentissage et l’adaptation dans les systèmes naturels et
artificiels. L’objectif est de développer des systèmes autonomes capables
d’apprendre sans supervision, de se développer de manière autonome et de
devenir de plus en plus complexes avec le temps. Les systèmes complexes
apparaissent comme un cadre adapté pour comprendre ces phénomènes en raison de
leur capacité à croître en complexité. Être en mesure de construire des
algorithmes d’apprentissage qui nécessitent peu ou pas de supervision
permettrait une plus grande flexibilité et adaptabilité dans diverses
applications. En tentant de comprendre les principes fondamentaux de
l’apprentissage dans les systèmes complexes, nous espérons améliorer notre
capacité à concevoir et à mettre en œuvre des algorithmes d’apprentissage à
l’avenir. Cette thèse apporte les contributions suivantes : le développement
d’une métrique de complexité générale que nous appliquons pour rechercher des
systèmes complexes qui présentent une croissance de complexité, l’introduction
d’une méthode pour étudier les calculs dans des systèmes complexes à grande
échelle, et le développement d’une métrique pour l’efficacité de
l’apprentissage ainsi que l’introduction d’un jeu de données de référence pour
évaluer la vitesse des algorithmes d’apprentissage. Nos résultats contribuent
significativement à notre compréhension de l’apprentissage et de l’adaptation
dans les systèmes naturels et artificiels. De plus, notre approche contribue à
une nouvelle direction prometteuse pour la recherche dans ce domaine. Nous
espérons que ces résultats inspireront le développement d’algorithmes
d’apprentissage plus efficaces et plus performants à l’avenir. Apprentissage
automatique $\star$ Intelligence artificielle $\star$ Systèmes complexes
$\star$ Complexité

## Abstract

Abstract

In this thesis, we explore the use of complex systems to study learning and
adaptation in natural and artificial systems. The goal is to develop
autonomous systems that can learn without supervision, develop on their own,
and become increasingly complex over time. Complex systems are identified as a
suitable framework for understanding these phenomena due to their ability to
exhibit growth of complexity. Being able to build learning algorithms that
require limited to no supervision would enable greater flexibility and
adaptability in various applications. By understanding the fundamental
principles of learning in complex systems, we hope to advance our ability to
design and implement practical learning algorithms in the future. This thesis
makes the following key contributions: the development of a general complexity
metric that we apply to search for complex systems that exhibit growth of
complexity, the introduction of a coarse-graining method to study computations
in large-scale complex systems, and the development of a metric for learning
efficiency as well as a benchmark dataset for evaluating the speed of learning
algorithms. Our findings add substantially to our understanding of learning
and adaptation in natural and artificial systems. Moreover, our approach
contributes to a promising new direction for research in this area. We hope
these findings will inspire the development of more effective and efficient
learning algorithms in the future. Machine learning $\star$ Artificial
Intelligence $\star$ Complex systems $\star$ Complexity

## Acknowledgments

Acknowledgments

I express my sincere gratitude to Professor Josef Sivic and Tomas Mikolov for
their invaluable guidance, enthusiasm, and endless encouragement, without
which this thesis would not have been possible.

I am very grateful to a number of people who have directly or indirectly
influenced and helped me in my work, both as colleagues and friends: Jelle,
Barbora, Kateryna, Teven, and David. Special thanks to Barbora Hudcová and
Josef Sivic for their meticulous proofreading of parts of this thesis.

I would also like to thank everyone at the Foundational AI Lab and the
Automated Reasoning Lab of the Czech Institute of Informatics, Robotics and
Cybernetics (CIIRC) for creating a welcoming and supportive work environment.

Most importantly, I would like to express my deep appreciation to my parents,
family, and friends for their support and understanding throughout my academic
journey.

Lastly, I would like to express my heartfelt thanks to Brune for her
unwavering patience, help, support, and constant inspiration.

###### Contents

  1. 1 Introduction
    1. 1.1 Goal
    2. 1.2 Motivation
    3. 1.3 Challenges
      1. 1.3.1 Design of a complex system
      2. 1.3.2 Complex systems control
      3. 1.3.3 Open-ended evolution without objectives
      4. 1.3.4 Complex systems inputs and outputs
    4. 1.4 Contributions
    5. 1.5 Thesis overview
    6. 1.6 Publications and software
  2. 2 Background
    1. 2.1 Cellular automata
      1. 2.1.1 Definition
      2. 2.1.2 Classification of cellular automata
      3. 2.1.3 Cellular automata variants
      4. 2.1.4 Parametrizing and sampling CA rules
    2. 2.2 Cellular automata and Recurrent neural networks
      1. 2.2.1 RNN formalism
      2. 2.2.2 Transition rule as a set of convolutions
      3. 2.2.3 Adding inputs and outputs
      4. 2.2.4 Consequences
      5. 2.2.5 Beyond the naive rule representation
    3. 2.3 Reservoir computing
      1. 2.3.1 Reservoir computing applications
      2. 2.3.2 Echo-state network
      3. 2.3.3 Reservoir cellular automata
  3. 3 Literature Review
    1. 3.1 Measuring complexity
      1. 3.1.1 Information content
      2. 3.1.2 Shannon Entropy
      3. 3.1.3 Rényi Entropy
      4. 3.1.4 Mutual information
      5. 3.1.5 Computational complexity
      6. 3.1.6 Solomonoff–Kolmogorov-Chaitin complexity (algorithmic complexity)
      7. 3.1.7 Lempel-Ziv complexity
      8. 3.1.8 Logical Depth
      9. 3.1.9 Thermodynamic Depth
      10. 3.1.10 Epsilon-machines
      11. 3.1.11 Sophistication
    2. 3.2 Emergence
    3. 3.3 Evolutionary algorithms
      1. 3.3.1 Genetic programming
      2. 3.3.2 Novelty search
    4. 3.4 Open-ended evolution
      1. 3.4.1 Defining open-endedness
      2. 3.4.2 Open-endedness in cellular automata
      3. 3.4.3 Artificial chemistries
    5. 3.5 Computing with complex systems
      1. 3.5.1 Computing in cellular automata
      2. 3.5.2 Amorphous computing
  4. 4 Measuring complexity in evolving complex systems
    1. 4.1 Introduction
    2. 4.2 Related work
      1. 4.2.1 Artificial life and open-ended evolution
      2. 4.2.2 Cellular automata
      3. 4.2.3 Compression and complexity
    3. 4.3 Compression-based metric
    4. 4.4 Predictor-based metric
      1. 4.4.1 Joint compression
      2. 4.4.2 Count-based predictor
      3. 4.4.3 Neural network based predictor
    5. 4.5 Experiments
    6. 4.6 Discussion
    7. 4.7 Conclusion
  5. 5 Visualization of computations in large-scale complex systems
    1. 5.1 Introduction
    2. 5.2 Related work
      1. 5.2.1 Coarse-graining in cellular automata
      2. 5.2.2 Filtering
      3. 5.2.3 Scaling-up cellular automata
    3. 5.3 Proposed coarse-graining of cellular automata
      1. 5.3.1 Frequency histogram coarse-graining
      2. 5.3.2 Clustering
      3. 5.3.3 Autoencoders for coarse-graining
    4. 5.4 Results
      1. 5.4.1 Domains and filtering
      2. 5.4.2 Results on elementary cellular automata
      3. 5.4.3 Complexity metrics and coarse-graining
      4. 5.4.4 Discussion
    5. 5.5 Conclusion
  6. 6 Learning efficiency in deep reservoir computing
    1. 6.1 Introduction
    2. 6.2 Related work
    3. 6.3 A benchmark for reservoir computing
      1. 6.3.1 Performance metric
      2. 6.3.2 Description of tasks in the benchmark
    4. 6.4 Standard language classification task
    5. 6.5 Reservoir computing and reservoir cellular automata
    6. 6.6 New benchmark: compared methods
      1. 6.6.1 Fully trained sequential models (RNN, LSTM and Transformer)
      2. 6.6.2 Echo-state networks and reservoir cellular automata
      3. 6.6.3 Experimental set-up
    7. 6.7 Human performance evaluation
    8. 6.8 Experimental parameters
      1. 6.8.1 Task generation parameters
    9. 6.9 Results
    10. 6.10 Reservoir cellular automata (ReCA) results
      1. 6.10.1 Binary sequences
      2. 6.10.2 Symbol counting
    11. 6.11 Conclusions
  7. 7 Conclusion
    1. 7.1 Contributions

##  Chapter 1 Introduction

###  1.1 Goal

Complex systems are systems composed of many interconnected elements that
interact with each other, often in non-linear ways, giving rise to emergent
properties that cannot be explained by the properties of the individual
elements alone. In many naturally occurring complex systems, learning is a key
process that allows the system to adapt and evolve over time. In this thesis,
we explore complex systems as a framework for studying learning and adaptation
in natural and artificial systems. The aim of this thesis is to develop
methods for studying and using computations that take place in complex
dynamical systems to eventually create learning algorithms that require
limited to no supervision. Complex systems often exhibit features such as
self-organization, adaptation, feedback loops, and the ability to undergo
phase transitions, all of which can make them challenging to model and
predict. Examples of complex systems that occur naturally include ecosystems,
weather patterns, financial markets, social networks, and biological
organisms. The objective of this thesis is broken down into the following
subgoals:

  1. 1.

The first subgoal is to identify complex dynamical systems that have the
potential to display emergent open-ended growth, which refers to the ability
of a system to spontaneously generate new levels of complexity over time
without reaching a state of equilibrium. This growth is often associated with
evolutionary-like properties, such as variation, selection, and inheritance.
There are many ways to define complex systems, and as illustrated in Figure
1.1, some may exhibit more interesting and promising behaviors than others. A
cellular automaton (CA) is an instance of a complex system that can be
described as a grid of cells that can take on a finite set of states and
change their state over time according to a set of rules that depend on the
states of their neighboring cells. Interesting Cellular automata, such as the
one shown in Figure 1.1(b) may be hard to find depending on how the search
space is defined. The work presented in Chapter 4 aims to construct a metric
of complexity that can help to identify interestingly behaving complex
dynamical systems.

(a) A disordered cellular automaton.

(b) A cellular automaton with visible emergent structures.

Figure 1.1: Two examples of complex systems (cellular automata) with different
behavior types. 1.1(b) and 1.1(a) show a single state of a randomly
initialized 2D CA simulated for a fixed number of steps. Some CAs appear more
promising than others for the design of unsupervised learning systems because
of their emergent complex structures (visible in 1.1(b)), whereas the CA in
1.1(a) seems to behave randomly.

  2. 2.

The second subgoal is to measure the fraction of systems that have the most
complex and rapidly evolving behavior. Defining these notions is also part of
the goal. This sub-goal is distinct from the first one, which focuses on
complex system design in general. Instead, this sub-goal involves establishing
approaches to evaluate growth in complexity. We believe that systems with the
most complex and rapidly evolving behavior are promising for further use since
they may exhibit open-ended complexity growth. In Chapters 4 and 5, we present
different methods to measure the evolving complexity and understand when the
complexity increases over time. Chapter 5 of this thesis is dedicated to
investigating the importance of multiscale analysis for the complexity of
cellular automata, which is the process of studying a system at different
levels of detail or resolution. Additionally, we identify complex systems with
behavior that changes when we manipulate the scale of the system, either by
increasing or decreasing its size.

Figure 1.2: Filtering the behavior of elementary cellular automaton rule 18.
This uncovers a highly structured behavior with the propagation of area
boundaries within the apparent randomness. (a) shows 300 timesteps of a
randomly initialized rule 18 simulation. Notice the complex structures made
visible in (b) with a filtering method. This Figure is discussed in more
detail in Chapter 5.

  3. 3.

Apply promising systems to challenging learning tasks where classical machine
learning models may fail or become less efficient. The goal is to define
various ways to apply evolving complex dynamical systems to some standard
learning tasks and to find out if it improves the performance or efficiency of
the learning algorithm. An example application that we explore in Chapter 6 is
illustrated in Figure 1.3, where a CA is used to implement a language model, a
probabilistic model that is used to generate text to complete sentences. In
Chapter 2, we explore the similarities between CAs networks and highlight the
numerous potential applications of CAs.

Figure 1.3: An example of using a cellular automaton and reservoir computing
to implement a language model. Tokens are encoded within the cellular
automaton internal state. The cellular automaton update rule is then applied,
and an output value is decoded from the final state. Each vertical bar
represents two consecutive internal CA states, which are enriched with the
encoded input.

In this thesis, we do not focus our attention on what the machine learning
community commonly refers to as “unsupervised learning”, that is, learning
underlying structures from unlabeled data [123]. In machine learning,
supervision refers to a label, a number, or a collection of numbers that
represents an expected outcome associated with some input data. Our goal is to
construct models that can develop autonomously without necessarily needing any
external data or interactions. Therefore, we first seek systems that behave
that way on their own and postpone the issue of learning to optimize a
particular objective function to the end of the thesis (Chapter 6). We are
particularly interested in systems that can develop through internal evolution
rules without any input, which is the case for many complex systems.

Throughout the thesis, we work toward achieving these goals, focusing on one
particular complex system: the cellular automaton [321]. This model has been
extensively studied due to its simple definition and its ability to simulate a
wide range of complex behaviors. We provide a detailed description of cellular
automata in Section 2.1. This thesis provides new insights into the role of
learning in complex systems and open-ended evolution and demonstrates the
potential of cellular automata as a model for studying these phenomena.

###  1.2 Motivation

It is possible that some form of evolutionary mechanism may be necessary in
order to achieve advanced forms of artificial intelligence (AI), particularly
if the goal is to create intelligent systems that can adapt and learn in
complex and changing environments. Complex dynamical systems could be the key
to overcoming the problems with existing learning algorithms, such as
difficulties in generalization, robustness, or the ability to learn
continuously [238]. The natural intelligence of biological systems seems to
depend on emerging properties selected through evolution. For example,
biological life exhibits a pattern of major evolutionary transitions in which
autonomously replicating entities at the lower level merged to form a single
more complex corporate body [186]. This is believed to have occurred for the
emergence of eukaryotic cells, as well as for multicellular life [112]. All
complex and diverse biological entities have presumably emerged from a single
common ancestor and, even before, from inorganic components present on the
surface of the Earth [328, 284].

So far, it remains uncertain which algorithmic characteristics might enable an
artificial system to exhibit a path comparable to the natural evolutionary
process within its state space, which involves the transition from basic
constituents to intricate entities. Producing emerging phenomena similar to
those of nature _in silico_ is a long-standing challenge. Many algorithms try
to mimic evolutionary properties to solve particular tasks, called
evolutionary algorithms [87, 203, 14]. However, most of these methods focus on
searching the space of solutions using high-level evolutionary mechanisms,
such as genetic mutations and crossovers. Although effective in solving
precise tasks, these methods often obscure another crucial component of
natural evolution by using an explicit fitness function and hard-coded
primitives.

Most existing machine learning algorithms rely on the choice of an objective
function: a clearly defined mapping from the current state and parameters of a
model to a real value, which indicates the performance of that model. The
function depends on the objective of the model. For a supervised learning
problem, we may count the number of misclassified objects or the distance
between the predictions and the expected results. Even in unsupervised
learning, the family of algorithms used for learning from unlabeled data,
objectives are still central. For example, the well-known K-means clustering
algorithm minimizes the sum of square distances of data points to cluster
centers.

This reliance on objective functions creates two main issues: (i) The
objective is not always clearly defined or can be too broad for general-
purpose applications. For example, a possible objective function of a walking
robot could be “not fall when stepping through its surrounding environment”.
This function is impractical to define and will vary greatly depending on the
parameters of the environment (e.g. depending on the terrain, malfunctioning
or missing limbs of the robots). Indirect rewards such as “head not touching
the ground” may help, but it does not cover all possible ways the model could
fail. This problem of defining an objective is also present within our goal of
designing a general-purpose, autonomously developing learning algorithm.
Furthermore, (ii) using predefined functions as goals can be counterproductive
because, as many examples in nature demonstrate, robust paths to complex
objectives are often deceptive. They involve developing in unexpected
directions that may initially seem to be against the original goal [296].

In this thesis, the term _unsupervised_ refers to a form of learning with no
predefined objective. Like in natural evolution, we expect true unsupervised
algorithms to develop new features autonomously and become progressively more
complex over time. Such algorithms would regularly learn to solve problems on
their own without the need to be explicitly guided towards the problem
solutions, thereby discovering robust and diverse solutions to deceptive
problems.

###  1.3 Challenges

Figure 1.4: The challenges of working with complex systems encountered across
this thesis can be broken down into several categories. (1) The choice and
design of the system, (2) the control of the system which involves
understanding the complex mapping between a parameter space and the possibly
unpredictable behavior of a system, (3) the search for open-ended evolution
properties similar to the ones found in nature, (4) the issue of sending
inputs and reading outputs from the internal state of a complex system. This
illustration uses Lenia icon4.png by Bert Wang-Chak Chan, licensed under CC BY
4.0.

The study of complex systems presents a range of difficult challenges by
itself [261]. The complexity of a system is an emergent property that arises
from various factors, including its intricate structure, the number of
elements it contains, how it functions, and how it responds to different types
of external influences. These factors contribute to the overall complexity of
the system, which could be measured in various ways. For many complex systems,
their emergent mechanisms are poorly understood. We identify four main
challenges associated with the study of complex systems in the context of this
thesis: (i) the questions of the design choices in defining and sampling a
complex system (section 1.3.1), (ii) which will in turn define their potential
to support a form of open-ended evolution (section 1.3.3) and (iii) how we can
expect to build an interface to communicate with it (section 1.3.4), (iv)
which is essential to achieve some form of control of that system (section
1.3.2).

####  1.3.1 Design of a complex system

The first challenge is to construct a suitable complex system. The definition
of complex systems is broad, and several systems with interesting dynamics
have been studied under that name. For example, abstract models such as
L-Systems (formal grammars used to model the growth and development of organic
structures), Random Boolean networks (dynamical systems consisting of a fixed
number of binary nodes that are randomly connected to each other and updated
based on the state of its neighboring nodes), Turing machines (abstract
deterministic computing machines consisting of a tape and a read-write head)
and CA. In this thesis, we focus mainly on the last listed element: the
cellular automaton. There are multiple benefits to working with this model. It
is very simple to define, and its high parallelism makes its implementation
straightforward. Furthermore, CAs have shown the ability to simulate a wide
range of complex behaviors [332].

Choosing the right complex system architecture is essential because it defines
the search space over which interesting and useful systems can be found.
Correctly parameterizing that space can also be challenging because too many
degrees of freedom make it difficult to search for and find good systems,
while too few might indicate a lack of expressivity. An example
parameterization of CAs with little expressivity is Langton’s lambda parameter
[172]. At the other end of the spectrum, the CA rule is a simple
parametrization with many degrees of freedom, which makes it impractical.

Even when we limit ourselves to the study of CAs, many variants can be
considered (we list some of them in Chapter 2). They can have continuous or
discrete states and operate in continuous or discrete space. For discrete
state and space CAs, the number of states and the window of the update
function can vary, as well as the topology of the simulation space. We tackle
this issue from various angles throughout the thesis, exploring the question
of rule definition in Chapter 4, the scale in Chapter 5, and the connectivity
pattern in Chapter 6.

####  1.3.2 Complex systems control

(a) CA rule 22 on a tape of size 100, ran for 50 steps from a random initial
state.

(b) CA rule 22 on a tape of size 100 ran from a slightly different initial
state. The cells different from Figure 1.5(a) are overlayed in red.

Figure 1.5: Comparison of the same 1 dimensional CA ran from two initial
conditions differing only by one cell. Each row is the state of the CA at one
time step, with time increasing from top to bottom. The effect of the small
perturbation of initial conditions grows rapidly as the CA evolves in time.

Even if we want complex systems that evolve in unexpected directions and grow
in an open-ended way without supervision, it may still be useful to steer them
locally toward specific targets. A major challenge that follows from this goal
is that many complex systems are unpredictable. Deterministic dynamical
systems can exhibit behavior that is extremely sensitive to their initial
conditions. This sensitivity is sometimes referred to as chaos, where even
tiny perturbations in the initial conditions can result in significantly
different outcomes or trajectories. This is illustrated with a simple CA rule
in Figure 1.5. Because of this property, it is often very hard to predict how
a given system will evolve over time, and therefore hard to steer its
evolution towards a particular final state or along a chosen trajectory.
Although it can be challenging to apply these systems to certain basic tasks,
their ability to generate unexpected solutions to difficult problems is also
an advantage for the development of open-ended systems. Such systems need to
continuously produce new and diverse solutions without a predefined endpoint
and their sensitivity to initial conditions can be helpful in achieving this
goal.

This problem is also related to the issue of sending a control signal to a
complex system that depends on the choice of encoding for that signal. This
encoding can significantly impact the system’s ability to respond to the
control signal and generate the desired outcome, which we describe in Section
1.3.4.

####  1.3.3 Open-ended evolution without objectives

Another challenge is posed by the lack of a clear objective in the design of
fully unsupervised learning systems. Even without an objective, it is still
essential to understand which complex systems to choose from all available
options or how to tune their parameters so that they behave in interesting
ways. For example, CAs such as the one shown in Figure 1.1(a) is unlikely to
be useful for building systems that demonstrate a growth of complexity due to
their disordered nature in both space and time. Because of this disordered
behavior, they cannot preserve information about the past.

Our goal is to create a system that has the property of evolving in an open-
ended way, and we need metrics that can help select systems. However, these
metrics should not be used as an additional objective function, as doing so
would result in the problems described in Section 1.2. We address this
challenge in particular in Chapter 4, by designing a complexity metric that
can help select interesting complex systems without relying on a specific
task-based performance score.

####  1.3.4 Complex systems inputs and outputs

Some of the complex systems we study in this thesis are closed systems. They
do not expect inputs or have well-defined outputs. For example, CA and random
boolean network (RBN) do not have the notion of inputs and outputs built into
the model. They are standalone objects that evolve according to a set of
internal rules.

A common challenge for such systems is to define the inputs and outputs in a
way that preserves their internal dynamics. This is also related to the
control problem of Section 1.3.2, because controlling a complex system implies
being able to send a control signal and read the current state of the system.

Throughout this work, we use a framework called _reservoir computing_ (RC) for
this purpose. Reservoir computing allows one to harvest the internal
computations of complex systems, or _read_ information from its internal state
by learning a linear regression that maps that internal state to desired
outputs (see Section 2.3).

###  1.4 Contributions

The main contributions of this thesis are as follows.

  1. 1.

Our first contribution is a review of the literature (Chapter 3) describing
the connections between cellular automata and other complex systems, open-
ended evolution, and neural networks. Studying these fields from a single
point of view is a relatively novel endeavor, and we consider a review
necessary to place the rest of our work in its context.

  2. 2.

Our second contribution is the development of a general complexity metric that
can help identify complex systems with interesting behavior (Chapter 4). Our
findings were published in [51].

  3. 3.

The third contribution is the development of a coarse-graining method to
visualize computations in cellular automata and other discrete systems with
local interactions (Chapter 5). Our findings were published in [52].

  4. 4.

Our fourth contribution is the introduction of a learning efficiency metric
for learning algorithms and a benchmark dataset of progressively harder
language tasks (Chapter 6). Our findings were published in [50].

###  1.5 Thesis overview

Chapter 2 presents some background notions about complex systems, cellular
automata, and reservoir computing.

In Chapter 3, we review relevant methods and tools for measuring the
complexity of complex systems and use their computations for various tasks.

Chapter 4 introduces a complexity metric that allows us to select complex
systems with interesting behavior. The metric measures the “novelty” of the
temporal states of a system compared to a reference system. We built a dataset
of interesting cellular automata to validate the quality of the metric.

Chapter 5 addresses the question of large-scale complex systems and the
applicability of complexity metrics at multiple scales. We propose three
algorithms for the coarse-graining of cellular automata. This allows us to
reduce the size of large-scale systems while retaining the interesting parts
of the behavior.

Chapter 6 presents a learning efficiency metric and a dataset to measure the
learning speed of various systems. We show that reservoir computing-based
systems using cellular automata can be more efficient than usual machine
learning algorithms in constrained data and computation settings.

Chapter 7 summarizes our contributions to this thesis.

Chapter LABEL:cha:future_work outlines potential avenues for further research
in the field. It provides suggestions on how current work could be expanded or
improved, highlighting areas that require additional research to advance
understanding of the subject. We propose some experiments that could extend
the potential applications of cellular automata, as well as a theoretical
framework for learning in dynamical systems.

###  1.6 Publications and software

The thesis has led to the following publications.

  * •

[51]

  * •

[52]

  * •

[50]

The code to reproduce the experiments of all three publications is available
on GitHub: https://github.com/hugcis/evolving-structures-in-complex-systems,
https://github.com/hugcis/benchmark_learning_efficiency. We also published a
dataset that we used for our benchmark in our last publication. It is
available at https://github.com/hugcis/incremental_tasks/.

##  Chapter 2 Background

In this chapter, we provide background on some of the topics that we study in
the thesis. We begin by describing the cellular automaton (CA) model, which is
the complex system we focus on in most of the thesis (Section 2.1). Next, we
describe the similarities between CAs and recurrent neural networks (RNNs),
which is useful for understanding the characteristics and applications these
two models share (Section 2.2). CAs can be completely reformulated as a
special case of recurrent neural networks. This reformulation makes it natural
to replace recurrent RNNs with CAs in several use cases. We describe the
reservoir computing (RC) model (Section 2.3), which enables sending inputs to
and harvesting the computations of complex systems to perform machine learning
tasks without requiring explicit knowledge of the underlying system dynamics
or the need to solve complex optimization problems. We apply reservoir
computing to sequential language-like tasks in Chapter 6. This model was
developed with RNNs, but we describe how CAs and other complex systems can be
a suitable replacement, and the benefits of this approach.

###  2.1 Cellular automata

Stanislaw Ulam and John von Neumann proposed the CA model in the 1940s as a
means of modeling crystal growth and creating an autonomous self-replicating
system [321].

####  2.1.1 Definition

It is usually defined in a regular lattice in one or two dimensions. Each of
its components is called a cell and can be in a state $k\in\mathcal{S}$.
$\mathcal{S}$ is the space of available states for cells, usually chosen to be
$\\{0,1\\}$ for binary CAs or $\\{1,\ldots,n\\}$ for CAs with $n$ states.

A neighborhood function $\bm{N}$ is defined that associates each cell with the
indexes of its neighbors in the grid. In general, a CA can be constructed on
any space $\mathcal{L}$ where this function can be defined. The space
$\mathcal{L}$ specifies an index and the relationship between the cells. In
practice, regular finite or infinite grids are chosen,
$\mathcal{L}\subset\mathbb{Z}$ or $\mathcal{L}\subset\mathbb{Z}^{2}$. For
example, the grid could be a one-dimensional torus with 10 cells, that is,
$\mathcal{L}_{{T_{10}}}=\\{1,2,\ldots,10\\}$. The neighborhood function has
the following general form:

$\displaystyle\bm{N}_{\mathcal{L}}:$
$\displaystyle\mathcal{L}\rightarrow\mathcal{L}^{s}$ (2.1)
$\displaystyle{i}\mapsto[{c_{j}}]_{j\in\mathcal{N}_{c_{i}}},$

where $\mathcal{N}_{c_{i}}$ is the neighborhood of cell $c_{i}$, $s$ is the
number of cells in the neighborhood, and the returned value is a finite set of
cells: the neighbors of cell $c_{i}$. For the torus $\mathcal{L}_{T_{10}}$
above, we can define the neighbors to be the cell itself and the two
immediately adjacent cells. This type of 1D neighborhood is usually associated
with a _radius_ parameter $r=1$. The neighborhood $r=1$ is illustrated in
Figure 2.1(a). It corresponds to the following neighborhood function:

$\displaystyle\bm{N}_{\mathcal{L}_{T_{10}}}:$
$\displaystyle\mathcal{L}\rightarrow\mathcal{L}^{3}$ (2.2)
$\displaystyle\bm{N}_{\mathcal{L}_{T_{10}}}({i})=\begin{cases}[c_{i-1},c_{i},c_{i+1}],&\text{if}\quad
i\in\\{2,\ldots,9\\}\\\ [c_{10},c_{1},c_{2}],&\text{if}\quad i=1\\\
[c_{9},c_{10},c_{1}],&\text{if}\quad i=10.\\\ \end{cases}$

A larger radius $r$ would correspond to including more cells in the
neighborhood, going in each direction from the initial cell. On two-
dimensional grids, there are multiple ways to define the neighborhood. Some
common examples are the Moore neighborhood (see Figure 2.1(b)) and the von
Neumann neighborhood (see Figure 2.1(c)). In the rest, we omit the subscript
on the neighborhood function $\bm{N}$ as we almost always work with regular
grids on a torus, for which it is simpler to just mention the size and
dimension.

(a) Standard 1D CA neighborhood

(b) Moore neighborhood

(c) von Neumann neighborhood

Figure 2.1: Illustration of commonly used neighborhoods for 1D and 2D CA.

A CA evolves in discrete time steps. An update rule
$\bm{\Phi}:\mathcal{S}^{s}\rightarrow\mathcal{S}$ defines the new state of a
cell as a function of its local neighborhood at the current time step. The
local group of cells is said to be in a particular _configuration_. The
function $\bm{\Phi}$ is applied in parallel to all cells. For a CA in its
initial state at time step 0 — i.e., a set of cells
$\left(c_{i}^{(0)}\right)_{i\in\mathcal{L}}\in\mathcal{S}^{|\mathcal{L}|}$,
and a neighborhood function $\bm{N}$, we have the following update rule:

$\displaystyle\forall i\in\mathcal{L},\quad
c_{i}^{(t+1)}=\bm{\Phi}\left(\left(c_{j}^{(t)}\right)_{j\in\bm{N}(c_{i})}\right).$
(2.3)

The details of an update step in a 1-dimensional CA is shown in Figure 2.2 for
example. The neighborhood of the cell $c_{i}$ is $c_{i}$ itself, as well as
its two immediately adjacent cells.

Figure 2.2: Illustration of a cellular automaton update rule in 1 dimension.
For each cell, we look up the neighboring cells and update their state
according to the current state of the neighbors. This operation is applied in
parallel to the entire grid.

The function $\bm{\Phi}$ is sometimes called a _rule table_ because it
associates an output state for each possible combination of input neighbor
states. In an implementation of the CA model, these output states can be
looked up from a table or array containing all possible transitions from input
to output.

There are many ways to define CAs, and we gave a broad definition that
includes many rarely used CA variants. For another more straightforward
definition of CAs, see, for example, [149].

###### Rule representation.

A useful rule representation can be obtained by listing all output states
corresponding to input neighborhood configurations in a predetermined order.
This results in a list of values $[o_{1},\ldots,o_{s^{|\mathcal{S}|}}]$, with
$\forall i,\ o_{i}\in\mathcal{S}$, where $s$ is the number of cells in a
neighborhood, $\mathcal{S}$ is the space of available states, and
$|\mathcal{S}|$ is the number of available states per cell. Using $o_{i}$ as
the digits of a base-$|\mathcal{S}|$ number, each rule is uniquely represented
by a number. For example, as explained in more detail in Section 2.1.3, a one-
dimensional cellular automaton with a neighborhood of size three has eight
possible configurations of neighboring cells (000, 001, 010, 011, 100, 101,
110, and 111), each of which can map to two states (0 or 1). To obtain the
rule number, we concatenate the new states for each of the input
configurations, resulting in an 8-bit number. The 256 possible binary rules in
one dimension with neighborhood size 3 can be numbered from 0 to 255 with this
standard method and are referred to by their number in the literature.

###### Boundary conditions.

The grid of a CA can be finite or infinite. In the infinite case, the grid is
assumed to be initialized to a uniform state, except for a few cells set to
other states. The simulation is then run on these few cells, while the rest of
the infinite grid does not have to be simulated from the start. For a finite
grid, an exhaustive simulation can be run, but one needs to define boundary
conditions. The boundaries can be set to wrap around the other side of the
grid, forming a torus. An example of the corresponding indexing is given in
equation 2.2. Other choices of boundary conditions consist of adding virtual
padding cells outside of the main grid. They can be set to a fixed state, a
randomly chosen state, or they can mirror the cells inside the grid. Each of
these choices affects the evolution and properties of the CA, but the
importance of these boundaries decreases for very large grids.

####  2.1.2 Classification of cellular automata

Stephen Wolfram approached CAs as discrete, spatially extended dynamical
systems [331]. The analogy is only superficial since many concepts from
dynamical systems theory, such as “chaos”, “attractors” and “sensitivity to
initial conditions” only admit a rigorous definition in the continuous state
and continuous time models. Wolfram proposed a qualitative classification of
CA update rule behaviors roughly analogous to classifications in dynamical
systems theory, with four classes defined as follows.

Class 1

All initial configurations converge to a single fixed configuration, such as a
configuration consisting entirely of 1s.

Class 2

All initial configurations relax after a transient period to some fixed point
or some temporally periodic cycle of configurations, but which one depends on
the initial configuration. (CA defined on finite lattices always have periodic
behavior because there is only a finite number of grid configurations. Class 2
does not refer to this type of periodic behavior but rather to cycles with
periods much shorter than the total number of possible states).

Class 3

All initial configurations exhibit chaotic behavior after a short transient
period. (The term “chaotic” here refers to apparently unpredictable space-time
behavior, not the standard notion of chaos in dynamical system theory.)

Class 4

Some initial configurations result in complex localized structures that can
persist for a long time.

This classification being qualitative and not rigorous, there is not even a
clear consensus on which of the Elementary cellular automata rules (one
dimensional binary CAs with neighborhood size 3) belong to class 4 or class 3.
Class 4 CA rules are speculated to be capable of universal computation [331],
which refers to the ability of a system to simulate any other system or
computation, given enough time and memory. For example, [181] claimed that ECA
rule 110 has class 4 behavior and was eventually proven to be universal [53],
but no other ECA has been proven universal since.

[347] studied the compression size of the space-time diagrams of all ECA for a
fixed-length simulation. Using a simple k-means clustering technique, he
obtained two groups that roughly match Wolfram’s classes 1 and 2 and classes 3
and 4. We reproduce these results in Figure 4.1(b) in Chapter 4. They offer an
interesting nonqualitative confirmation of the results of Wolfram’s
classification. However, these results vary significantly if we modify the
initial conditions, as well as the grid size, data representation, or
compression algorithm [128].

[337] studied the behavior of ECAs when the simulations are reversed and
computed the preimages of each configuration. They introduced the Z-parameter,
which is the probability that a partial preimage can be extended by one symbol
for each CA. The authors speculate that class 4 occurs at $\text{Z}\approx
0.75$. This is not a classification but a class 4 membership test that can be
computed from the rule directly, making it practical compared to alternatives.
However, when tested in practice, Wuensche’s hypothesis that $\text{Z}\approx
0.75$ corresponds to class 4 is rarely verified.

Hudcová defined a classification of CA that is based on the form of the
asymptotic growth of its transients, obtained by repeated simulation of the
rules of CA starting from various initial conditions and using the best
fitting function for the asymptotic growth of its transients [128, 130]. For a
detailed review of the current methods and challenges of CAs classifications,
see [319].

####  2.1.3 Cellular automata variants

Several CA variants have been proposed, modifying or restricting various parts
of the definition in Section 2.1.1. Here, we list some common ones.

###### Elementary cellular automata.

ECA are 1 dimensional CAs with two states per cell and neighborhood size 3 —
the cell and its two direct neighbors on the 1D grid. There are 8 possible
configurations of a neighborhood with 3 cells and 2 states per cell, which
corresponds to 256 possible ways to define an ECA — two possible outputs for
each of these 8 possible configurations; hence $2^{8}=256$ possible CA. This
relatively small number of rules allows for an exhaustive exploration of the
rule space and mapping of the properties of ECA, which would not be possible
for general CAs.

Figure 2.3: Illustration of the rule of ECA number 150.

These CAs have been extensively studied and offer an interesting combination
of trivial definition and implementation, and complex and unpredictable
properties. One of the fundamental problems of CA research is to classify the
256 rules into well-defined behavior types and order them by complexity, which
was attempted in several previous works [337, 110, 335, 332, 347, 128, 129].
We discuss these classifications in more detail in Section 2.1.2.

(a) Single cell initialization

(b) Random initialization

Figure 2.4: Evolution of ECA number 150 simulated on a grid of size 100 for 50
steps. 2.4(a) shows a simulation starting from a blank grid with only one cell
set to 1. 2.4(b) shows a simulation starting from a random initialization.
Time flows from top to bottom, and each row of cells represents a single
internal CA state at a single time step.

ECA rules are easily visualized because there are only eight possible
neighborhood configurations that need to be shown. For example, Figure 2.3
shows the transition table for ECA Rule 150. If we assign 1 to the black state
and 0 to the white state, the possible neighborhood configurations are ordered
in their binary order from right to left, with the leftmost bit being the most
significant. This is how the rule number is computed, using the output states
(last row in Figure 2.3) as a binary representation. Example simulations of
ECA rule 150 starting from various initial states are shown in Figure 2.4. In
these representations, time flows from top to bottom, and each row of cells
represents a single internal CA state at a single time step. This
representation of an ECA rule is often called a _spacetime diagram_.

There are several well-known ECA rules with particularly interesting
properties. For example, a universal computer has been constructed in rule 110
[53], making it the first (and only to date, although ECA Rule 54 is
postulated to be as well) Turing complete ECA.

###### Totalistic cellular automata.

Totalistic CA are a subset of CA whose rules can be expressed as a function of
the sum of neighboring cell values. These CA were introduced by Stephen
Wolfram [330]. ECA 150 is an example of a totalistic CA, and its rule and
typical space-time diagram are depicted in Figures 2.3 and 2.4. Its rule could
be summarized in natural language as “if exactly two states are 1 or all
states are 0, the next state is 0. Otherwise, if one or three states are 1,
the next state is 1”. Conway’s Game of Life, presented in the following
paragraph, is an example of a totalistic CA in two dimensions.

###### Game of Life.

The game of life is one of the most famous CA. It was proposed by the
mathematician John Conway in 1970 [92]. It is a two-dimensional binary CA. Its
two states are often called “alive” and “dead”. Its rule can be summarized in
three sentences as follows.

  * •

Any live cell with two or three live neighbors survives.

  * •

Any dead cell with three living neighbors becomes a live cell.

  * •

Other live cells and already dead cells are dead in the next generation.

This CA has a particularly active community dedicated to finding interesting
patterns with particular properties, such as long cycling periods or
particular speeds of movement through the grid. Some of these patterns have
been used as memory registers and communication channels to build a Universal
Computer [132]. This construction proved that the game of life is Turing
complete. This property is thought to be also shared by other CAs — it is
proven for at least ECA rule 110 [53]. This makes CAs models theoretically
appealing for the design of a learning algorithm because they can simulate any
algorithm.

(a) Moving oscillator
(_glider_).

(b) Fixed pattern
(_still life_).

(c) Period 3 oscillator
(_pulsar_).

Figure 2.5: Some game of life patterns with various properties. The moving
oscillator 2.5(a) moves 1 cell along the bottom right diagonal every 4 steps.
The fixed pattern 2.5(b) never changes except if it interacts with others. The
oscillator 2.5(c) loops through three different configurations.

###### Asynchronous cellular automata.

A cellular automaton is said to be asynchronous when its cells are not updated
in parallel at each time step. Various cell update schemes can be chosen.
Asynchronous CAs have to define an order of update of the cells, which is not
easily defined on an infinite grid. Therefore, most implementations are done
on finite grids. This update order can be random, follow a predefined order,
or be decided by a global controller. Groups of cells can be updated
simultaneously, or updates can be done cell by cell. The many effects of
asynchronous updates can be difficult to predict and can make these types of
CAs relatively difficult to work with.

Asynchronous CAs are an attractive model when using large systems for which
parallel update is prohibitively expensive. The rule could adapt itself and
preferentially update cells in active or useful parts of the CA while doing
slower updates to the less active parts of the CA. An asynchronous CA with
evolutionary properties was constructed in [220]. The authors argue that
asynchronicity is a strong advantage in the construction of systems that can
evolve within CAs.

###### Stochastic cellular automata.

In a stochastic cellular automaton, the update function $\bm{\Phi}$ is
stochastic. This means that the next state of all cells in the grid is sampled
from a probability distribution that depends on the current neighborhood
configuration. We can write

$\displaystyle\forall i\in\mathcal{L},\ s\in\mathcal{S}\quad
p\left(c_{i}^{(t+1)}=s\right)=\bm{\Phi}\left(\bm{N}\left(c_{i}^{(t)}\right)\right)(s).$
(2.4)

These CAs have had successful applications in physics [318, 231] or biology
[27], because their stochasticity allows modeling complex physical phenomena.

###### Continuous cellular automata.

Another family of CAs uses real-valued states, often restricted to the range
$[0,1]$. The update function is then a real multivariate function, which we
can write

$\displaystyle\bm{\Phi}:[0,1]^{s}\rightarrow[0,1].$ (2.5)

Examples of continuous CAs include Lenia, which uses convolutional operators
followed by thresholding for the update rule [44], or neural cellular automata
[210] which represent CAs as neural networks (more details in Sections 2.2 and
3.5.1). [93] explores the condition for a real-valued CA to be able to compute
real-valued functions.

###### Higher dimensional cellular automata.

CAs of dimension greater than 2 have been comparatively less studied for
several reasons, including the limits that arise when simulating and
visualizing systems in more than 2 dimensions on a computer screen. Another
problem is with the increasing number of possible rules in higher dimensions.
The number of neighbors per cell grows exponentially with dimension, and the
number of possible rules has a doubly exponential growth rate. This makes the
convenient representation of CAs rules as tables infeasible since the size of
that table quickly exceeds the available memory of most computers. For
example, there are $2^{9}=512$ possible $3\times 3$ configurations of a binary
Moore neighborhood (see Figure 2.1(b)) in 2D that can each lead to 2 states,
which means that there exists $2^{512}\approx 10^{154}$ distinct 2D rules with
2 states and a Moore neighborhood. This is already an incomprehensibly large
number, but there are $2^{134,217,728}\approx 10^{40,403,562}$ such rules in
3D. In general, there are $2^{3^{n}}$ possible binary CA rules with a Moore-
like neighborhood in dimension $n$.

Despite these limitations, several works have studied higher dimensions CAs,
although mostly in 3 dimensions [308, 298]. For example, there are several
examples of successful 3D CA simulations applied to material sciences [91, 12,
236, 70].

###### Hexagonal cellular automata.

Hexagonal CAs are defined on grids tiled with hexagons, where each cell has 6
direct neighbors.

(a) Range 1 neighborhood

(b) Ray neighborhood

Figure 2.6: Example definition of the neighborhood for hexagonal cellular
automata.

One advantage of this type of CAs over regular grids is the absence of
preferred direction since they are all equivalent. In a square grid,
diagonally adjacent cells span more distance than directly adjacent cells,
whereas on a hexagonal grid, all neighbors are equivalent [211].

####  2.1.4 Parametrizing and sampling CA rules

As explained in Section 1.3, one of the main challenges of working with
complex systems is the parametrization and control of the behavior of that
system. CAs are no exception, and several parametrization schemes have been
proposed, with their respective benefits and drawbacks. There are infinitely
many ways to define rules for CAs, and for each of these definitions, a very
large number of rules are available, making it impossible to sample a
significant portion of the rule space. A good parametrization allows one to
scan a wide range of behaviors of CAs by traversing the space in an
interesting way.

###### Langton’s lambda.

Christopher Langton proposed one of the first parameters that could be used to
control the behavior of CAs to a certain extent [170, 172]. For a CA with
$K=|\mathcal{S}|$ states and a state arbitrarily chosen to be the _quiescent_
state (this corresponds to the “dead” state in the game of life, for example),
if there are $n$ transitions to the quiescent state within the rule table and
$K^{s}-n$ remaining transitions that do not lead to the quiescent state, where
$s$ is the number of cells in the neighborhood, we have

$\displaystyle\lambda=\frac{K^{s}-n}{K^{s}}.$ (2.6)

For Langton, the purpose of $\lambda$ is to search the space of CAs in an
ordered manner by varying the value of the parameter. His procedure starts
with a rule with all transitions leading to the quiescent state. The value of
$\lambda$ is increased in discrete steps to $1-1/K^{s}$ by randomly changing
the transitions of the rule to lead to a different state. An illustration of
the behavior change of a CA rule under this procedure is shown in Figure 2.7.
Langton collected various measures of the dynamical behavior of CA and studied
them as a function of $\lambda$. He observes a phase transition as $\lambda$
approaches its maximal value, where CAs seem to behave in the most complex
way, with long transients and large-scale propagating structures. He calls
this phase transition “edge of chaos” because it corresponds to $\lambda$
values just before the generated CAs become chaotic.

Figure 2.7: The effect of varying $\lambda$ for a 1D binary CA rule. A CA rule
is progressively modified along a trajectory of increasing $\lambda$. The rule
starts with a fixed behavior, becomes periodic, and then complex when hitting
the “edge of chaos”. Note the localized structures that spread over time (down
along the y axis) and interact in the fourth figure. When $\lambda$ increases
further the rule becomes chaotic.

###### Dirichlet sampling.

For an arbitrary number of states and an arbitrary neighborhood size, it can
be challenging to sample CAs while scanning the wide range of behavior these
models are capable of simulating. This is because the size of the space of CAs
rules is very large. The naive method of uniformly sampling each transition
output is not useful in large rule spaces with multiple states, large
neighborhoods, or grid dimensions larger than 1.

Rules with equal proportions of transitions leading to all states tend to be
the most chaotic. This is also what Langton observed when studying the
$\lambda$ parameter. This is explained by the fact that sampling each
transition output uniformly is equivalent to sampling the rules from a
multinomial distribution with the number of possible states ($K$), number of
possible transitions ($n=K^{K^{s}}$, with $s$ the number of cells in a
neighborhood), and the uniform probabilities $p_{1}=\ldots=p_{K}$ as
parameters. A random variable $X=(X_{1},\ldots,X_{K})$ indicates the number of
times each result is observed. The probability mass function of this
distribution is

$\displaystyle P(X_{1}=x_{1},\ldots,X_{K}=x_{k})=\frac{n!}{x_{1}!\cdots
x_{K}!}p_{1}^{x_{1}}\cdots p_{K}^{x_{K}}.$ (2.7)

This quantity becomes vanishingly small for large $n$ (that is, rules with
many states or large neighborhoods) and rules with an output transition skewed
towards a specific state. For example, the binary Game of Life rule has 372
transitions leading to state 0 and 140 leading to state 1. The probability of
sampling a rule with these transition proportions is $8.24\mathrm{e}{-26}$
(compared to a $17\%$ probability of sampling a rule with between 254 and 257
transitions to 0). Using a uniform transition sampling method makes it highly
improbable to obtain a rule resembling the Game of Life, let alone the rule
itself.

We propose a Dirichlet sampling method as an alternative way to sample rules
with fixed ratios of transitions leading to each output state. For a rule with
$K$ states, we sample a $K$-uple from a Dirichlet distribution of order $K$
with parameters $(\alpha_{k})_{k\in[1,K]}$ where
$\alpha_{0}=\alpha_{1}=\ldots=\alpha_{K}=\alpha<1$. The result is a quantile
$K$-uple $(q_{1},\ldots,q_{K})$. For $\alpha<1$, the distribution is
concentrated around the corners of a simplex of dimension $K$, which means
that it preferably samples a tuple with one of its values dominating the
others.

Rules are sampled so that the number of transitions to each output state
matches the quantile generated from the Dirichlet distribution. The samples
will be more likely to have a dominant quantile, which can be associated with
the quiescent state in Langton’s $\lambda$ calculation. The resulting sampling
of cellular automata is much better for scanning the entire space of rules and
generating CA rules that would be impossible to reach with the naive sampling
method, as illustrated in Figure 2.8.

Figure 2.8: An illustration of the difference between naive uniform rule
sampling and Dirichlet sampling on binary rules. 10000 2D binary CA rules were
sampled with each method, the plot displays a histogram of their average
output state. Uniform sampling leads to more rules with an average output
state close to 0.5, meaning approximately as many transitions toward both
states. Dirichlet sampling can control, through the choice of parameter
$\alpha$, how many rules with more skewed transitions should be sampled, which
is shown by the spikes on the blue histogram close to 0 and 1.

###### Smooth sampling with the recurrent convolutional neural network
analogy.

The recurrent convolutional network analogy of CAs (see Section 2.2 for
details) formulates a CA as a neural network. In this paradigm, the rule of a
CA is completely determined by the parameters of that neural network. This
allows us to modify the CA rules as we would change the weights of a neural
network. For example, as long as all simulation steps are differentiable, the
backpropagation algorithm can be applied and used to update a CA rule by
updating the weights of the neural network with gradient descent.
Dimensionality reduction methods applied to the parameter space of the neural
network can help to understand the structure of that space and the CAs
behaviors produced by different sets of parameters.

###  2.2 Cellular automata and Recurrent neural networks

The purpose of this section is to show that cellular automata and recurrent
convolutional neural networks have very strong connections and to draw this
parallel as clearly as possible. We express the CA update function as a set of
convolutional operations that can be derived from any CA rule.

This connection yields interesting consequences for both the theoretical
properties of these models and the potential applications of CAs and recurrent
networks. It shows, for instance, that emergent properties with increasing
complexity and perhaps open-ended development that we expect from complex
systems such as CAs are possible within the hidden state of a recurrent neural
network.

The conceptual similarity between CAs and neural networks is not surprising.
Fundamentally, CAs represent the paradigm of emergence, in which the origins
of complex behaviors are searched for in an assemblage of possibly very simple
parts rather than being viewed as a sum of complex building blocks. It is
often argued that there is no better-known example of a truly emergent
phenomenon than that of the emergence of consciousness out of the large
network of functionally simple (and certainly unconscious) neuronal components
that make up the human brain. A biological neural network consists of a large
space of interconnected nodes with dynamic behavior that is a local function
of the other nodes to which it is connected, which is strikingly similar to
the principle of a CA. Artificial neural networks can be thought of as being a
set of biologically inspired CA rules [134]. The more precise parallel between
cellular automata and a form of recurrent/convolutional network has also been
drawn by several other researchers [338, 96, 210].

In this section, we formally describe the relation between CAs and RNNs and
discuss the extensions this implies for the CA model, as well as some of the
consequences of that relation.

####  2.2.1 RNN formalism

Figure 2.9:  Standard RNN architecture (top) and Game of Life seen as a RNN
with no inputs and outputs (bottom). For the CA, the “hidden” state $h_{t}$ is
the current state of the grid at timestep $t$. The operator $\bm{\Phi}$ is the
CA update rule which is equivalent to a CNN (see Section 2.2.2). This
illustration is based on Recurrent neural network unfold by fdeloche, licensed
under CC BY 4.0. Figure 2.10: The CA update rule is local and can be
represented by a set of CNNs: linear local uniform transformations followed by
the application of a non-linear function.

We write the definition of a CA with a formalism and notation inspired by
RNNs. This parallel is illustrated in Figures 2.9 and 2.10. The state of the
grid at time $t$ is denoted $h_{t}$ and corresponds to the hidden state in a
RNN. In the case of classical CAs, it is a 1 or 2D vector of discrete values
(see Section 2.1.1), but [210] and other CAs extensions use continuous values,
much like usual RNNs.

The mapping $\Phi$ operates only on the hidden state. Because it is local, it
can be shown to be equivalent to a convolutional layer, as explained below in
Section 2.2.2. The inputs and outputs $(\mathbf{x},\mathbf{o})$ in Figure 2.9
are not included in the classical definition of CAs, but are an easy-to-
implement extension, as discussed in Section 2.2.3.

####  2.2.2 Transition rule as a set of convolutions

Each cell $c_{i}$ from the CA definition can be in one of the $k$ states. We
represent the cells as vectors of size $k$, where $k$ is the number of states,
with only zeros excepted for a one in the $k$-th position, which can be
interpreted as a one-hot encoding of the cell state. A neighborhood of size
$3$ in a 1D CA can be represented as a $3\times k$ vector
$\mathbf{u}_{i}=[u_{i-1},u_{i},u_{i+1}]$. Each $u_{i}$ is a vector of size $k$
with a $1$ in position $s_{i}$. This is illustrated in the 1D (resp. 2D) case
on the left (resp. right) of Figure 2.11. For a CA with only two states, it is
redundant to have a $3\times 2$ vector, but the “one-hot” encoding becomes
useful when working with more states.

Figure 2.11: A CA neighborhood vector representation example with 2 states. A
$3\times 3$ square of cells with two states can be represented by a $3\times
3\times 2$ tensor. Left: 1D 3-neighbors representation. Right: 2D $3\times 3$
neighbors representation. The last dimension of the vector encodes a “one-hot”
representation of the state of the cell.

With this representation, we can express the transition rule $\Phi$ as a
simple convolutional neural network. This network would be made up of two
layers, which are shown in Figure 2.12 for the 2D case. We describe a simple
construction of a CNN representing any binary CA rule below:

(a) A representation of any binary 2D CA rule operating on $3\times 3$
neighborhoods as a 2-layer CNN. There are 512 filters receptive to each
$3\times 3$ neighborhood states in the first layer. The second layer
determines the output value for each neighborhood state.

(b) A representation of any binary 1D CA rule operating on neighborhoods of
size 3 as a 2-layer CNN. There are 8 filters of size $3\times 3$ in the first
convolutional layer, and 8 filters of size $1\times 1$ in the second one.

Figure 2.12: Two examples of CA rules represented as a simple CNN. Padding
ensures the grid obtained after the CNN step is of the same size as the
original grid.

###### The first convolutional layer.

It is receptive to each possible neighborhood configuration. In the 1D case
with neighborhood size 3, this is all eight configurations
$000,001,010,\ldots,111$. For a radius $r$ in 1D, this layer is composed of
$k^{2r+1}$ filters of dimension $k\times(2r+1)$ with only ones and zeros,
which are the mirror of a possible configuration of size $(2r+1)$ of the
neighborhood.

The product of each filter with an input neighborhood in the grid will be an
integer between $0$ and $2r+1$. Applying a ReLU nonlinearity preceded by a
constant vector of value $2r$ as bias, we obtain the input to the second
layer, a vector of size $k^{2r+1}$ for each cell containing all zeros except
for one corresponding to the detected neighborhood. This vector plays the role
of an indicator of the current input configuration.

###### A second convolutional layer.

It has $k^{2r+1}$ filters of size $1$ that are $0$s or $1$s depending on the
desired output value of that transition. When applied to the indicator vector
above, the output obtained will be the output value of the rule corresponding
to the detected neighborhood state.

With some circular padding that wraps around the edges of the grid or applies
constant values outside of the main grid, the size of the output is the same
as the input. This means that the CNN step can be applied multiple times,
simulating a single CA step every time.

####  2.2.3 Adding inputs and outputs

Figure 2.9 shows the locations where inputs and outputs can be incorporated
into the Game of Life or any other CA. We provide a variety of examples of how
input and output can be integrated and how they can interact with the rule of
the CA.

##### Inputs

There are many ways to add inputs to the recurrent CNN model presented above.
We divide our proposed methods into two classes: inputs that directly modify
the hidden state during the CA evolution and inputs that augment the hidden
state without changing it directly and affect the rule.

###### Hidden-state augmentation and rule modulation.

Inputs are usually added to the hidden state just before the application of
the non-linearity in standard RNNs.

In the case of cellular automata, it can also be done in the following ways:

Figure 2.13:  Inputs $x$ and outputs $y$ can be directly encoded within the
hidden state. $U$ and $V$ are the operators mapping $x$ to a hidden state
tensor and decoding a hidden state tensor to output $y$.

  * •

Vector state. A straightforward way to add inputs to a CA is to consider the
grid as having an additional (possibly read-only) dimension. For example, a 1D
automaton of size $N$ would be represented by a vector of dimension $N\times
2$ where the first vector of size $N$ is the state of the grid and the other
is the input. The update rule would be changed to take into account this new
component. One can see this model as using multiple CA rules at the same time,
with the input state conditioning the rule chosen for a given update step.

  * •

Variable update rule. Inputs can also influence a CA’s evolution by changing
the update rule. With this configuration, the update rule $\Phi$ is now a
function of the input $x$. We now have $\Phi_{x}=G(x)$, where

$G:\mathcal{X}\rightarrow\left({\\{1,\ldots,k\\}}^{2r+1}\to\\{1,\ldots,k\\}\right),$

and $\mathcal{X}$ is the input space.

A similar approach was used in [2]. It showed that conditioning a CA update
rule on another CA’s evolution could enable a higher diversity of behavior.

  * •

Concatenation. One way to incorporate input is by concatenating it with the
hidden state, such as at the boundaries of the grid, before applying the
update rule. This creates a fixed read-only memory space, as shown in Figure
2.14. However, a potential drawback of this method is that information must
propagate through the grid in order to be processed in locations far from the
read-only memory’s position.

This approach is more reminiscent of computer architecture, where designated
areas are reserved for specific data functions.

Figure 2.14:  Input $x_{t}$ is projected and concatenated to hidden state
$h_{t}$, affecting the boundary conditions of the CA. For the CA, this vector
is just like another part of the hidden state except that it is not writable

###### Hidden-state manipulation.

Another approach is to directly modify the hidden state to “communicate”
information to the system. These methods are used in [210, 249] to make
interactive demos and allow users to directly modify that hidden state. A user
can interact with the system by drawing with its mouse. This sets parts of the
internal state to a fixed cell state.

  * •

Masking. Input data can serve as a mask on top of the current grid state,
forcing some cells into states that depend on the input values. If we view the
state activations in the CA as some neural pattern, this approach can be seen
as a form of _neuromodulation_ , which has previously been used in machine
learning [290, 136, 18].

A mask can be constructed from an input vector $x$ by linearly transforming
$x$ and applying an activation function (e.g., step function). It controls
which channels are activated and where information can flow or not. This kind
of mask can be applied with element-wise multiplication or addition but also
more elaborate operations. It is illustrated in Figure 2.15.

Figure 2.15:  Input is converted into a binary mask for the hidden state. The
mask is applied through element-wise multiplication here.

##### Outputs

Similarly, inputs can be extracted from the hidden state in several different
ways. One might read outputs from the boundaries of the grid, from a
transformation of the grid using a neural network, etc. The output could also
be stored within an additional dimension of the “extended” grid state
presented above.

##### Cellular automata and computations

From a computational point of view, the hidden state can be seen as a working
tape on which some kind of _parallel Turing machine_ (the cellular automaton)
performs computations. In this framework, the input is encoded as the initial
state of the tape and decoded from the last state of the tape (as illustrated
in Figure 2.13). The recurrent convolutional neural network (RCNN), or CA,
then plays the role of a fixed computer program that is executed. This is the
setting adopted in previous work on constructing computations with cellular
automata: a task is chosen, and rules that can execute that task on
input/output pairs are searched [205].

Another interesting point of view can be taken when we consider the hidden
state (or tape) as encoding both some data and a computer program, as is the
case with a Turing machine. We can then expect a CA (or RNN) to not only
compute the result of a particular function but to be equivalent to a general-
purpose computer capable of computing the result of any chosen algorithm
without any need for optimization. Making a universal CA compute some program
amounts to encoding the program in the right language and communicating it by
embedding it within the hidden state. In practice, figuring out the right
encoding is often the biggest challenge. This is also the reason that the few
Turing complete CAs are not so useful in practice since we do not know of any
efficient encoding for programming them.

####  2.2.4 Consequences

Viewing cellular automata as recurrent convolutional neural networks, as
described above, has several interesting consequences, of which we list a few
here.

##### Turing-completeness of the system

Because we can simulate rule 110 ECA in the above RCNN system, it follows from
the Turing completeness of this CA rule that the RCNN is Turing complete. This
is an interesting result, although not very significant since RNNs have
already been proven to be Turing complete [279], with very few practical
implications. Our model is relatively far from a real-world CNN with a fixed
number of layers independent from one another — compared to a variable number
of steps and shared layers for the automaton-RCNN. Thus, this property does
not seem to bear any consequence on CNNs.

##### Differentiable cellular automata

Each step of the computations involved in computing a step of a cellular
automaton represented as a RCNN is differentiable. Therefore, we can
theoretically couple this framework with backpropagation to create _learnable_
cellular automata that can adapt their rules to minimize a target loss
function.

This is the direction taken by [210]. The authors use supervised learning on a
CA and train it to obtain a stable self-repairing target shape. However,
because supervised CA can only do as much as they have been trained to do, it
may defeat the purpose of working with a model capable of spontaneous complex
emergent behavior. An open-ended complexity increase could very unlikely be
achieved through pure supervision.

[96] takes the reverse approach and tries to train RCNNs to simulate a fixed
CA rule, using the statistics of that training process as a way to help
understand the structure of the CA rule space.

####  2.2.5 Beyond the naive rule representation

The representation of CA rules that we built in Section 2.2.2 is a one-to-one
mapping. Each rule has its RCNN counterpart, and vice versa. However, there
are several ways to make that representation of CA rules more efficient, using
a neural network with fewer parameters. For example, we can make the first
layer of filters receptive to both a given configuration and its inverse
(e.g., $(1,0,1)$ and $(0,1,0)$ in an elementary cellular automaton) by using
negative values in the filter (use a filter $(1,-1,1)$ instead of $(1,0,1)$
and $(0,1,0)$ separately).

For example, the rule of the game of life does not need more than two
convolutional filters on the first layer to be represented by a CNN because it
is totalistic. The new state of a cell depends only on its number of neighbors
in the alive state and the current state of the cell.

###  2.3 Reservoir computing

RC is a computational framework that aims to exploit the states of a complex
dynamical system to perform some target task [300]. It relies on a _reservoir_
of computations, that is, a dynamical system performing some computations on
its internal state. An input signal is fed into this reservoir that behaves as
a black box from the point of view of the algorithm. Input values can be
sequential or nonsequential. They are projected and combined with the
dynamical system using a suitable mechanism. This projection can be learned,
set randomly, or chosen. The internal state of the dynamical system evolves
according to its update rule, which is defined by the chosen system. Finally,
a decoder model (usually a linear regression) is trained in a supervised
manner to extract necessary information from the internal state of the
dynamical systems to predict the right output. A general diagram describing
this process is shown in figure 2.16.

Figure 2.16: Diagram of the general functioning of a reservoir computing (RC)
system. Input values are projected in the state or evolution function of a
dynamical system which is run according to its internal rule. Output values
are decoded from the internal state of the dynamical systems with a trainable
layer.

Some early known formulations of the RC idea were done by [153] and [269, 270,
271]. In another early work, [36] used a random spiking neural network with
excitatory and inhibitory elements. The probabilities of neuron connection was
inspired by the real rat brain data [198]. The authors observed an interval-
sensitive response of these neurons when subjected to pulses spaced by varying
time intervals. This indicates an ability to encode temporal information. To
measure this phenomenon, they trained an output linear layer to recognize
specific patterns in the activation of the last layer of neurons. This idea of
using a randomly initialized RNN with fixed weights and training a simple
linear layer to decode outputs was reinvented and popularized later under the
names “Echo-state networks” [139] and “Liquid state machines” [190].

Another advantage of reservoir computing is that reservoirs can be implemented
using a variety of physical systems, substrates, and devices. These types of
reservoir are sometimes called “exotic” [187] in contrast to RNN-based
reservoirs. Physical RC is a promising area of research that may help us
develop cheap and efficient machine-learning hardware and can inform us about
the nature and behavior of the underlying physical systems. [300] identifies
four characteristics that make a reservoir suitable for solving a
computational task.

  1. 1.

The inputs must be mapped to a high-dimensional space, which corresponds to
the internal state of the reservoir. This high-dimensionality ensures that the
inputs are separated with high probability.

  2. 2.

The reservoir should be non-linear. This will allow inputs that are not
linearly separable to be separated as they are projected within the reservoir.

  3. 3.

The reservoir should have the echo-state property [139, 344], or fading memory
[33, 190, 191]. This property relates the asymptotic properties of the excited
reservoir dynamics to the driving signal. A reservoir with the echo-state
property will asymptotically forget all input values. This makes some
reservoirs unable to solve tasks where unbounded memory is possibly required,
such as context-free grammar parsing [268]. Later, reservoir models that
address this issue were developed [239].

  4. 4.

A reservoir should separate responses from different signals into different
parts of the space while being insensitive to small perturbations of the
input. For a given system, this trade-off is often obtained at the transition
between chaotic and non-chaotic regimes [25, 175].

We list common types of RC that are based on various families of reservoirs
below:

Dynamical systems.

This refers to a broad category of RC models based on other dynamical systems
than the random RNNs. This includes reservoir computing with Cellular
automata, which we give more detail about in section 2.3.3.

Electronic RC.

These models are implemented on electronic circuits, such as artificial neural
networks implemented on physical circuits or other neuromorphic circuits. For
example, RC models can be build on FPGAs [7, 317, 4, 9] or memristive circuits
[342, 201, 74].

Mechanical RC.

Soft mechanical bodies have complex nonlinear dynamics that can be used as a
reservoir to build a RC model [243]. For example, a reservoir using a mass-
spring network was proposed by [119].

Biological RC.

There have been multiple hypotheses on whether the parts of the brain behave
like a RC system [341]. The goal of this area of research is to study the RC-
like properties of biological systems rather than build reservoir computers.
For example, a RC model was proposed to understand the mechanism of context-
dependent eye movement [73, 72].

Photonic RC.

The principle of photonic RC is to use optical reservoirs to generate the
computations. A first example using semiconductor optical amplifiers (SOAs)
was proposed by Vandoorne and colleague [312, 311] and subsequently built
[313]. The photonic implementation of reservoir computing is based on the idea
that photonic accelerators [155] can realize fast information processing with
low learning costs [237, 196, 299, 8]. Some of the implementations use the
scattering of light in complex media [76, 248].

Spintronics RC.

Some RC works used nanoscale electronics involving the charge and spin of
electrons called _spintronics_ [329]. Spintronics has been used in multiple
ways to build RC models, using spin torque oscillators (STO) [306, 326], or
spin waves [219] for example.

####  2.3.1 Reservoir computing applications

RC has had successful applications in various fields. It has been applied for
pattern classification; in audio with spoken digit recognition [316] and
waveform classification [237]; in computer vision with written digits
recognition [142], and human motion classification [285, 8]. Another popular
application of RC is time-series forecasting [139, 140, 339]. RC has also been
used in reinforcement learning to control agents in artificial environments
[148] or learn radio spectrum access [45].

####  2.3.2 Echo-state network

The echo-state network (ESN) (and simultaneously developed model _Liquid state
machine_ (LSM)) is the most well-known implementation of the RC principle
[300]. The main idea behind this model is to drive a RNN with some input
signal, which will excite the neurons within the reservoir and induce several
nonlinear response signals. This is combined with a trainable linear
regression to extract a desired output from a combination of these response
signals. The ESN model is illustrated in Figure 2.17.

In practice, the input projection is often fixed, but it can also be
trainable. The output can also be fed back to the reservoir as an input, and
the structure of the RNN reservoir can be adapted to various applications.

Figure 2.17: Diagram of an echo-state network. The RNN is reprensented
“flattened” in time. The circles represent the units of the hidden state of
the RNN. An arrow between unit $i$ and $j$ corresponds to a non-zero entry in
the matrix, ${\bm{W}}_{h,ij}\neq 0$. Non-linear operations are not
represented.

We define an input sequence as $({\bm{x}}_{t})_{t=1}^{T}\in\mathbb{R}^{n\times
T}$, where $n$ is the input dimension and $T$ is the number of input time
steps. The initial state of the reservoir at $t=0$ is ${\bm{r}}_{0}$. The
echo-state network is based on the following update equation:

${\bm{r}}_{t+1}=(1-\beta){\bm{r}}_{t}+\beta\tanh({\bm{W}}_{h}\>{\bm{r}}_{t}+{\bm{W}}_{\text{in}}\>{\bm{x}}_{t+1}),$
(2.8)

where ${\bm{r}}_{t}$ is the $K$-dimensional state vector corresponding to
hidden neurons — at time $t$, $\beta$ is the leak rate,
${\bm{W}}_{h}\in\mathbb{R}^{K\times K}$ is a sparsely connected random hidden
layer matrix and ${\bm{W}}_{\text{in}}\in\mathbb{R}^{L\times K}$ is the input
projection matrix. The matrices ${\bm{W}}_{h}$ and ${\bm{W}}_{\text{in}}$ have
random values.

For the random initialization of ${\bm{W}}_{h}$ and ${\bm{W}}_{\text{in}}$,
[141] recommends: ${\bm{W}}_{h}$ should have an average of 10 non-zeros
entries per row, all sampled uniformly in $[-1,1]$. The matrix is then scaled
to achieve a set spectral radius $\rho$, which is optimized for each
experiment in [141]. ${\bm{W}}_{\text{in}}$ has its entries uniformly sampled
in $[-1,1]$. The columns of the matrix are then individually scaled with
factors $\sigma_{1},\ldots,\sigma_{L}$ specific to each experiment. In this
formulation, there are multiple parameters to optimize:

  * •

The size of the reservoir $K$

  * •

The spectral radius of ${\bm{W}}_{h}$, $\rho$

  * •

The input weight scaling parameters $\sigma_{1},\ldots,\sigma_{L}$

  * •

The leaking rate $\beta$.

[141] explores three optimization schemes for these parameters:

Blind.

The input weight scaling parameters are set to a single value $\sigma$. The
parameters $K$, $\rho$, $\sigma$, and $\beta$ are optimized. This corresponds
to a search space of dimension 4.

Basic.

Each $\sigma_{i}$ is optimized individually or in groups. The other parameters
are also optimized.

Smart.

All parameters are optimized as in the Basic scheme, and the weights of
${\bm{W}}_{h}$ are also designed specifically for the target task.

The $L$-dimensional outputs are computed at times $t>0$ as

$\tilde{{\bm{x}}}_{t+1}=D({\bm{r}}_{t}),$ (2.9)

where $D:\mathbb{R}^{K}\rightarrow\mathbb{R}^{L}$ is a (trained) decoding
function. For echo state networks, the decoder is often a linear
transformation $D({\bm{r}}_{t})={\bm{W}}_{\text{out}}{\bm{r}}_{t}$ where
${\bm{W}}_{\text{out}}$ is a matrix of dimensions $K\times L$. In our
experiments in Chapter 6, we set $\beta=0$, which was empirically observed to
yield the best results on our tasks. Parameter $\beta$, as well as the
randomly sampled weight matrix, are sometimes adjusted for each task [141]. We
only use default values to obtain a task-independent setup with the least
possible assumptions and to make the methods comparable.

####  2.3.3 Reservoir cellular automata

Cellular automata can also be used as a dynamical system in reservoir
computing. Yilmaz originally proposed this in 2014 and later was named ReCA
(Reservoir Cellular Automata) [345, 195].

Several implementations of ReCA systems have been proposed and evaluated on
various tasks [345, 225, 226, 224, 194, 156, 13, 199, 209]. In this section,
we lay out a general description of reservoir computing with cellular automata
based on these previous works and present our proposed extensions. We apply
reservoir cellular automata to language-like tasks in Chapter 6.

###### Encoding.

Input data is assumed to be categorical and sequential,

$X=[X_{1},\ldots,X_{t},\ldots],\quad t\in\mathbb{N},\quad\forall t\
X_{t}\in\mathcal{X}\subset\mathbb{N}.$ (2.10)

A CA is a discrete system not specifically designed to handle input. The
purpose of the encoding step in ReCA is to convert the input data points to
vectors that can be embedded in the state space of the cellular automaton.
Such encoding should translate — or embed — the input space $\mathcal{X}$ into
a new one that can be combined with the current state of the cellular
automaton. The goal is to make a cellular automaton “react” to its input and
leverage the resulting computation to solve a problem.

###### Input projection.

First, each categorical input vector is one-hot encoded into a vector of size
$L_{in}$, where $L_{in}=|\mathcal{X}|$ is the number of input categories. We
have

$\forall t,\quad{\bm{x}}_{t}\in{\\{0,1\\}}^{L_{in}},$ (2.11)

with $\sum_{i=1}^{L_{in}}{({\bm{x}}_{t})}_{i}=1$.

Next, the vectors ${\bm{x}}_{t}$ are projected onto the vectors
${\bm{p}}_{t}=P({\bm{x}}_{t})\in\mathcal{P}={\\{0,1\\}}^{L_{d}}$ of fixed size
$L_{d}$, where $L_{d}$ is the size of the internal state of CA. Usually, we
have $L_{d}>L_{in}$, which means that we embed the input in a space of higher
dimension. In our work, we compute this projection in one of three ways:

One-to-one

each input bit is assigned to a single index in ${\bm{p}}$. This is the
projection function first proposed in [345].

###### Building the reservoir

The final state of the reservoir ${\bm{r}}_{t+1}$ is obtained by stacking $I$
consecutive CA states obtained from a combination of inputs of a single state
${\bm{s}}^{\prime}$ by applying $\Phi$ again. The parameter $R$ can be
understood as a space redundancy parameter, while $I$ is a time redundancy
parameter. If the size of the state is $n$, the resulting reservoir vector
${\bm{r}}$ has dimension $K=I\times n$, where $I$ is defined above. Similar to
the ESN, the $L$-dimensional output tokens are calculated at times $t>0$ as

$\displaystyle\tilde{{\bm{x}}}_{t+1}$ $\displaystyle=D({\bm{r}}_{t}),$ (2.12)

where $D:\mathbb{R}^{K}\rightarrow\mathbb{R}^{L}$ is the (trained) decoding
function. Here, we predict $\tilde{{\bm{x}}}_{t+1}$, which corresponds to a
language-modeling-like task of predicting the next input. It would also be
possible to predict another sequence $({\bm{y}}_{t})_{t}$. Usually a linear
decoding function is used such that
$D({\bm{r}}_{t})={\bm{W}}_{\text{out}}{\bm{r}}_{t}$. The complete pipeline of
a RC model with CA is summarized in Figure 2.18.

Figure 2.18: Illustration of the 1D ReCA model with the XOR-based input and
state combination method. The highlighted boxes correspond to $I$ stacked CA
states that make up a single reservoir state.

##  Chapter 3 Literature Review

In the previous chapter, we gave a detailed definition of cellular automata,
neural networks, and reservoir computing, and described the interplay between
them. The current chapter aims to provide an overview of several fields
associated with learning and complex systems that have informed and influenced
our work in this thesis. We begin by reviewing related work on complexity
measures for dynamical and complex systems (Section 3.1). We also review works
on defining and understanding emergence (Section 3.2), evolutionary methods
for searching solutions in complex spaces (Section 3.3), methods for
constructing open-ended evolving systems (Section 3.4), and methods for
extracting and using the computations happening within complex systems
(Section 3.5).

###  3.1 Measuring complexity

3.2(c)3.2(a)3.2(b)ComplexityRandomness

Figure 3.1: _Ideal_ “complexity” curve as a function of the “randomness” of a
system. The three CAs from figure 3.2 are displayed at their approximate
expected location on that curve. This curve is just for illustrative purposes
and does not correspond to any true function linking randomness and
complexity.

Measuring the complexity of a system is a fundamentally difficult task. Many
complex systems exhibit what Peter Grassberger calls _self-generated
complexity_ [104]. This means that the formulation of the system is
translationally invariant and the observed structure arises from a spontaneous
breakdown of translational invariance. For example, CA has a uniform update
rule, but the complexity arises locally in some of them. Unfortunately, there
is no universally accepted and formalized notion of “complexity”, although
most intuitively agree that it exists. For example, Figure 3.2 shows three
examples of behaviors generated by 1D ECAs. Most people would consider the
leftmost figure 3.2(a) to be not complex. However, depending on one’s
definition of complexity, the last picture could be labeled as complex.

(a)

(b)

(c)

Figure 3.2: Three 1D Cellular automata with qualitatively different behavior.
The left (3.2(a)) and right (3.2(c)) CAs are usually not defined as “complex”,
whereas the middle CA (3.2(b)) appears to be more complex than the others. The
Figures show CAs space-time diagrams. Each row represents the state of the CA
at a single time step, with the time increasing from top to bottom.

No clear observable quantities and protocols have been proposed that would
give a quantitative notion of complexity. [105] argued that no single quantity
is sufficient to measure complexity since it depends on exactly how the
meaning is assigned to this term. Even when some meaning has been fixed by the
definition of an observable quantity, the statistics of the measurement of
this observable are also crucial to its interpretation [109].

Despite these drawbacks, we seek a measure of complexity that matches
intuition as well as possible. Such a measure would assign low complexity to
both simple objects and random objects and high complexity to objects in
between. For illustration, we place the three ECAs from Figure 3.2 on this
ideal complexity curve, shown in Figure 3.1. For example, in Chapter 4, we
develop a complexity metric that matches the human intuition of complexity on
a dataset of cellular automata.

One of the most widely known concepts of the complexity of symbol sequences,
“algorithmic complexity,” should also be called a measure of information. This
is the position held by one of its co-creators [43]. In the literature,
information measures are often used as complexity metrics. These quantities
are better measures of “randomness” than complexity, but they are nonetheless
important for the study of complex systems. In this section, we list several
complexity measures, including information measures that have influenced our
research.

####  3.1.1 Information content

For an event $E$ with probability $P$, the information content of this event
is defined as the negative logarithm of its probability, that is,

$I(E):=-\log(P).$ (3.1)

This metric quantifies how unlikely an event is and depends on how the
probability $P$ was estimated in practice. This notion is at the foundation of
information theory. The information content of a finite set of $N$ events is
maximal when all events are equally probable, that is $I(E)=\log(N)$.

####  3.1.2 Shannon Entropy

Shannon entropy is defined as the expected information content of the input
[277]. We have

$\displaystyle H(X):=\mathbb{E}[-\log(P(x))]_{x\in X}.$

This measure is a lower bound on the number of bits that the input could be
compressed to.

In the case of a 1D ECA, the Shannon entropy could be computed cell-wise over
the time distribution of the states, producing an entropy per cell score that
can be averaged over an entire automaton. This measure is, for example, one of
the measures used by Wolfram in [330] and by Langton in [172] to study how the
parameter $\lambda$ affects the behavior of the automaton. There are several
ways to compute it when dealing with a CA, depending on which part of the CA
is considered as the main random variable. If the CA is finite, the state at
timestep $t$ can be seen as a random variable that can take one of $2^{N}$
possible values (with $N$ the width of the automaton state). In that case, the
probability of a state can easily be estimated by counting its number of
occurrences during evolution. For too large state spaces, this becomes
challenging, as it is very unlikely that a given state will be seen again.

####  3.1.3 Rényi Entropy

The Rényi entropy is a generalization of Shannon entropy that gives different
weights to events of various probabilities [252]. It is formally defined for
an $\alpha\geq 0,\alpha\neq 1$ and a random variable $X$ with possible
outcomes $0,1,...,n$ as

$\displaystyle
H_{\alpha}(X)=\frac{1}{1-\alpha}\log\left(\sum_{i=0}^{n}p_{i}^{\alpha}\right).$

In the limit $\alpha\rightarrow 1$ it is equal to the Shannon entropy, where
the probabilities of each event are equally important.
$\alpha\rightarrow\infty$ yields the Min-entropy, and we have
$H_{\infty}(X)=\min_{i}(\log(p_{i}))$. With $\alpha\rightarrow 0$ Rényi
entropy is the same as Max-entropy, or topological entropy. Rényi entropy was
used by [330] and [184] to estimate the complexity in infinite CAs.

####  3.1.4 Mutual information

The mutual information is a measure of the dependence between two variables.
Two independent variables will have mutual information of zero. If the two are
strongly dependent, for example, if one is a function of another, the mutual
information between them will be larger.

[42] proposes to split a system into fixed blocks and calculate mutual
information among its components. He uses the maximum value of the mutual
information in all possible partitions to define "life" in a mathematical way.
[278] and [104] also use the mutual information measure between two semi-
infinite blocks in a sequence to define complexity. Mutual information has
also been used to study the complexity of CAs as the parameter $\lambda$ is
changed (for details on $\lambda$ in the context of CA, see section 2.1.4)
[111, 182].

####  3.1.5 Computational complexity

Algorithms can be described by their space and time complexity, which
respectively correspond to the amount of memory storage and CPU time necessary
to run them [307, 235, 127]. A problem that depend on a parameter $N$ will be
said to be NP-hard if the time needed to find a solution to them increases
exponentially with the parameter $N$. NP-hard problems can be said to be
complex as they require a supposedly irreducible amount of computation to
compute their output. In practice, this description only applies to
computations that were generated by a hand-designed algorithm and not the kind
of computations self-generated by a complex system that we are interested in.
For example, the computations generated by one CA cannot be said to be
computationally more complex than those of another CA because the algorithm
that implements them is fundamentally the same and computationally simple.

####  3.1.6 Solomonoff–Kolmogorov-Chaitin complexity (algorithmic complexity)

Introduced by Solomonoff [289], Kolmogorov [159] and Chaitin [41, 40, 43],
this complexity measure is defined for a string $s$ of characters and a
universal description language (e.g., a programming language) as the length of
the shortest program that can generate the string $s$.

This number $K(s)$ is called the minimum description length of $s$. We note
that Chaitin prefers to call his field "algorithmic information theory." His
position is that "algorithmic complexity" is a measure of randomness rather
than a measure of complexity [43].

From the invariance theorem [287, 288, 159, 41], the difference in algorithmic
complexity of the same string $s$ in two different description languages is
bounded, although this bound might be very large in practice.

The algorithmic complexity is uncomputable [287, 159], and there exists
strings of arbitrarily large complexity, which makes it hopeless to use this
exact measure in practice. It can be approximated from above, but no accuracy
guarantee can be given, and the runtime of the approximators can grow
arbitrarily large. Moreover, algorithmic complexity tells us how much
information is required to encode a number, but does not tell us how difficult
it is to recreate the number from that code [94].

A range of resource-bounded approximations of algorithmic complexity were
developed to obtain computable complexity measures [63, 64, 83, 158, 266]. One
rather straightforward way of approaching the algorithmic complexity of an
arbitrary string is to use a compression algorithm and use the length of the
decompression program plus the length of the compressed string as an upper
bound to the algorithmic complexity. This is similar to the optimal symbol
compression ratio (OSCR) algorithm proposed by [82]. [347] used the
compression-based method to classify 1D ECA. This method, which often uses the
popular LZ algorithm, can be seen as an independent complexity measure, also
closely related to Lempel-Ziv complexity, described in more detail in the next
section 3.1.7.

However, it is worth noting that when a complex system is described by an
algorithm (such as for a CA), the algorithmic complexity is also easily upper
bounded by a constant value entirely defined by the algorithm that simulated
the complex system. For example, for a CA, the algorithmic complexity is lower
than the size of the rule table of the automaton, its characteristics (size,
boundary conditions, etc.), its initial state, and the number of simulation
steps. This approximation does not inform us about the difference in
complexity between the two CAs.

####  3.1.7 Lempel-Ziv complexity

The Lempel-Ziv complexity, as defined in [179] is the number of steps in the
LZ algorithm, directly related to the number of repeated substrings in the
input string. The main idea of this algorithm is to scan the input string
while trying to find some repetition of the previous input in the incoming
data. This builds over time a set of basic components called the exhaustive
history of the string, from which the complete string can be constructed. The
number of components in that set is the Lempel-Ziv complexity of that string.

The compressed length method for measuring complexity uses a compression
algorithm to reduce the size of the input. An input with regularities and
repetitive patterns will produce a small output, whereas a completely random
input will be irreducible to a simpler, shorter string.

####  3.1.8 Logical Depth

Bennett’s logical depth is a measure of complexity based on the algorithmic
complexity [22, 23]. The main difference is that it takes into account the
computation time (or number of steps) along with the length of the program
used to generate the sequence. It is a combination of algorithmic complexity
and computational complexity. For a universal computer $U$, the logical depth
of a string $x$ at a significance level $s$ is defined as

$\min\\{T(p):(|p|-|p^{*}|<s)\wedge(U(p)=x)\\},$ (3.2)

where $T$ is the number of steps that the universal computer runs the program
$p$ for. This quantity corresponds to the least time required to compute the
string $x$ by a $s$-incompressible program, that is a program $p$ whose length
is within $s$ symbols from the optimal program $p^{*}$ of the algorithmic
complexity metric.

[10] considered logical depth to be one instance of a more general concept:
_computational depth_ ; and proposed several other variants.

####  3.1.9 Thermodynamic Depth

The thermodynamic depth, developed by [185] is another measure of complexity
based on the intuitive notion that complex systems lie somewhere in the
continuum between order and chaos [43, 39, 69]. Similar to computational
complexity and logical depth, this metric is designed to be a measure of how
the system came to be in its final state. The complexity corresponds to how
difficult it is to put the system together in that state.

By the definition of thermodynamic depth, the average complexity of a state
must be proportional to the Shannon entropy [277] of the set of trajectories
that the experiment determines can lead to that state. If we write $p_{i}$ the
probability of reaching the target state with the $i$-th possible trajectory,
we have

$S=-\left(\sum_{i}p_{i}\log p_{i}\right).$ (3.3)

The measure of complexity of a macroscopic state $s$ of a system that has
reached that state by the i-th possible trajectory is $-k(\log p_{i})$, where
$p_{i}$ is the probability that the system has reached $s$ by the i-th
trajectory, and $k$ is an arbitrary positive constant. The thermodynamic depth
of the state $s$ is defined as

$\mathcal{D}(s)=-k(\log p_{i}).$ (3.4)

The quantity $\mathcal{D}$ can be thought of as the amount of information
required to specify the trajectory that the system has followed to its present
state. The thermodynamic depth of the whole system is then

$\mathcal{D}=\sum_{s}\mathbb{P}(s)D(s),$ (3.5)

where $\mathbb{P}(s)$ is the probability that the system followed the
trajectory $s$.

[59] argued that the thermodynamic depth is a fundamentally flawed structural
complexity measure because it relies on a set of chosen macroscopic states for
the system, which are difficult to choose and need to be defined separately
for each system. [185] does not mention how these states are supposed to be
chosen, nor do any follow-up work, making this complexity metric difficult to
use in practice.

####  3.1.10 Epsilon-machines

The $\epsilon$-machine is an approach to complexity that seeks to construct a
metric more suitable for physical systems that also addresses some issues of
other existing complexity metrics [57]. It is the result of the field of
computational mechanics, an extension of statistical mechanics that describes
not only the statistical properties of a system but also how it stores
information and how it computes [60, 56, 84, 57]. Computational mechanics
algorithms take as input the time series being analyzed and output a minimal,
optimized model that can reproduce a time series that is statistically
equivalent to the input time series. The size of the model produces a metric
known as statistical complexity. The models are known as $\epsilon$-machines.
Three optimality theorems say that $\epsilon$-machines capture all the
properties of a process [60, 59, 274]: prediction: the $\epsilon$-machine is
its optimal predictor; minimality: compared to all other optimal predictors,
the $\epsilon$-machine of a process is its minimal representation; uniqueness:
any minimal optimal predictor is equivalent to the $\epsilon$-machine.

This model has many attractive properties and was successfully applied to
study the symbolic dynamics of chaotic systems [56], molecular dynamics [259],
single-molecule microscopy [151], and the spatiotemporal complexity of CAs
[58, 115, 276]. The main drawback is the construction of the
$\epsilon$-machine itself, for which there is no general-purpose approach.

####  3.1.11 Sophistication

Intuitively, _sophistication_ is the complexity in a set of strings of which
the string is a “typical” member. [213] defines sophistication based on the
original definition of [160, 161]. It measures the amount of structural
information contained in a string. It also uses a follow-up result by [320]
that shows that Koppel’s definition is equivalent to measuring the complexity
of a good model for a string up to low order terms. The definition uses an
intermediate quantity called _discrepancy_ that measures how far a set $S$ is
from being a good model of a string $x$.

Formally, the discrepancy $\Delta$ is defined for a string $x$ and a set $S$
that contains $x$ as

$\Delta(x|S):=\log|S|-K(x)+K(S),$ (3.6)

where $K$ is the Solomonoff–Kolmogorov-Chaitin complexity function.

The sophistication of $x$ is defined as the complexity of the simplest model
of $x$ with a limited discrepancy:

$\text{soph}_{c}(x):=\min_{S}\left\\{K(S):\Delta(x|S)\leq c\right\\}$ (3.7)

where the significance level $c$ tells us how much discrepancy the set $S$ is
allowed to have.

Koppel’s definition of sophistication, Definition 3.1, may not be stable.
Small changes in c could cause large changes in $\text{soph}_{c}(x)$. For this
reason, [11] introduces a new notion of _coarse sophistication_ that
incorporates the "constant" $c$ as a penalty in the formula to obtain a more
robust measure. In the formalism of [213] the definition is

$\text{csoph}(x)=\min_{S}\left\\{K(S)+\Delta(x|S)\right\\}$ (3.8)

which is also equivalent to

$\text{csoph}(x)=\min_{c}\left\\{\text{soph}_{c}(x)+c\right\\}.$ (3.9)

Like algorithmic complexity, sophistication is a useful theoretical notion to
model ideas of entropy and complexity, but it cannot be directly applied in
numerical simulations and can only be approximated because it is also
uncomputable.

###  3.2 Emergence

The notion of emergence is central to the study of complex systems. It is a
broad concept that could be phrased as _the properties a composite entity
acquires that its composing parts did not possess_. Emergence is often
described as being similar to self-organization. Although these two concepts
are closely related, they are fundamentally different ideas [66]. Both
properties can exist independently within a dynamical system. Some examples of
emergent behavior include:

  * •

The spontaneous formation of clusters of randomly distributed objects - a
behavior common in ant colonies forming bridges out of individual ants or
birds flocking into “murmurations” - that naturally emerges out of a simple
set of autonomous actions having nothing to do with that clustering. This was
demonstrated by [19] in the context of exploring collective robotics). The
macroscopic behavior in each of these examples is unexpected even though the
details of the microscopic dynamics are well-defined.

  * •

The spirals of the Belousov- Zhabotinsky chemical reaction [310].

  * •

The Navier-Stokes-like macroscopic behavior of a lattice gas that consists, of
simple unit-bit billiards moving back and forth between discrete nodes along
discrete links at the microscopic scale [118].

There seems to be qualitatively different types of emergence, which [67]
describes as Discovery, Mechanistic emergence, and Reflective emergence. These
correspond to different levels, or “strengths”, of emergence, from fractal
patterns to complex social systems and ecosystems.

A subset of emergence research has focused on complex adaptive systems. In
such systems, emergence is explicitly used to refer to macro-level patterns
arising from interacting agents [126, 150, 170].

###  3.3 Evolutionary algorithms

Evolutionary algorithms are the class of algorithms inspired by natural
biological processes, in particular evolution. There are many types of
evolutionary algorithms, from genetic algorithms to quality diversity and
novelty search [177, 178]. Evolutionary algorithms are used as search methods,
in particular when the search space is hard to parametrize or very large
[245]. Evolutionary algorithms facilitate the search for complex optimization
spaces by using intermediate representations, as illustrated in Figure 3.3. CA
rules are a good example of such search spaces. The CA rule space is very
large, and it is difficult to predict how perturbations of the rule translate
to changes in the behavior of a CA. Genetic algorithms were successfully used
to evolve rules to perform complex computations [206].

Figure 3.3: Illustration of the general principle common to several
evolutionary algorithms. There are three virtual spaces: ($G$) the genotype
space where the candidate solutions are generated through some encoding. This
is the space where the search process is happening. ($P$) the phenotype space,
which corresponds to the decoded solution from a genotype $x$. It can be the
policy of an agent, the rule of a CA, etc. ($B$), the behavior space, which is
the space from which candidate solutions are evaluated. The smaller subspace
$\mathcal{G}$ is the goal space, corresponding to the set of behaviors that
would be considered successful. A small perturbation in the genotype will have
potentially large consequences on the behavior of the candidate solution. In
the case of a CA rule, the genotype could be a vector ($x$) that encodes a
rule ($p$) that will translate into the CA behavior $b$.

####  3.3.1 Genetic programming

Many of the problems that machine learning and artificial intelligence are
attempting to solve require the discovery of a computer program that produces
some desired mapping between inputs and outputs. Solving the problems
therefore amounts to searching the space of computer programs in order to find
a suitable individual with high enough fitness [168, 164, 17, 31].

In genetic programming, candidate solutions to a problem are encoded as
_chromosomes_ , which is a structured data representation that can be modified
incrementally. In practice, it is often chosen to be a string of bits. Every
generation, a population of solutions is evaluated. The best solutions are
kept and combined to form the candidates for the next generation. Random
mutations may also be applied to introduce randomness in the search.

####  3.3.2 Novelty search

The idea behind novelty search (NS) is to drive a search algorithm only by the
novelty of produced behavior [177]. The most counter-intuitive feature of this
algorithm is that the actual objective of the task is not taken into account
at all during the search process. Generated agents are evaluated solely on the
novelty of their behavior. Despite this, it appears to be at least as
efficient as other search processes that are focused on goals, such as maze
navigation and biped locomotion [177], swarm robotics [101], or neural network
design [255]. NS can lead to the discovery of innovative and creative
solutions to complex and deceptive objectives that would be difficult or
impossible to achieve using traditional optimization methods. We illustrate
this property in Figure 3.4.

The principle of guiding search by novelty alone is closely related to the
goal of this thesis, and especially with the challenge of parametrizing and
searching the space of available complex systems without using any explicit
goal function. The purpose of NS is to perform a search without a goal
function, and we draw inspiration from this algorithm throughout our work.

Figure 3.4: Illustration of the advantage of novelty search (NS) on a maze
environment with deceptive dead-ends. Dotted trajectories illustrate the
behavior of a goal-based search, which will start by minimizing the distance
to the goal. Blue trajectories are from a novelty search algorithm exploring
the space more efficiently. This type of maze environment was proposed by
[177].

This method has some limits, which are caused by a relative lack of
theoretical understanding of the effects of the parameters of NS. The choice
of behavior descriptors for determining the novelty of agents is also not
straightforward. Several empirical studies have investigated the impact of a
range of parameters on the performance of NS [100, 154], while other works
have begun to shed light on the theory [75]. In practice NS algorithms are
expected to cover the exploration space well [61, 247], in some cases
uniformly [100]. NS algorithms are related to genetic algorithms since they
maintain a population, that is, a set of individuals used to measure the
novelty of current solutions. There is also an archive of the behavior of
previous individuals to ensure that the novelty is measured against all
previously generated behaviors. There exists multiple strategies for
maintaining this archive [100]. Some use individuals whose novelty was above a
threshold when first evaluated [177], the most novel individuals of each
generation [183], random individuals from the past generations [176], or none
at all [214]. An alternative to explicitly measuring novelty in NS is _fitness
sharing_. The goal of fitness sharing is to encourage the diversity of a
population by making them share virtual “resources” [98, 125]. A particular
implementation of NS using this idea, with rewards physically spread across
the environment, was done by [120].

Typically, novelty search algorithms use one of a few types of maps from
genotypes to phenotypes, that is, a map from the space of encoded solution to
agent and policy implementation [214]. Some common ones are:

  * •

A RNN (of type [80] or [145]), for which the weights are directly searched.
For input size $n_{i}$ output size $n_{o}$, and hidden size $n_{h}$,
$n_{i}n_{h}+n_{h}n_{o}+n_{h}^{2}$ weights must be evolved.

  * •

Neuro-evolution of augmenting topology (NEAT, [297]), which is an encoding of
both neural network weights and architectures that has a built-in mechanism to
sustain diversity.

###  3.4 Open-ended evolution

The field of Artificial Life research has worked to figure out what the
fundamental conditions for the emergence of living systems are, and how to
create a process that can display analogous levels of creativity and
complexity as natural evolution [79, 171, 77, 295, 232, 292]. It builds upon
the data and understanding we collected about the process of life, but
abstracts from any specific living process and attempts to integrate various
approaches into one unified research to extract the first principles of life.
A major assumption underpinning this research is that this natural
evolutionary process can be implemented equally well in different media [68].

A system that behaves like natural evolution, producing a seemingly endless
amount of novelty and complexity starting from elementary building blocks is
called _open-ended_. The main challenge of open-ended evolution (OEE) research
is that there is no single simple test for the phenomenon, but instead
different kinds of open-ended evolution exist. Systems can exhibit more than
one kind at a time. In the report from a workshop on OEE at York [305], the
authors summarized the different types of OEE, which were further refined in a
follow-up work [232]. They are:

  1. 1.

Interesting new kinds of entities and interactions

  2. 2.

Evolution of evolvability

  3. 3.

Major transitions

  4. 4.

Semantic evolution.

The first category describes the ability of a system to construct new entities
with different properties, behaviors, or interactions with other entities. For
example, the Tierra simulation sees entities emerge that exploit the computing
power of others, acting as parasites [250]. The second type is related to how
open-ended evolution itself can be evolved through the emergence of multiple
“stepping stones” that allow individuals to use higher-level evolutionary
units or through interactions [241]. “Major transitions” refer to the
emergence of new levels of hierarchy in evolving populations. These
transitions are characterized by groups of reproducing entities that interact
tightly and form a new population of higher-level reproducing entities. The
process can repeat, with certain groups in the new population forming even
higher-level entities. This process of emergence of major transitions was
explored in [265, 212] for example. Lastly, semantic evolution is related to
the work of [133], who propose a new category of open-ended evolution called
semantic evolution, which refers to the evolution of semantic relationships
within a system. This can be observed in the evolution of web services, where
the meaning of tags changes as new combinations of tags are created. It is not
biological in nature and is also present in the analysis of technological
evolution [20], where the meaning and importance of keywords shift over time.

####  3.4.1 Defining open-endedness

Several necessary conditions and requirements have been identified in the OEE
literature, forming an overlapping set of potential research directions for
developing open-ended systems. We list a few of these conditions here. First,
[193] identifies four requirements:

  1. 1.

An open-ended evolutionary system must demonstrate unbounded diversity during
its growth phase.

  2. 2.

An open-ended evolutionary system must embody selection.

  3. 3.

An open-ended evolutionary system must exhibit continuing new adaptive
activity.

  4. 4.

An open-ended evolutionary system must have an endogenous implementation of
niches.

Next, [291] identified four more necessary conditions, which are

  1. 1.

A rule should be enforced that individuals must meet some minimal criterion
(MC) before they can reproduce, and that criterion must be nontrivial.

  2. 2.

The evolution of new individuals should create novel opportunities for
satisfying the MC.

  3. 3.

Decisions about how and where individuals interact with the world should be
made by the individuals themselves.

  4. 4.

The potential size and complexity of the individuals’ phenotypes should be (in
principle) unbounded.

Then, [304] also stated five requirements for an open-ended system:

  1. 1.

Robustly reproductive individuals.

  2. 2.

A medium allowing the possible existence of a practically unlimited diversity
of individuals and interactions, at various levels of complexity.

  3. 3.

Individuals capable of producing more complex offspring.

  4. 4.

An evolutionary search space that typically offers mutational pathways from
one viable individual to another viable (and potentially fitter ) individuals.

  5. 5.

Drive for continued evolution.

Taylor also states a more general condition that should be sufficient for
creating an open-ended system as “evolutionary dynamics in which new,
surprising, and sometimes more complex organisms continue to appear” [304,
305].

All these conditions illustrate a major challenge of OEE research: the lack of
a clear definition or notion of what exact conditions make a system open-
ended. We seem to agree about what is not open-ended, but whenever a
constraint or requirement for OEE is identified, subsequent evidence forces us
to refine them later. This is related to the problem of complexity, for which
no single definition exists [144].

A common process to produce systems that behave analogously to natural
evolution is to start from evolvable units or building blocks [250, 281, 229,
340, 46, 293, 291]. The reason is that starting from higher-level primitive
units whose emergence would be hard to characterize may be easier and faster
than starting from lower-level components. The results obtained from these
systems are often surprising, as they bear some key similarities to natural
evolutionary processes. For example, we note the emergence of parasitic
entities within the Tierra simulation [250]. The process of emergence of these
building blocks from simple rules and components has also been investigated
significantly [15, 131, 85, 264]. It appears harder to bridge the gap and
create high-level evolutionary-like processes and behaviors from elementary
rules and substrates.

####  3.4.2 Open-endedness in cellular automata

One class of systems that has rich interactions between each of its
components, as well as no predefined evolvable units or assumptions about
individuality is the CA. One of the very first automata, Von Neumann’s self-
reproducing machine, was designed with goals that align with open-ended
evolution, which is to build a machine with no central controller and limited
local interaction that can self-reproduce as a whole [321, 242]. Later, other
self-replicating structures such as Langton’s loop [169] and evoloops [263,
260] showed that more properties of open-ended systems can be included in a
CA. A potential limitation of CAs is the absence of the notion of conservation
of “matter”. For example, the game of life can start from a configuration with
very few live cells and create many more at no cost during its evolution. Some
authors believe that this conservation property is essential to the
construction of an open-ended evolving system [303].

####  3.4.3 Artificial chemistries

Artificial chemistries, are computational models that aim to simulate the
behavior of chemical systems, which are typically used to study the emergence
of complex behavior from simple interactions between individual molecules.
Most of the time, artificial chemistries do not try to accurately model
chemical processes (as in [230, 35, 21, 264] for example). Instead, they build
models of the dynamics of complex molecular processes that lead to
evolutionary behavior [71]. By abstracting away from natural molecular
processes, AC tries to uncover fundamental conditions for the emergence of
organization, self-maintenance, or self-construction with basic building
blocks. There are various approaches for building these artificial
chemistries, of which we review a few here.

###### Rewriting systems.

Rewriting systems are a class of computational models that use a set of
rewriting rules to transform and manipulate strings of symbols. They are
composed of entities or symbols that get modified according to their set of
syntactic rules. Patterns of symbols or entities are replaced according to
these rules. In AlChemy [88], molecules are represented as expressions in the
$\lambda$-calculus. The $\lambda$-calculus is a mathematical formalism that,
like Turing machines, is capable of describing any computable function. In
AlChemy, pairs of randomly selected expressions are joined using function
application, evaluated, and the resulting value is added back to the
population of molecules. This process is repeated to simulate the behavior of
a chemical system. [167] hypothesized that self-reproducing metabolisms emerge
as a subset of autocatalyzed reactions within a Turing-complete set. They
introduced _combinatory chemistry_ , an artificial chemistry designed to
capture the core computational properties of living systems that is based on
the rewriting rules of _combinatory logic_ [62, 272]. The generated structures
exhibit behaviors that are similar to natural metabolisms. The system is able
to represent patterns of arbitrary complexity, and it is able to produce
diverse self-reproducing patterns.

###### Cellular automata.

CA can be seen as a particular case of lattice molecular systems. For example,
the autopoietic system (referring to the ability of an organism to
continuously sustain itself through the exchange of matter and energy with its
environment, while maintaining its own boundaries and identity) introduced by
[314] is a 2D square grid with sites that be occupied by _atoms_ which is
similar to a CA with 4 states. Each of these states is analogous to a chemical
component of the system: ($\emptyset$) empty site, (S) substrate, (K)
catalyst, and (L) monomer. Basic rules are applied asynchronously and define
how neighboring atoms interact with each other. Remarkably, stable self-
repairing cells spontaneously arise from these basic rules. Their membrane is
composed of a chain of monomers, which is maintained by the substrate and
catalyst reacting according to the rules. Some key components of that model
were investigated in other works, showing that they are crucial for this
emergence autopoeisis to be possible [346, 200].

###  3.5 Computing with complex systems

The problem of computing within complex systems is closely related to the
question of decentralized parallel computation, in general, for which there
exists abundant literature. Different paradigms exist for controlling and
harvesting the computations within complex systems. Several other names have
been used for closely related topics, such as organic computing [215] which is
the study of systems with life-like properties such as self-organization or
the ability to adapt to a dynamically changing environment. Agent-based
computing [143] focuses on computing systems composed of several relatively
simple autonomous agents. Amorphous computing [1, 218, 217] is about making
large amounts of individual computing elements work and ensuring “the
cooperation of large numbers of unreliable parts interconnected in unknown,
irregular, and time-varying ways”.

####  3.5.1 Computing in cellular automata

CA are decentralized parallel systems with many identical components with
local connectivity. Because of these properties, they have the potential to
carry out robust and efficient computations. CA-based computing machines could
recover from perturbations or carry out computations in stochastic
environments. Moreover, they are also interesting for modeling the behavior of
natural complex systems. For more details on CAs, see Section 2.1.

###### Von Neumann’s self-reproducing CA.

The early developments of CAs were guided by Von Neumann’s question “What kind
of logical organization is sufficient for an automaton to be able to reproduce
itself?” Since this question may admit very simple solutions, additional
constraints were added so that the problem does not admit trivial solutions.
For example, Von Neumann required that the automaton in question be equivalent
in power to a universal Turing machine while having minimal complexity [321].
The final model he proposed was an intricate CA composed of a tape containing
the instructions to construct the next automaton and a construction unit that
would progressively build that new automaton cell by cell. This was an early
example of complex computations being carried out by a relatively simple
decentralized system such as a CA.

###### Universal Computation in Cellular Automata.

It is not difficult to see that a CA can be capable of universal computation.
The basic approach is to show that it can simulate a Turing machine, which we
assume has an infinite tape. A CA rule can be constructed by reproducing all
the steps of a Turing machine’s behavior while adding a state to each cell,
indicating whether it is active or not, and enforcing that only one cell is
active at a time. This turns the parallel CA into a sequential object that
simulates a Turing machine. A similar construction was carried out by [283],
making a CA with one-to-one correspondence between its time steps and that of
a target Turing machine.

Another approach was used to show the universality of the game of life (see
details in Section 2.1.3). Instead of simulating a Turing machine, basic
logical functions are built from gliders (see figure 2.5(a)) produced by a
game of life structure called _glider gun_. Two gliders that collide within
the simulation will either annihilate or keep moving depending on the exact
position in which they collide. This allows the construction of NOT, AND and
OR gates. For example, see Figure 3.5 for a construction of a NOT gate in the
game of life.

Figure 3.5: Construction of a NOT gate in game of life. The left image
represents an input equal to 1, while the second shows an input equal to 0.
Output streams behave like a NOT gate. A glider gun and a modified half-
frequency glider gun are highlighted. They are necessary for the construction
of the gate. Images are adapted from a blog post [38].

Universal computation is an intriguing yet impractical property, and proving
that a system is a universal computers often has limited usability, but it
serves as a proof of principle that the studied system is theoretically as
powerful as any computer. In the case of the game of life, this was
illustrated by the implementation of the OTCA metapixel which is a tileable
square cell object that can be used to simulate another instance of game of
life within the game. It is important to note that such embedded computers and
Turing machines are often very slow and inefficient, and the game of life has
brittle structures which would be destroyed by the slightest perturbation,