one-dimensional CA rules into each other through coarse-graining of the transition rule. They built a graph of equivalence of all 256 ECA and identified some rules that do not admit any computational reduction. This indicates that some cellular automata are accomplishing fundamentally more computations than others.

### 5.2.2 Filtering

Filtering cellular automata (CA) was introduced to reduce a CA's behavior to its most relevant parts. The goal is to extract relevant irregularities from a CA's space-time diagram. Seminal work by (Hanson and James P. Crutchfield 1992, 1997) formalized the notion of domains and coherent structures in cellular automata. They used a set of regular languages to represent cellular automata dynamics and extract relevant behaviors such as discontinuities between regular domains or "particles". Figure 5.7 shows a filtering example for cellular automaton rule 110 — in Wolfram's numbering.

A filtering method similar to our proposed frequency-based coarse-graining — originally presented as a complexity metric for cellular automata — is introduced in (Wuersche 1999). The author proposes to progressively filter out cells in cellular automata's space-time diagrams according to read frequency of the rule table. Cells that originated from frequent rule table lookups are set to a quiescent or null state. The choice of threshold has to be decided by a user for each rule. Another notable difference is the method aims at making visualization of gliders easier without reducing the size of the grid or making more compact representations.

More recent work by (C. R. Shalizi, Haslinger, et al. 2006) uses the combination of a modified Lyapunov exponent approach with statistical complexity (C. R. Shalizi, K. L. Shalizi, and Haslinger 2004) to underline complex behaviors. However, the first method requires repeated perturbations and simulations of the system to study its sensitivity.

### 5.2.3 Scaling-up cellular automata

Hashlife (Gosper 1984) and other Game of Life-specific optimizations enable simulating a large number of cells for numerous timesteps. Nonetheless, these algorithms essentially exploit input redundancy. The regularity in patterns allowing such optimizations might indicate a lack of novel patterns being generated by the system.
This also means that Game of Life-based simulations are computationally reducible
to a much simpler system, indicating that its computations are inefficient (Wolfram
2002). An optimally complex-behaving computational model should be impossible to
predict except when computing its actual evolution step by step.

In the following, we used coarse-graining as a method for scaling down CAs in both
time and space in order to make visualization of larger patterns and complex behaviors
easier. The underlying fine-scale computations may be essential for these larger patterns
to appear, hence the necessity to keep them. However, analogous to many natural
processes (swarms, chemistry, cells in an organism, DNA), interesting behaviors might
not be observable at the level of individual components — or small groups of components
(individuals, single cells or molecules in the examples above). We view coarse-graining
as a way to reduce a cellular automaton’s space-time diagram to its most relevant parts
while keeping primary dynamics in the background. The resulting diagram would ideally
be an irreducible system.

5.3 Proposed coarse-graining of cellular automata

For reasons stated above, we introduce coarse-graining methods for cellular automata
that are not reversible — information is discarded in the process. This process does
not attempt to find shortcuts for the computations of a cellular automaton, but rather
to select relevant parts of the space-time diagram and discard information irrelevant to
the core behavior. For example, a standard glider in Game of Life spanning 3 × 3 cells
could be replaced with a single cell moving diagonally when coarse-graining by a factor
3. This is because the actual oscillator’s dynamics might not be relevant at this coarser
scale.

Coarse-graining is akin to constructing *supercells* from blocks of individual cells.
These supercells are assigned a new state and form a coarser partitioning of the initial
grid which can be studied as its own system. In particular, complexity metrics or further
coarse-graining can be applied to this new grid.
### 5.3.1 Frequency histogram coarse-graining

A simple coarse-graining is achieved by mapping blocks to a single supercell state according to the probability of this configuration appearing, given a previously constructed model. The easiest way to think of it is with a simple frequency counting model of the distribution of 2 × 2 blocks in a 2D CA. For a 2-state automaton, there are 16 possible supercell configurations. The simplest model for the occurrence of these blocks is their empirical frequency. Let us consider a CA with N blocks of 2 × 2 cells, let $S^{(in)} = \{0000, 0001, 0010, \dots, 1111\}$ be the set of 2 × 2 blocks and $s_i \in S^{(in)}$ be a given supercell. The probability $p_i$ of observing supercell $i$ on a grid $G$ is estimated with

$$p_i = \frac{\text{count}_G(s_i)}{\sum_{s_j \in S^{(in)}} \text{count}_G(s_j)} \quad (5.1)$$

where $\text{count}_G(s_i)$ is the number of blocks matching ($s_i$) in $G$.

Supercells can then be assigned a particular state. We call the corresponding mapping $f: S^{(in)} \to S^{(out)}$. $S^{(out)}$ can be chosen depending on the desired output or use. For instance, with $S^{(out)} = \{0, 1\}$ we can define $f$ to map each supercell $s_i$ as follows:

$$f(i) = \begin{cases} 0 & \text{if } p_i \ge \alpha \\ 1 & \text{if } p_i < \alpha \end{cases} \quad (5.2)$$

where $\alpha$ is a chosen threshold.

#### Partitioning the histogram

This method can be understood as partitioning the histogram of supercell frequency. In equation equation 5.2, supercells with low probability — with higher self-information — are mapped to state 1 whereas commonly occurring states are mapped to 0.

Choosing a partition of the histogram is equivalent to selecting a suitable $\alpha$ — scalar for two output states, or vector $\alpha = (\alpha_1, \dots, \alpha_n)$ for n output states. Therefore, one can map supercells to any number of target states (three or more) by partitioning the frequency histogram into any number of bins. Supercell distribution can be anything between uniform and very unbalanced, with a few supercells being overwhelmingly represented (background) and only a few occurrences of other configurations. The
chosen partitioning has to deal with both situations equally well. In the following, we use a uniform partitioning of the area under the negative log-histogram for elementary cellular automata — supercells are divided into two bins of equal summed negative logarithmic probability. For 2D CAs, we use the same method but with quadratic partition of the histogram ($1/k^2$ instead of $1/k$, with $k$ the number of output states, chosen because of better visual results).

## Dithering

Histogram partitioning introduces another set of parameters to be manually tuned, adding complexity to the procedure. An alternative way to produce an output image from the histogram is to use dithering. Dithering is an image processing technique commonly used to reduce large visual artifacts induced by quantization errors. Noise is added to the image during the quantization process to make the average local value of a set of pixels as close to their target continuous value as possible. The resulting image is created so as to match target continuous values with discrete values only — cell states in the grid. It can be seen as another way of partitioning the histogram with variable thresholds that depend on a running quantization error. Figure 5.2 shows a comparison of dithering and regular histogram partitioning (Floyd-Steinberg's algorithm was used (Floyd and Steinberg 1976)).

<figure><img src="image_53.png" /><figcaption>**Figure 5.2** — Close-up view of coarse-graining effects on a 4-states CA rule (1 shade of blue per state). Both coarse-graining methods conserve many of the interesting structures. Dithering introduces additional artifacts on regular backgrounds. Fig. 5.2a shows actual states in the CA simulation on a 128 × 128 grid. Fig. 5.2b is a coarse-grained version of 5.2a with histogram coarse-graining, the grid is 64 × 64 cells. 5.2c is obtained with histogram coarse-graining and dithering (see Dithering).</figcaption></figure>
## Visualization

One advantage of this frequency histogram-based method is that it naturally highlights rarer events in the simulation grid, creating a “heatmap” of the simulation’s activity. Since we sort supercells according to their observed frequency, the right choice of colors — e.g. progressively darker gradient — can lead to automatic highlighting of active regions of a cellular automaton. Figure 5.3 shows the same simulation both unprocessed and downscaled by a factor of 4 with coarse-graining. Although much coarser, Figure 5.3b is more readable than the base version, which is helpful when dealing with large grids *.

<figure><img src="image_54.png" /><figcaption>**Figure 5.3** – Side-to-side comparison of a CA simulation and its coarse-grained version. The first simulation is 256 × 256 cells and the second has been coarse-grained to 64 × 64. Notice the interesting patterns on Figure 5.3a are hardly distinguishable. They are highlighted by histogram-based coarse-graining in Figure 5.3b.</figcaption></figure>

## Hierarchical coarse-graining

The above procedure can be applied recursively to the same cellular automaton or with larger block sizes to get a progressively coarser representation. Since information is systematically discarded in the process, it cannot be applied any number of times. For this reason, many 2D CAs exhibiting interesting behaviors at the micro-level but not at the macro-level have no remaining visible structure after reducing their scale several

<footnote>* Several figures in this chapter have animated versions, accessible at the project page of our paper (Cisneros, Sivic, and Mikolov 2020) https://hugocisneros.com/ALIFE-Paper-2020/</footnote>
times with this method.

Because a simple model like frequency counting can be estimated quickly, hierarchical coarse-graining is easily applied to large grids, reducing the size by a factor of $n$ (block size) every time. For instance, this property makes it suitable to search the cellular automata rule space for CAs behaving interestingly at multiple coarse-graining levels simultaneously.

### 5.3.2 Clustering

Another way to convert blocks of cells for coarse-graining is to distribute these blocks into a small number of clusters, where each group becomes the new coarse state.

Several distance functions may apply here, the most natural of which being Hamming distance, which measures how many states differ between two positions (Hamming 1950). It is defined for two strings of equal length $n$, $s_1 = [s_{(1,1)}, \dots, s_{(1,n)}]$ and $s_2 = [s_{(2,1)}, \dots, s_{(2,n)}]$, as the number of positions where the two strings differ:

$$ \sum_{k=1}^{n} 1 \{ s_{1}^{(k)} \neq s_{2}^{(k)} \}. \qquad (5.3) $$

A supercell of $N \times N$ cells of a CA can be converted into a string to be compared to other blocks with the Hamming distance. For CAs, we limit ourselves to strings of digits representing states, i.e. $s_{(i,j)} \in \mathbb{N}$. We use a vanilla implementation of the K-means algorithm where clusters' centers are computed using a continuous average of position vectors rounded to nearest integer values. Clusters are initialized with randomly selected observations.

### 5.3.3 Autoencoders for coarse-graining

Instead of just relying on the amount of information of a given supercell's configuration, one can also try to automatically find a relevant representation with dimensionality reduction methods. Autoencoders are neural networks composed of an encoder part and a decoder part, originally designed to identify principal components of a collection of data points (Baldi and Hornik 1989; Hinton 1989; Kramer 1991). An encoder neural network converts data to a latent vector of smaller dimension than the original input.
Then, a decoder neural network reconstructs a vector with the same dimension as the input from this encoded *latent* representation. These models can automatically find an optimal constrained representation through minimizing a reconstruction loss between the original input and the reconstructed output.

We denote the encoder network with $E$ and the decoder network with $D$. We frame the reconstruction problem as a $N$ class classification problem with multiple components — one class per input state, one component for each cell of the $K$ cells in a block. The reconstruction loss is the component-wise cross-entropy between the state of each input cell and the reconstructed state after $D \circ E$ is applied.

<figure><img src="image_55.png" /><figcaption>**Figure 5.4** — Diagram of the autoencoder architecture used for coarse-graining. A block of 6 × 6 cells is encoded in a vector of fixed dimension. There are 3 components in the example. They can either represent a RGB color or a 3 states smaller automaton.</figcaption></figure>

Figure 5.4 illustrates the autoencoder layout for coarse-graining. By adjusting the block size and dimension of the encoded vector, one can influence the amount of information conserved during encoding. Naturally, smaller blocks will be more easily represented in lower dimension.

The encoder has a softmax layer to ensure the coded state's components sum to one. Therefore, one can view this coded supercell as a mixture of states which can either be kept as is or converted to a discrete state by keeping the maximal component only. They are trained with stochastic gradient descent until convergence.

## 5.4 Results

We evaluate our proposed coarse-graining methods in the following two different ways:

— We compare our results on elementary cellular automata (ECA) to previous works
on particle and domain filtering.

— We use a metric which evaluates complexity of CAs introduced in (Cisneros, Sivic, and Mikolov 2019) in order to compare our methods' complexity metric scores of the coarse-grained systems and contrast the scores against a standard image processing baseline that computes local average of neighbouring cells followed by downscaling the grid. Using the complexity metric we measure to what extent the interesting behavior of cellular automata is conserved after coarse-graining compared to this image processing baseline.

In the following we begin by showing that a simple histogram-based coarse-graining is effective at detecting structures (such as gliders) in ECA space-time diagrams. Our method achieves results comparable with previous work, while being simpler to apply.

### 5.4.1 Domains and filtering

In the space-time diagrams of cellular automata, moving structures such as gliders are embedded in uniform or periodic backgrounds, or “domains”. This domain is different depending on the rule: some ECAs have uniform backgrounds, checkerboard backgrounds or more complicated patterns (e.g. rule 110). (James P. Crutchfield and Hanson 1993) also identified chaotic domains, which cannot support regular gliders but have “walls” and “particles”. Those correspond, respectively, to boundaries between two chaotic domains and propagating defects (localized structures with a pattern different from the domain) within a domain.

Our proposed coarse-graining methods offer interesting perspectives to filter cellular automata's space-time diagrams, which enables identifying gliders and studying the formation of large-scale patterns. We find that a simple histogram coarse-graining achieves results comparable to those reported in (Eloranta and Nummelin 1992; Hanson and James P. Crutchfield 1992, 1997; Wuensche 2011) for ECA rules 18 and 54. A similar approach was undertaken in (Wuensche 1999) in which the authors used the entropy of rule table lookup frequencies to filter out regular domains in the space-time diagrams of cellular automata and to identify gliders and domain boundaries. However, Wuensche's approach described in (Wuensche 1999) does not attempt to downscale space-time diagrams.
5.4.2 Results on elementary cellular automata

We apply frequency histogram-based coarse-graining on elementary cellular automata (ECA) and obtain space-time diagrams with suppressed background domains. Resulting partitions of ECAs' space-time diagram are similar to results reported by (Hanson and James P. Crutchfield 1992, 1997). Figure 5.5(a) and 5.6(a) show the space-time diagrams of rules 18 and 54 with random initialization. Boundaries between different background patterns in both Figures were obtained with coarse-graining; they are similar to boundaries obtained by Hanson and Crutchfield. We also observe the propagation of many of the same particles and defects without any prior information about the cellular automaton rule.

Particles in Rule 54 have been used to implement computations (N. Boccara, Nasser, and Roger 1991; Martinez, Adamatzky, and McIntosh 2014; Pivato 2007). Because the presented reduction reduces the size of the grid, it can merge some of those particles, sometimes resulting in ambiguities and gaps. However, our goal here is not to precisely describe particle interactions in order to manipulate or construct complex computations manually. Underlying computations described in the works above are still happening within our reduced CA simulation. We consider the *apparent* destruction of some of these fine-scale details acceptable in order to discover larger-scale complex behavior.

Our method is also arguably much simpler than computational mechanics (used by Hanson and Crutchfield) which requires some reverse-engineering of the rule and the construction of a finite-state transducer to generate output symbols. Although full automation has been demonstrated, this method introduces significant overhead (Rupe and James P. Crutchfield 2018). On the other hand, our method is sensitive to the quality of statistical estimation of the frequency histogram (see equation 5.1) and needs enough input examples to achieve a reasonable result — examples in Figure 5.5 and 5.6 used simulations with the width of 3000 cells, ran for 6000 timesteps to obtain reliable pattern frequency estimates.

In the Figures, we used the coarse-graining method introduced in *Frequency histogram coarse-graining*. Space-time diagrams are coarse-grained by a factor 2 to a binary automaton — each cell corresponds to a 2-cell block. These binary coarse-graining results in the Figures are labeled (c). Because of the statistical nature of the domains of
<figure><img src="image_56.png" /><figcaption>**Figure 5.5** – Space-time diagrams for rule 18 in elementary cellular automata. (a) Standard rule 18 space-time diagram, starting from a random position. (b) Filtered domain with our frequency coarse-graining (even). (c) Our domain boundaries extracted from the filtered domains in (b). (d) Domain boundaries computed according to (Hanson and James P. Crutchfield 1992). Note that (a) shows semi-chaotic behaviour, which is hard to interpret, whereas our method (b) highlights distinct domains within the disordered space-diagram in (a). The detected domains and domain boundaries from previous work (d) and ours (c) are very similar.</figcaption></figure>
these 1D ECA's and the use of blocks of size 2, filtered domains differ depending on the starting position of coarse-graining. We distinguish an odd and even filtered domain.

Figure 5.5(c) is obtained by applying the element-wise OR operator to both the even and odd domain diagrams to merge them into a single space-time diagram. Figure 5.6(c) is obtained by computing differences between neighboring cells after the filtering process to highlight lines. Figure 5.7 is another example showing filtering of particles in rule 110.

### 5.4.3 Complexity metrics and coarse-graining

Coarse-graining is not only useful for detecting gliders and domains in space-time diagrams, but also as a tool to visualize large CAs. To evaluate the quality of our proposed coarse-graining methods, we compare complexity scores computed according to (Cisneros, Sivic, and Mikolov 2019) for different coarse-graining methods. This metric was shown to correlate well with a user study of interesting automata. It uses neural networks to estimate how easy it is to learn a compressed representation of a CA. We also computed the scores on downscaled CAs as a baseline. Local averaging is used for downscaling, with each block of *N* cells being replaced by its average value rounded to the nearest integer state.

Experiments begin by sampling 3600 cellular automata rules with 3 or 4 states. We apply the complexity metric on a randomly initialized simulation on a 512 × 512 grid of cells. The top 100 rules with the highest complexity scores, which should correspond to rules with interesting behaviors, are then used for coarse-graining. We apply coarse-graining on grids of 4096 × 4096 cells, scaling the grid down by a factor of 8, and compute the complexity metric also on the reduced grid. Figures reported in Table 5.1 are percentages of rules still considered interesting (above the selection threshold for the first step of the process) after coarse-graining. The higher this number is, the more a method is able to conserve complex and interesting behaviors after the reduction.

Results in Table 5.1 suggest that using our proposed methods seems largely beneficial for studying complexity in large systems. Histogram and autoencoder methods are superior to downscaling using k-means and local averaging. This could be attributed to the fact that contrary to the latter two, the histogram and autoencoder both represent
<figure><img src="image_57.png" /><figcaption>**Figure 5.6** — Space-time diagrams for rule 54. (a) Space-time diagram of standard rule 54, starting from a random position. (b) Filtered domain with our frequency coarse-graining (even). (c) Particles filtered from the domains in (b) using our method. (d) Domain boundaries computed using computational mechanics (Hanson and James P. Crutchfield 1997). Please note that particles are detected equally well using computational mechanics (d) and our (simpler) frequency-based method (c). Some close-by particle trails are merged using our method.</figcaption></figure>

<table><caption>**Table 5.1** — Experimental results — Percentage of rules classified as interesting after reduction with our 3 proposed methods (K-means, Histogram, Autoencoder), compared to a local averaging baseline.</caption><thead><tr><th>Local-averaging baseline</th><th>K-Means</th><th>Histogram</th><th>Autoencoder</th></tr></thead><tbody><tr><td>19.3%</td><td>40.4%</td><td>82.4%</td><td>84.2%</td></tr></tbody></table>
<figure><img src="image_58.png" /><figcaption>**Figure 5.7** – Spate-time diagram of rule 110 (a) and filtered particles using our histogram-based coarse-graining (b). Structures propagating in time (vertical axis) and space (horizontal axis) become clearly visible in (b) as vertical and diagonal lines.</figcaption></figure>

well anomalies (rare events). This is because rare events are explicitly captured and kept by the histogram method. They also represent useful information that may be kept for reconstruction using the autoencoder.

### 5.4.4 Discussion

Downscaling by local averaging is not an effective solution to the coarse-graining problem for several reasons. In particular, it tends to favor the majority state in a supercell because of the averaging effect. Thin structures spanning only a few cells placed on a uniform background are likely to disappear after coarse-graining, although they may still be relevant with respect to large-scale patterns. The histogram-based method explicitly encodes those rare events in a supercell, even if their size is relatively small compared to the supercell size.

Figure 5.8 is a qualitative comparison of coarse-graining methods. This cellular automaton was selected from the experimental dataset. When simulated on large grids, it generates large linear structures that are 4-cells wide. These structures disappear after downscaling by averaging because the background dominates the average. Other methods correctly highlight these structures when downscaling the grids by a factor of 8. In Figure 5.9, we show another rule that was selected for its high complexity score
on multiple coarse-graining scales from our dataset. The CA has significantly different dynamics depending on the chosen scale. Example 5.9a is a spontaneously occurring stable oscillating glider with period 3. Large structures emerge from these simple gliders when observing large grids. The online project page† shows animated examples for Figure 5.9, emphasizing the advantage of using coarse-graining for visualization. Figures 5.10 and 5.11 show more comparisons of large-scale coarse-graining of interesting CAs.

A crucial advantage of the frequency histogram method is its speed and ease of implementation compared to autoencoders. Other than a few hyper-parameters for partitioning the histogram, no training or tuning is needed to produce the coarse-grained output.

## 5.5 Conclusion

We intend to use these coarse-graining methods to find cellular automata (CA) which exhibit interesting behaviors at multiple scales. Figure 5.9 shows an example of such a CA. We observe various dynamics depending on the scale, from simple oscillating gliders to large wave-like patterns composed of thousands of gliders. It demonstrates that observing multi-scale behaviors within those automata is possible. The existence of 2D cellular automata with disordered behaviors at the smallest level but organized at coarser scales, similar to hidden patterns in rule 18, would also be of great interest.

Cellular automata are powerful computational models. Some of them have been shown to be Turing-complete, and can thus be expected to support arbitrarily complex computations (Berlekamp, Conway, and Guy 2001; Cook 2004). Naturally, most interesting CAs spontaneously generate a fraction of available computations at a time, usually supporting a few stable oscillators or moving structures. Proofs of universality for these CAs required careful design of computational devices out of these stable oscillators and structures, resulting in very brittle and inefficient universal computers. In practise, only elementary functions — such as density classification, binary addition, etc. — can be implemented. This requires searching for CA rules specifically targeted at a particular function (Melanie Mitchell, James P Crutchfield, and Das 1996; Sapin, Bailleux, and Jean-Jacques 2003; Wolfram 2002). Hierarchies are central to naturally occurring com-

<footnote>†. https://hugocisneros.com/ALIFE-Paper-2020/</footnote>
plex phenomena (Simon 1962), and may be required for robust and complex processes
to emerge in CAs.

Viewing space-time diagrams of cellular automata is akin to visualizing a foreign
computer design. Cellular automata are manipulating information, registers and instruc-
tions in parallel in the form of cell states. We believe visualization tools proposed in
this chapter can help understand computations in those unconventional computers. By
reducing available information to its essential parts, we attempt to distill the content
of the space-time diagram with as little prior information as possible. Future work
could focus on identifying some known simple computational primitives within cellular
automata and understanding how our visualization can help to find them.

These methods also enable apprehending large grid sizes for which even image pro-
cessing algorithms begin to show limitations. Complexity metrics and CA classification
techniques can be extended to these reduced large grids and could lead to the discovery
of CAs with — similar to life and physical processes — significantly different dynamics
at multiple scales that could in turn be a basis for artificial evolution.
<figure><img src="image_59.png" /><figcaption>**Figure 5.8** – Qualitative comparison of coarse-graining methods. Simulations are on grids of 4096 × 4096 cells coarse-grained to 512 × 512. Most lines are barely visible with downscaling 5.8a, but are visible in 5.8b-5.8d. Coarse-graining helps visualize linear structures that would be hard to see otherwise.</figcaption></figure>
<figure><img src="image_60.png" /><figcaption>**Figure 5.9** – Changing CA dynamics at multiple scales. (a) shows a single glider oscillating between 3 positions. Such gliders emerge spontaneously from a random initialization of a small grid, as shown in (b). When scaling the grid up, trails of gliders begin to appear, creating moving straight and diagonal lines, as shown in (c). Scaling up even more, individual gliders are not visible anymore, as shown in (d). In an even larger grid, shown in (e), many more triangular-shaped waves travel and collide with each other. Please note that (d) and (e) are coarse-grained to 256 × 256. Otherwise, the patterns would not be visible.</figcaption></figure>
<figure><img src="image_61.png" /><figcaption>**Figure 5.10** – A CA with 4096 × 4096 cells coarse-grained to 256 × 256. Comparison of the histogram (5.10b) and autoencoder (5.10a) methods.</figcaption></figure>

<figure><img src="image_62.png" /><figcaption>**Figure 5.11** – A CA with 4096 × 4096 cells coarse-grained to 256 × 256. Comparison of the histogram (5.11b) and autoencoder (5.11a) methods.</figcaption></figure>
Learning efficiency in deep
reservoir computing

It is common to evaluate the performance of a machine learning model by measuring
its predictive power on a test dataset. This approach favors complicated models that can
smoothly fit complex functions and generalize well from training data points. Although
essential components of intelligence, speed, and data efficiency of this learning process
are rarely reported or compared between different candidate models. In this chapter,
we introduce a benchmark of increasingly difficult tasks together with a data efficiency
metric to measure how quickly machine learning models learn from training data. We
also highlight that within complex systems, there are computations taking place that
can be harnessed for various purposes. To that end, we compare the learning speed
of some established sequential supervised models, such as RNNs, LSTMs, or Trans-
formers, with relatively less-known alternative models based on reservoir computing,
which is a tool for harvesting the computations happening within a complex system.
The proposed tasks require a wide range of computational primitives, such as memory
or the ability to compute Boolean functions, to be effectively solved. Surprisingly, we
observe that reservoir computing systems that rely on dynamically evolving feature
maps learn faster than fully supervised methods trained with stochastic gradient opti-
mization while achieving comparable accuracy scores. The code, benchmark, trained
models, and results to reproduce our experiments described in this chapter are available
at https://github.com/hugcis/benchmark-learning-efficiency/.
## 6.1 Introduction

Most machine learning models are evaluated by measuring performance on a specific dataset or task. Learning efficiency – the ability to learn, generalize, and adapt quickly from a few examples – is crucial for practical intelligence (Kanazawa 2004) and low-data machine learning applications, but rarely used to evaluate models. Supervised learning systems are theoretically limited in their learning speed by the optimization algorithms used for training. These algorithms, such as stochastic gradient descent (SGD), have various speed guarantees depending on the structure of the function to be optimized (Bottou, Curtis, and Nocedal 2018). However, when intelligent beings learn, they appear to quickly reuse past knowledge and progressively improve over time. Their learning speed depends on a dynamically evolving internal state. To measure the learning efficiency of various systems, in this work we propose the Weighted Average Data Efficiency (WADE) metric based on the time taken to reach several test accuracy checkpoints. We also design a simple modular benchmark composed of a set of sequential tasks. They begin with the task of recognizing a simple periodic sequence in an input string and end with elaborate question-answering tasks that require counting occurrences of patterns and long-term memory.

Established sequential supervised models such as recurrent neural networks (RNNs; Elman 1990), long short-term memory networks (LSTMs; Hochreiter and Schmidhuber 1997) or Transformers (Vaswani et al. 2017) lack essential properties such as learning beyond the training phase or the ability to adapt over time after being trained. These models can also be expensive to train, requiring a large number of labeled training examples to reach reasonable performance, leading to poor learning speeds. In this work, we use the newly proposed WADE metric and the benchmark dataset to experimentally compare the learning speed of these well-established models, such as RNNs, LSTMs, and Transformers, with less explored *reservoir computing models*.

Reservoir computing is a computational framework that aims to exploit the states of a complex dynamical system. The simplest example of a reservoir computer is a RNN with frozen weights. This special RNN performs random manipulation on its hidden state in reaction to each new input. Interestingly, it has been shown that with a specific initialization of the frozen weights, these RNNs (called Echo state networks)
can keep a memory of past inputs (Jaeger 2001). Usually, a standard linear regression
is added as a decoder to extract valuable representation from the hidden state for some
downstream task. Freezing the weights of these recurrent models is useful when available
supervision is very limited or non-existent or for reinforcement learning with sparse
rewards since direct training would be impossible. In such cases, a reservoir computer
creates a continuously evolving pool of random functions that can be combined using
the last trainable layer.

When evolving in response to input stimuli, complex recurrent systems such as RNNs
are building dynamically changing representations of data within their internal state
(Nino Boccara 2010). We know that these internal states can be interesting on their own
because of their ability to self-organize and exhibit increasingly complex behaviors (Allen
and Strathern 2003; C. H. Bennett 1995; Cisneros, Sivic, and Mikolov 2019; Goldstein
2011; Koppel and Atlan 1991). We wish to investigate whether complex dynamical
systems — in particular RNNs with frozen weights (echo-state networks) (Jaeger 2001)
and reservoir cellular automata (Yilmaz 2014) — create representations that allow them
to learn faster, as measured by our metric.

**Contributions.** In this chapter, we make the following main contributions: First, we introduce the Weighted Average Data Efficiency (WADE) metric to measure the learning speed of various learning systems and use it to benchmark a few standard models on the IMDB text classification task (Maas et al. 2011). Second, we present a benchmark of language-based tasks of increasing difficulty to evaluate the learning speed in different conditions. The proposed tasks require a wide range of computational primitives, such as memory or the ability to compute Boolean functions, to be effectively solved. Third, we study the learning speed of reservoir computing learning models and compare them with more standard supervised solutions.

**6.2 Related work**

The WADE metric is a generalization of the *Time-to-threshold* metric (M. E. Taylor and Stone 2007; M. E. Taylor, Stone, and Liu 2007) introduced for measuring transfer learning in reinforcement learning contexts. In general, the Time-to-threshold is simply
defined as the number of training steps needed to reach a fixed threshold performance. However, this definition leaves open the choice of threshold or the definition of a training step. WADE alleviates this issue by aggregating several of these thresholds into a single number that summarizes the learning speed.

Other metrics for measuring how quickly a model adapts to new tasks have been introduced in the context of transfer learning, few-shot and zero-shot learning. In few-shot learning, one tries to obtain the best performance for a particular task using a small amount of labeled data compared to the task's fully supervised equivalent (Y. Wang et al. 2020). This correlates with a model's learning speed, but these problems often measure how much prior information about similar data has been encoded in the models. With our benchmark and the WADE metric, we explicitly measure the number of steps to reach multiple test accuracy values using all the data needed, effectively emphasizing data efficiency.

Sample efficiency has also been studied in the context of reinforcement learning. (Chevalier-Boisvert et al. 2018) use the number of demonstrations before a task is solved to measure sample efficiency. This requires defining what solving the task means, which may vary from task to task. Another approach is to measure performance (cumulated reward, accuracy, etc.) after a fixed budget of training steps (Yarats et al. 2019). In this case, the most efficient model is the one that achieves the best performance within the allocated budget. In other cases, the sample efficiency is mentioned but not explicitly measured and one has to examine the learning curves (Buckman et al. 2018). The WADE metric is a general approach to measure the learning efficiency of machine learning models. We use it to benchmark a few standard models on the IMDB text classification tasks (Maas et al. 2011) and propose a set of modular and extensible language-based tasks.

Synthetic tasks such as ours have played a vital role in a series of crucial advances in machine learning algorithms. For example, the XOR problem has partially motivated the development of neural networks (Minsky and Papert 1972; Rumelhart, Hinton, and Williams 1985), and the *circle and ring* dataset has inspired the creation of novel clustering algorithms (Ng, Jordan, and Y. Weiss 2001). The design of synthetic datasets has also been an essential component of the development of learning algorithms with memory and general computational capabilities (Graves, Wayne, and Danihelka 2014;
Hochreiter and Schmidhuber 1997; Joulin and Mikolov 2015; Richardson et al. 2020; Weston et al. 2016).

Other tasks are based on real datasets with artificial manipulations (Goodfellow et al. 2014; Krizhevsky and Hinton 2009; Nguyen et al. 2017; Srivastava et al. 2013). The goal of our dataset is to be truly progressive in difficulty yet simple to understand and extend, to allow applications in the field of online learning, and to easily understand a model's basic computational capacities. Combined with our metric, it enables us to measure learning speed across a range of conditions. In contrast to similar synthetic datasets, we built this benchmark so that the last task is vastly more complicated than the first and could still be extended to more complex examples.

## 6.3 A benchmark for reservoir computing

To measure the learning speed of candidate systems and their ability to improve over time, we propose a performance metric and a standardized set of tasks. We want to select those systems that quickly and reliably adapt and learn from new inputs. For this purpose, we introduce the Weighted Average Data Efficiency (WADE) metric. It aggregates the speed at which a model reaches several test accuracy checkpoints. We describe the metric in more detail in Section 6.3.1.

To reliably compare learning speeds for various systems on a shared foundation, we also introduce a novel dataset described in Table 6.1. It is made up of sequential tasks that begin with straightforward pattern recognition and progressively increase in complexity to approach the complexity of natural language and other complex real-world tasks.

We do not focus on the prediction performance of our models but rather on their data efficiency — the number of example sequences they need to learn from before reaching a target accuracy on a validation set.

Standard benchmarks and metrics such as those introduced in this chapter have always been essential in advancing various aspects of machine learning. For example, the LSTM network demonstrated a superior memory capacity on a set of synthetic tasks designed to challenge the memory of sequential learning systems (Hochreiter and Schmidhuber 1997). Our goal with this benchmark is to emphasize measuring learning
<table><caption>**Table 6.1** – General description of all the tasks in the benchmark.</caption><thead><tr><td>Task id</td><td>Name</td><td>Description</td></tr></thead><tbody><tr><td>1</td><td>Simple periodic pattern identification</td><td>Identify a simple periodic pattern.</td></tr><tr><td>2</td><td>Harder periodic pattern identification</td><td>Identify a periodic pattern with an arithmetically increasing period.</td></tr><tr><td>3</td><td>Symbol counting</td><td>Count symbols from a sequence.</td></tr><tr><td>4</td><td>Pattern counting</td><td>Count patterns (delimited group of symbols) from a sequence.</td></tr><tr><td>5</td><td>Simple question answering</td><td>Answer simple YES/NO questions from a single prompt.</td></tr><tr><td>6</td><td>Harder question answering</td><td>Answer simple YES/NO questions from a single prompt with a more extensive vocabulary.</td></tr><tr><td>7</td><td>Question answering with world definition</td><td>Answer YES/NO questions from a sequence of prompts.</td></tr><tr><td>8</td><td>Question answering with world definition and counting</td><td>Answer YES/NO and counting questions from a sequence of prompts.</td></tr><tr><td>9</td><td>Adjective question answering</td><td>Answer YES/NO and adjective questions from a sequence of prompts.</td></tr><tr><td>10</td><td>Adjective question answering and counting</td><td>Answer YES/NO, adjective, and counting questions from a sequence of prompts.</td></tr></tbody></table>
speed across tasks of varying difficulties with a range of computational requirements rather than focusing on performance only. We describe the performance metric and the benchmark next.

### 6.3.1 Performance metric

We introduce the Weighted Average Data Efficiency (WADE) metric as a way to measure how quickly a model learns using a weighted average of inverse times taken to reach various test accuracy *checkpoints* over time.

It is computed for an evenly distributed set of target accuracies $\mathcal{A}$. They represent the *checkpoints* at which the speed of learning is estimated. For example, we may choose $\mathcal{A} = [0.1, 0.2, 0.3, 0.4, \dots, 1.]$. The metric is then calculated as

$$WADE(\mathbf{a}) = \frac{1}{\sum \alpha} \sum_{\alpha \in \mathcal{A}} \frac{\alpha}{T(\alpha, \mathbf{a})}, \qquad (6.1)$$

where $\mathbf{a} = (a_0, a_1, \dots, a_n)$ is a sequence of test accuracies achieved by the evaluated system sampled at different training steps. The quantity $a_i$ typically corresponds to the accuracy reached after seeing $i$ examples, and $T(\alpha, \mathbf{a})$ is the number of steps in the sequence $\mathbf{a}$ needed to reach an accuracy of $\alpha$. It is defined as

$$T(\alpha, \mathbf{a}) = \min \{i \in \{1, \dots, n, +\infty\} \mid a_i \ge \alpha\}. \qquad (6.2)$$

We also define $T(\alpha, \mathbf{a}) = +\infty$ if the accuracy value $\alpha$ is never reached in $\mathbf{a}$. This is equivalent to appending an additional term $a_{+\infty}$ to $\mathbf{a}$, always set to the maximum accuracy 1. Note that by construction, $T(\alpha, \mathbf{a})$ is in $[1, +\infty[$.

Since $T$ can be $+\infty$ we define $\frac{1}{+\infty} = 0$ for the quantity in equation 6.1 to always exist. A visual intuition of $T(\cdot, \cdot)$ is given in figure 6.1.

The choice of checkpoints $\mathcal{A}$ does not need to be tuned in any specific way because WADE($\mathbf{a}$) quickly converges to a single value when $\mathcal{A}$ approaches the continuous interval $[0, 1]$. The approximation is good enough as long as $\mathcal{A}$ is not too coarse (more than ten elements was enough in our experiments), and the WADE values computed from the same set $\mathcal{A}$ are comparable.

The time-to-threshold $T$ is always greater than or equal to 1 step for any threshold
<figure><img src="image_63.png" /><figcaption>**Figure 6.1** – Illustration of the calculation of $T(\cdot, \cdot)$, representing the number of training steps (x axis) needed to reach a certain test accuracy $\alpha$ (y axis) from a learning curve. In this example, $\mathcal{A} = [0.1, \dots, 0.8]$ (y axis). $T(0.6, \mathbf{a})$ is highlighted in red. $T(0.8, \mathbf{a}) = +\infty$ as the accuracy of 0.8 is never reached.</figcaption></figure>

and sequence of accuracy scores. We have $\forall \alpha \in [0, 1]$, $\forall \mathbf{a} = (a_n)_{I \subset \{\mathbb{N} \cup \{+\infty\}\}}$, and we have

$$ \frac{1}{T(\alpha, \mathbf{a})} \le 1, \qquad (6.3) $$

and therefore we always get $0 \le \text{WADE}(\mathbf{a}) \le 1$. The metric is equal to 0 for systems that never get past the smallest possible accuracy, while 1 corresponds to reaching a perfect test accuracy in one single training step. Such a system would also be considered to be performing well according to the underlying performance metric with which it is usually evaluated. Therefore, maximizing WADE also maximizes performance.

### 6.3.2 Description of tasks in the benchmark

This section provides a more detailed description of each task in our benchmark. The tasks are designed to be language modeling tasks, where the goal is to predict some tokens from sequences of previously processed tokens. An overview of the tasks is given in Table 6.1. The tasks are divided into three groups: (i) binary tasks with only binary symbols, (ii) general symbolic tasks – symbolic manipulations with arbitrary symbols, and (iii) language-based tasks, where symbols represent words in English and behave like a language. We introduce this benchmark together with the WADE metric, but both can be used in other contexts as well to measure the learning speed of other systems. Individual sentences are generated and divided into a training set and a test set for
<figure><img src="image_64.png" /></figure>

The symbol `x` is the query symbol (QS) that marks the beginning of the query. In the first example above, the goal is to predict the token `5` because the symbol `A` appears `5` times. As detailed in Sect. 6.6, we represent these nonbinary symbols with one hot encoding, so the numerical nature of some tokens is not encoded a priori.

**Pattern counting.** This aim of this task is to count the number of occurrences of delimited patterns instead of single symbols. A sequence is still divided between a prompt — before `x` — and a query — after `x`. One has to predict the symbol coming after each separator symbol (S) `y` in the query part of the sentence. For example, sentences are of the form:

<figure><img src="image_65.png" /></figure>

Multiple queries are presented successively, which requires keeping and being able to retrieve several counts simultaneously. A query is composed of a pattern, a separator symbol, and the pattern count that the system should predict.

## Basic language understanding

To make the tasks progressively more complex, we steer them towards general language understanding tasks. The tasks described below are generated automatically, but gradually incorporate more complex skills required for advanced language processing. The last task is a step towards understanding the general language albeit with a limited vocabulary.
**Elementary question answering (QA).** This task introduces elements of natural language. Each example is composed of a stated fact and a question about that fact. A sentence is constructed from a few basic elements: (i) Names (e.g., JOHN, JAMES, etc.), (ii) Verbs (e.g., HEAR, SEE, etc.), (iii) Answers (YES or NO), (iv) Additional words and symbols (I, DO, NOT, AND, BUT, ?, .).

A random subset of names is selected, and we generate a random prompt/question pair from it. The question is drawn to ensure an equal proportion of positive and negative answers. For example, sentences may look like this:

I HEAR JOHN AND PAUL . DO I HEAR PAUL ? YES

I SEE JOHN BUT I DO NOT SEE PAUL AND TOM . DO I SEE TOM ? NO

The only token to predict is the binary answer YES or NO.

**Question answering (QA) with adjectives.** This task extends the previous task by adding adjectives and modifiers to the object names. The queries may be about the subject-verb relation or the subject-adjective relation.

I SEE A SMALL BANANA . WHAT IS THE SIZE OF THE BANANA I SEE ? SMALL

I SEE A LARGE GREEN APPLE BUT I DO NOT SEE A RED APPLE .

DO I SEE A LARGE APPLE ? YES

I SEE A SMALL GREEN APPLE BUT I DO NOT SEE A BANANA .

WHAT IS THE COLOR OF THE APPLE I SEE ? GREEN

Here the task output space is slightly larger because the model may be predicting YES, NO, SMALL, GREEN, etc.

**Question answering (QA) with world definition.** This task introduces more complex configurations in which the state of the world is defined in one or more sentences, and an unknown number of questions follow. This is more akin to a real-world conver-
sation where stored facts should be remembered longer and accessed on demand. For
example, below we show a generated group of sentences followed by several questions:

I SEE A SMALL BANANA.

I SEE A LARGE GREEN APPLE BUT I DO NOT SEE A RED APPLE.

I SEE A SMALL GREEN APPLE BUT I DO NOT SMELL A BANANA.

WHAT IS THE COLOR OF THE APPLE I SEE ? GREEN

HOW MANY THINGS DO I SMELL ? ONE

DO I SEE A LARGE APPLE ? YES.

The difficulty of each of these tasks can be modulated by changing the size of the base vocabulary, the length of sequences, or the number of queries. Our particular setting of these parameters will be described in section 6.8.1.

## 6.4 Standard language classification task

To show the usefulness of measuring WADE on standard language classification tasks, we train various text classifiers on the IMDB dataset and compare their WADE scores with a usual performance metric for classification: accuracy. This classification task, first proposed by (Maass, Natschläger, and Markram 2002), consists of deciding if a movie review is positive or negative from its text. It contains 25000 training examples and 25000 test examples. The two labels are balanced in both the training and test set. This dataset is a high dimensional language-based task with a binary output.

We study five standard models: (i) an Elman recurrent neural network (RNN) (Elman 1990) with tanh activation functions trained with backpropagation through time. (ii) A long-short term memory (LSTM) recurrent neural network (Hochreiter and Schmidhuber 1997), also trained with backpropagation through time. (iii) A gated recurrent unit (GRU) recurrent neural network (Cho et al. 2014). (iv) A standard encoder-only transformer neural network model (Vaswani et al. 2017). (v) A logistic regression using a bag-of-words representation of each sentence as input features. All the
<figure><img src="image_66.png" /><figcaption>**Figure 6.2** – Test accuracy curves for each model. Shaded areas are ±1σ around the average over 50 runs.</figcaption></figure>

models are trained with batches of training data using the Adam optimization algorithm (Kingma and Ba 2015). Each model's hyperparameters are chosen to ensure they have a similar number of trainable parameters except for the logistic regression whose parameter count is solely determined by the input and output dimensions.

<table><caption>**Table 6.2** – Comparison of our new WADE metric to assess learning speed and the standard maximum test accuracy on the IMDB classification dataset. Results are averaged over 50 separate runs. (↑ indicates that higher is better).</caption><thead><tr><th></th><th>WADE ×10<sup>-2</sup> (std.) ↑</th><th>Max test accuracy (std.) ↑</th></tr></thead><tbody><tr><td>RNN</td><td>1.028 ±0.283</td><td>0.705 ±0.076</td></tr><tr><td>LSTM</td><td>2.280 ±0.303</td><td>0.902 ±0.002</td></tr><tr><td>GRU</td><td>2.711 ±0.318</td><td><b>0.904</b> ±0.002</td></tr><tr><td>Linear</td><td>3.737 ±0.745</td><td>0.862 ±0.000</td></tr><tr><td>Transformer</td><td><b>8.716</b> ±0.720</td><td>0.872 ±0.003</td></tr></tbody></table>

Table 6.2 shows the results of all models on the IMDB dataset reporting both the standard test accuracy as well as our new WADE metric measuring the learning speed of the different models. We report the maximum test accuracy observed during training. This corresponds to the model checkpoint that would be selected with a validation set before using it on test data. The transformer model learns the fastest of all, as shown by its higher WADE score, but it does not reach test accuracy values as high as the GRU and LSTM model. We think that this could be attributed to the transformer model over-fitting on the available data as discussed below.

According to the WADE metric, the RNN is the worst (i.e., slowest to learn) model
with a score of $1.04 \times 10^{-2}$ whereas the linear model and the transformer are the fastest
with a score above $8 \times 10^{-2}$. The transformer seems to have more reliable learning
speeds than the linear model as shown by the lower standard deviation ($0.7 \times 10^{-2}$
versus $4.3 \times 10^{-2}$). The LSTM and GRU models have intermediate and stable learning
speeds. The GRU has slightly better WADE score than the LSTM, which can be also
seen by inspecting the learning curves in figure 6.2 where the GRU is consistently above
the LSTM.

However, when we look at the maximum test accuracy we obtain a different ordering,
with LSTM and GRU performing best with slightly above 90% accuracy followed by the
transformer and the linear model (around 86%) and finally the RNN with the lowest
accuracy. The LSTM, GRU and linear models all seem to have converged at the end
of the experiment. The transformer's lower final accuracy despite it being considered a
state of the art model may be explained by over-fitting (apparent on the graph with the
test accuracy score going down). Moreover, the RNN clearly hasn't converged at the
end of the experiment which also explains the relatively low max accuracy score.

Our new WADE metric gives a complementary view of a model's abilities, which
may be significantly different from what can be obtained from the usual performance
metrics focused on the final accuracy of the model.

## 6.5 Reservoir computing and reservoir cellular automata

We use names adapted from (Jaeger 2012) in this section. An echo-state network is a
random recurrent neural network with frozen weights and skip-connections. Its random
weights are sampled in a specific way so that it performs random combinations of input
vectors with its current state while keeping a history of past inputs (Jaeger 2001).

Reservoir cellular automaton (ReCA) is a model similar to echo-state networks but
where a cellular automaton (CA) replaces the random RNN. The cellular automaton can
be seen as a RNN with additional weigth-sharing similar to convolutional neural network.
The special structure of a recurrent CA update makes it more likely than random RNNs
to generate complex structures (Wolfram 1983, 2002). Because CAs were not designed
to make use of inputs or produce outputs, we extend the model to make it accept input
vectors and to make reading from the CA state possible (details in Section 2.3.3).
We also propose two novel projection schemes that offer more flexibility than existing ones. They extend the one-to-one projection and allow for a wider variety of produced encodings:

**One-to-many.** Each input bit is assigned exactly to *k* positions in *P* instead of one. This is equivalent to adding *k* separate and mutually exclusive one-to-one projections into a single one.

**One-to-pattern.** Each input bit is assigned to a random contiguous pattern of *k* bits set in a fixed position.

The effect of applying our three methods to a simple input with three components is illustrated in Fig. 6.3. Projections are chosen to map each input bit to a unique output configuration.

<figure><img src="image_67.png" /><figcaption>**Figure 6.3** – Three encoding methods. From left to right: *one-to-one*, *one-to-many* and *one-to-pattern*.</figcaption></figure>

Following (Nichele and Gundersen 2017; Nichele and Molund 2017a; Yilmaz 2014), the input is projected multiple times to add redundancy to the encoding. This was experimentally observed to improve performance. We also use a projection vector larger than the initial one. Projections are generated randomly *R* times, applied, and concatenated as a single large encoder to create the full CA input vector. The parameter *R* is called redundancy.

For cellular automata in 1D, the space *P* is one dimensional, and the concatenation is performed on this dimension. In higher-dimensional spaces, this concatenation must be defined in another way.

We write the *R* projection functions $E_1, E_2, \dots, E_R$. The final size of the input vector and the CA state grid is now $R \times L_d$ instead of $L_d$. We have

$$p_t = P(x_t) = E_1(x_t) \| \dots \| E_R(x_t), \qquad (6.4)$$
where $\parallel$ is the concatenation operator.

For example, other projections have been proposed and implemented in (Yilmaz 2014). We choose to present the three above because they are simple to understand and implement, and their effects can be explored thoroughly.

**Input combination.** There are multiple ways to combine the input vector with the current state of the CA. Glover et al. (2021) propose to use a XOR function between the projected input and the state of the CA.

At each input step $t$, the projected input vector $p_t$ is XORed element-wise with the current CA state $s_t$, so that each 1 bit of the input switches the corresponding bit in the CA state to another value. This creates a new state $s'_t$ from which the CA will evolve. $s'_t$ is defined as

$$s'_{t} := p_{t} \otimes s_{t}, \qquad (6.5)$$

where $\otimes$ is the element-wise XOR operator between two vectors of binary values, and $s'_t$ is the temporary CA state resulting from the combination of the CA state and the input vectors at time $t$.

From the state of the CA at time $t$, $s'_t$, we then compute the next CA states applying the update function $\Phi$,

$$s_{t+1} = \Phi(s'_{t}). \qquad (6.6)$$

This is one of many possible ways to combine an input vector with the current state of the CA that may affect its performance as a reservoir. The XOR-based input combination gives an asymmetrical role to 0 and 1 in the input vectors, which is natural considering how we encode and project categorical data points. Different rules of CAs might benefit or lose performance due to these encoding choices. The combination problem can be generalized to incorporate it into the CA rule search problem. We demonstrate this in the next paragraph.

**Generalization.** We generalize the input combination method above by incorporating it into the CA update rule. Since the input vector $p$ is binary, we can treat its value at
position *i* as just another virtual CA cell. For a standard ECA, the update step takes
into account the three immediate neighbors **s**<sup>(i-1)</sup>, **s**<sup>(i)</sup>, **s**<sup>(i+1)</sup> plus the additional virtual
cell **p**<sup>(i)</sup>. Instead of 8 possible input configurations for a binary 1D CA, we now have 16.
In this extended CA space, the number of possible rules is 2<sup>16</sup> = 65536 instead of 256.

<figure><img src="image_68.png" /><figcaption>**Figure 6.4** – Comparison of standard CA update rule and our extended input combination rule.</figcaption></figure>

This method is illustrated in Fig. 6.4 during the regular CA update. It generalizes
the concept of input combination with the state *s*. The XOR method described above
is one of its special cases, but our method also contains all possible Boolean functions
with 4 inputs.

**6.6 New benchmark: compared methods**

In the following sections, we carry out experiments to measure WADE on the bench-
mark described in Table 6.1 and introduced in section 6.3.2. We compare several baseline
models to understand their learning efficiency: three of the most common sequential
machine learning models for which all parameters are trained, RNNs, LSTMs, and
transforms, with two methods using reservoir computing: the echo-state networks (ESN,
with a random RNN reservoir) and reservoir cellular automata (ReCA, with a cellular
automaton reservoir) for which only a fraction of the parameters are learned. Table 6.3
presents all the methods we study in our experiments.

In all our tasks, the input data is assumed to be categorical and sequential. Tokens
are observed one by one in sequence, we define this input as $X = [X_1, \dots, X_t, \dots]$, $t \in \mathbb{N}$, $\forall t X_t \in \mathcal{X} \subset \mathbb{N}$, where *t* is the time index of the sequence, each $X_i$ is a token corresponding to time index *i*, and $\mathcal{X}$ is the set of numbered input categories — or
<table><caption>**Table 6.3** – Summary of the compared models: three are fully trained, and two are reservoir-based.</caption><thead><tr><th>Methods</th><th></th><th>Type</th></tr></thead><tbody><tr><td>RNN</td><td>Recurrent neural networks</td><td></td></tr><tr><td>LSTM</td><td>Long-short term memory networks</td><td>Fully trained</td></tr><tr><td>Transformer</td><td></td><td></td></tr><tr><td>ESN</td><td>Echo-state networks</td><td></td></tr><tr><td>ReCA</td><td>Reservoir Cellular Automata</td><td>Reservoir-based</td></tr></tbody></table>

different tokens in the vocabulary. First, each categorical input vector is one-hot encoded into a vector of size $L$, where $L = |\mathcal{X}|$ is the size of the input vocabulary. We define $\mathbf{x}_t$ as the encoded vector form of $X_t$, and we have $\forall t, \mathbf{x}_t \in \{0, 1\}^L$, with $\sum_{i=1}^L (\mathbf{x}_t)_i = 1$. Since the tasks are designed to be generally compatible with language modeling, the input and output vocabularies are the same.

### 6.6.1 Fully trained sequential models (RNN, LSTM and Transformer)

We first study two standard supervised recurrent models: (i) an Elman recurrent neural network (RNN) (Elman 1990) with tanh activation functions trained with backpropagation through time. (ii) A long-short term memory (LSTM) recurrent neural network (Hochreiter and Schmidhuber 1997), also trained with backpropagation through time. (iii) An encoder-only transformer model with positional encoding (Vaswani et al. 2017).

The three models are trained with a batched Adam optimization algorithm (Kingma and Ba 2015) to minimize a cross-entropy loss function between the predicted and target tokens. No other training device, such as dropout, regularization, or normalization, is used for these fully trained baselines.

### 6.6.2 Echo-state networks and reservoir cellular automata

In our experiments, we also use two reservoir based models. The first is an echo state network (ESN). We compare this model with reservoir cellular automata (ReCA, see Sections 2.3.3 and 6.5 for more details).
### 6.6.3 Experimental set-up

We ran 100 separate experiments with different random seeds for each of the CA rules, the RNN, LSTM, Transformer, and ESN on each task in the benchmark. These experiments have a separate input projection matrix for the CA, different random weights for the ESN, and different weight initialization for the supervised baselines. The task inputs are also generated from a new seed for every experiment, but we reuse the seeds for the same experiment on different models to ensure they were trained with the same data. Intervals of one standard deviation for these multiple experiments are reported in the result graphs. The code to reproduce our experiments is available on GitHub†.

#### Training parameters

For each experiment, we generate 1200 random examples from the task generator. We split this set randomly into a training set with 80% of the data — 960 examples — and a test set with the remaining 240 examples. The reservoir is run on each training example for the reservoir-based models, which creates the input features for training the decoder. The sequential supervised models use batches of single sequences with the Adam algorithm (Kingma and Ba 2015). They are trained for ten epochs in total. With reservoir models, only the last linear layer (the decoder) is trained. We minimize the cross-entropy loss with stochastic gradient descent (SGD), doing only a single pass over the 960 training examples.

Every few training steps, we generate the output predictions on the testing set, decode it, and compute the test accuracy for our WADE metric. Supervision is only applied on tokens that can be predicted — similar to masked language modeling, e.g., only the answer token is used in the symbol counting or question answering tasks. Accuracy is also computed for these symbols only.

## 6.7 Human performance evaluation

The proposed benchmark is relatively simple to understand, and hence one may ask what human performance would be and what WADE values this would correspond to. In particular, language tasks appear to be readily solvable from one's understanding

<footnote>†. https://github.com/hugcis/benchmark-learning-efficiency</footnote>
of the English language. However, similar to how words are encoded as vectors before being processed by a neural network, we need to obfuscate the tokens to make the task equivalent. This could be achieved in a number of ways. For example, if we map all available tokens to random letters of the alphabet, the apparently trivial task

I DO NOT SEE PAUL . DO I SEE PAUL ? NO

I HEAR JAMES BUT I DO NOT HEAR PAUL AND JOHN . DO I HEAR JAMES ? YES

would become significantly less obvious to humans if written

w K k A D r K w A D l W

w Z t g w K k Z D G C r K w Z t l H.

One would need to read through several of these sentences to identify patterns such as the fact that W and H represent Yes or No or that r plays the role of a full stop.

We apply the following procedure in our human evaluation experiments:

1. Choose a random task among 10.

2. Apply a random mapping from the task token to letters of the alphabet.

3. Present the sequences one by one with the tokens to be predicted hidden.

4. The user enters his predicted answer.

5. The valid sequence is shown so that the user can learn from their mistakes.

6. Steps 3-5 are repeated until 10 sequences are correctly solved in a row. Then we go back to step 2 with a new task.

We add the requirement that no external device such as pen and paper or a note-taking program should be used during the experiment, so the user relies solely on their memory. The accuracy is computed by counting the number of right answers in a row. For example, three right answers in a row would correspond to an accuracy of 30%, while ten right answers in a row are 100%, which also corresponds to a change of task. This accuracy score is attributed to the first correct answer of the series of correct answers. This means that a series of five correct answers, starting from Question 6 to Question 11, will correspond to reaching the accuracy of 50% in Question 6. This ensures that ten correct answers on the first attempt yield a WADE score of 1.
## 6.8 Experimental parameters

We report all the parameters used in our experiments in table 6.4:

<table><caption>**Table 6.4** – Experimental parameters common to all tasks. Some of the sizes (such as *h*) vary from task to task.</caption><thead><tr><th></th><th>Reservoir-based</th><th>Fully trained</th></tr></thead><tbody><tr><td>Total number of sequences per task</td><td>1200</td><td>1200</td></tr><tr><td>Number of training sequences</td><td>960</td><td>960</td></tr><tr><td>Number of testing sequences</td><td>240</td><td>240</td></tr><tr><td>Passes over the data (epochs)</td><td>1</td><td>10</td></tr><tr><td>Random runs per task</td><td>100</td><td>100</td></tr><tr><td>Algorithm</td><td>SGD</td><td>Adam (Kingma and Ba 2015)</td></tr><tr><td>Learning rate</td><td>0.001</td><td>0.001</td></tr><tr><td>Regularization</td><td>weight decay</td><td>None</td></tr><tr><td>Internal state (hidden) size</td><td>1800</td><td>h task-dependent</td></tr><tr><td>Number of trainable parameters</td><td>1800</td><td>h<sup>2</sup> + 2 × h × dictionary_size for the RNN<sup>2</sup></td></tr><tr><td>Output non-linearity</td><td>Softmax</td><td>Softmax</td></tr><tr><td>Internal non-linearity</td><td>Not applicable</td><td>tanh</td></tr><tr><td>Batch size</td><td>1</td><td>1</td></tr></tbody></table>

### 6.8.1 Task generation parameters

The tasks are generated according to the procedures described in Section 6.3. They have some parameters that allow the difficulty of the task to be adjusted. We report results on ten tasks. The parameters chosen for our experiments are listed below:

**Periodic (1) and Increasing period (2):** Sequences are generated from patterns of length between 1 and 10.

**Easy symbol counting (3):** Available symbols are A, B and C. Generated sequences have between 1 and 10 of these symbols in the prompt, and the query has either one, two, or all three symbols.

**Hard symbol counting (4):** Available symbols are the same as for the previous task. Generated sequences have between 1 and 45 symbols with separators in the
prompt. There is a minimum of 1 query and can be as many queries as there are different patterns in the prompt.

**Question answering (5):** There are five available names and two verbs. The prompt consists of between one and five names, and the question is about one of these names.

**Harder question answering :** There are eleven available names and five verbs. The prompt is made of between one and five names, and the question is about one of these names.

**Question answering with world (7), with counting (8):** There are thirteen available names and seven verbs.

**Adjective question answering (9), with counting (10):** There are eight available names, six verbs, four color adjectives, and five size adjectives. The prompt consists of between one and six statements, and there are up to eight questions.

We chose relatively small values of these parameters because we are interested in simple tasks so that models can learn from less than 100 examples. Moreover, the number of possible sentences generated from these small values is already huge, with more than $10^{35}$ possible sentences for task 4, for example. These parameters could also be varied dynamically to change the task's difficulty when needed or turn each task into multiple subtasks or levels of difficulty. We chose the ten separate tasks/settings pairs listed above to get a broad overview of our benchmarked models on a range of task difficulties.

## 6.9 Results

We report the final weighted average data efficiency (WADE) scores on our benchmark in Table 6.5 and the accuracy results for comparison in Table 6.6. We include the best elementary reservoir cellular automaton (ReCA) and the echo state network (ESN) with the same internal state size for each task.

Figure 6.5 shows the learning curves for the best reservoir cellular automaton, as well as the echo-state network, the recurrent neural network (RNN), LSTM, and the

<footnote>†. *h* is chosen to match the number of parameters of the reservoir-based methods.</footnote>
<table><thead><tr><th rowspan="2">Task ID - Name</th><th colspan="2">Reservoir</th><th rowspan="2">Human subject</th></tr><tr><th>ReCA</th><th>ESN</th></tr></thead><tbody><tr><td>1 - Periodic</td><td><strong>0.78</strong> ±0.05</td><td>0.74 ±0.05</td><td>1.00</td></tr><tr><td>2 - Incremental periodic</td><td>0.57 ±0.02</td><td><strong>0.72</strong> ±0.02</td><td>1.00</td></tr><tr><td>3 - Symbol counting</td><td><strong>0.06</strong> ±0.01</td><td>0.04 ±0.01</td><td>0.11</td></tr><tr><td>4 - Pattern counting</td><td>0.12 ±0.04</td><td><strong>0.14</strong> ±0.03</td><td>0.09</td></tr><tr><td>5 - Basic question answering (QA)</td><td><strong>0.31</strong> ±0.08</td><td>0.26 ±0.03</td><td>0.15</td></tr><tr><td>6 - Harder QA</td><td><strong>0.35</strong> ±0.11</td><td>0.26 ±0.03</td><td>0.12</td></tr><tr><td>7 - QA with world def.</td><td><strong>0.32</strong> ±0.10</td><td>0.27 ±0.04</td><td>—</td></tr><tr><td>8 - QA with world def. &amp; counting</td><td>0.09 ±0.03</td><td><strong>0.14</strong> ±0.06</td><td>—</td></tr><tr><td>9 - Adjective QA</td><td>0.04 ±0.03</td><td>0.04 ±0.04</td><td>—</td></tr><tr><td>10 - Adjective QA &amp; counting</td><td>0.04 ±0.02</td><td><strong>0.06</strong> ±0.02</td><td>—</td></tr></tbody></table>

<table><thead><tr><th rowspan="2"></th><th colspan="3">Fully supervised</th></tr><tr><th>RNN</th><th>LSTM</th><th>Transformer</th></tr></thead><tbody><tr><td>1</td><td>0.28 ±0.07</td><td>0.31 ±0.04</td><td>0.31 ±0.06</td></tr><tr><td>2</td><td>0.32 ±0.11</td><td>0.49 ±0.15</td><td>0.42 ±0.16</td></tr><tr><td>3</td><td>0.04 ±0.02</td><td>0.03 ±0.01</td><td>0.05 ±0.02</td></tr><tr><td>4</td><td>0.10 ±0.05</td><td>0.08 ±0.03</td><td>0.13 ±0.04</td></tr><tr><td>5</td><td>0.17 ±0.08</td><td>0.16 ±0.07</td><td>0.20 ±0.06</td></tr><tr><td>6</td><td>0.16 ±0.07</td><td>0.12 ±0.06</td><td>0.24 ±0.05</td></tr><tr><td>7</td><td>0.17 ±0.07</td><td>0.11 ±0.06</td><td>0.24 ±0.05</td></tr><tr><td>8</td><td>0.10 ±0.05</td><td>0.05 ±0.02</td><td>0.02 ±0.01</td></tr><tr><td>9</td><td><strong>0.05</strong> ±0.03</td><td>0.03 ±0.02</td><td>0.02 ±0.01</td></tr><tr><td>10</td><td>0.05 ±0.02</td><td>0.03 ±0.02</td><td>0.01 ±0.01</td></tr></tbody></table>

**Table 6.5** – Comparison of WADE scores (also shown in parentheses in the legend in figure 6.5, higher is better) of the best cellular automaton rules (ReCA, Yilmaz 2014) for each task against an echo-state network (ESN, Jaeger 2001), a RNN, a LSTM (Hochreiter and Schmidhuber 1997), and a Transformer (Vaswani et al. 2017) with the same number of parameters. The dashed line “—” indicates that the task was too difficult to complete from memory alone for the human subject. The dots indicate that the task name is the same as in the first line. Accuracy scores are also reported in Table 6.6.
Transformer for all ten tasks. Interestingly, the reservoir-based models are consistently more efficient learners than the fully supervised methods, reaching better accuracy in much fewer training steps. For example, for tasks 5, 6, and 7, the LSTM needs ten times more steps to approach the accuracy that the reservoir CA model reached in less than 1000 training steps.

Echo-state networks (ESN) and reservoir cellular automata (ReCA) appear to learn at similar rates, with no clear advantage for one or the other, as each model outperforms the others in five tasks out of ten. On tasks 2, 4, 8, and 10, the ESN is visibly faster than the ReCA (see curves Figure 6.5), which explains the ESN's higher WADE scores even though the ReCA reaches higher accuracy values after several more training steps.

<table><thead><tr><th rowspan="2">Task ID - Name</th><th colspan="2">Reservoir</th></tr><tr><th>ReCA</th><th>ESN</th></tr></thead><tbody><tr><td>1 - Periodic</td><td>0.99 ±0.01</td><td><strong>1.00</strong> ±0.01</td></tr><tr><td>2 - Incremental periodic</td><td>0.88 ±0.01</td><td>0.87 ±0.03</td></tr><tr><td>3 - Symbol counting</td><td>0.80 ±0.02</td><td>0.30 ±0.02</td></tr><tr><td>4 - Pattern counting</td><td>0.56 ±0.01</td><td>0.59 ±0.02</td></tr><tr><td>5 - Basic QA</td><td>0.81 ±0.03</td><td>0.73 ±0.03</td></tr><tr><td>6 - Harder QA</td><td>0.72 ±0.04</td><td>0.57 ±0.03</td></tr><tr><td>7 - QA with world def.</td><td>0.66 ±0.03</td><td>0.60 ±0.03</td></tr><tr><td>8 - QA with world def. & counting</td><td>0.59 ±0.03</td><td>0.56 ±0.03</td></tr><tr><td>9 - Adjective QA</td><td>0.62 ±0.04</td><td>0.49 ±0.03</td></tr><tr><td>10 - Adjective QA & counting</td><td>0.54 ±0.02</td><td>0.46 ±0.03</td></tr></tbody></table>

<table><caption>**Table 6.6** – Comparison of accuracy scores (higher is better) of the **ReCA**, **ESN**, **RNN**, **LSTM**, and **Transformer** models with a similar number of parameters. In contrast to the results of table 6.5, the fully-supervised models are more performant when we measure the accuracy, as shown here, but do not necessarily do as well when we measure the speed of learning, as shown in table 6.5.</caption><thead><tr><th rowspan="2"></th><th colspan="3">Fully supervised</th></tr><tr><th>RNN</th><th>LSTM</th><th>Transformer</th></tr></thead><tbody><tr><td>1</td><td>0.79 ±0.08</td><td>0.68 ±0.04</td><td>0.69 ±0.04</td></tr><tr><td>2</td><td>0.87 ±0.00</td><td><strong>0.89</strong> ±0.02</td><td>0.88 ±0.00</td></tr><tr><td>3</td><td>0.33 ±0.03</td><td>0.36 ±0.03</td><td><strong>0.97</strong> ±0.01</td></tr><tr><td>4</td><td>0.61 ±0.05</td><td><strong>0.61</strong> ±0.02</td><td>0.54 ±0.03</td></tr><tr><td>5</td><td>0.51 ±0.02</td><td>0.75 ±0.05</td><td><strong>1.00</strong> ±0.00</td></tr><tr><td>6</td><td>0.51 ±0.03</td><td>0.68 ±0.07</td><td><strong>1.00</strong> ±0.00</td></tr><tr><td>7</td><td>0.51 ±0.04</td><td>0.64 ±0.07</td><td><strong>1.00</strong> ±0.00</td></tr><tr><td>8</td><td>0.47 ±0.05</td><td>0.50 ±0.06</td><td><strong>0.98</strong> ±0.01</td></tr><tr><td>9</td><td>0.43 ±0.04</td><td>0.44 ±0.03</td><td><strong>0.87</strong> ±0.11</td></tr><tr><td>10</td><td>0.47 ±0.04</td><td>0.49 ±0.03</td><td><strong>0.57</strong> ±0.04</td></tr></tbody></table>

Even if they lack slightly in accuracy, as seen for example on the curves of task 4,
the two reservoir-based methods consistently outperform the fully supervised sequential methods (RNNs and LSTMs) in terms of learning speeds. This better learning efficiency could be explained by the internal state structure introduced by the CA rules and the special form of the ESN random matrix which favors memory retention whereas usual recurrent network initialization does not — we initialize the weights of the fully trained models from a uniform distribution $U(-\sqrt{h^{-1}}, \sqrt{h^{-1}})$ in our experiments, where $h$ is the hidden size.

The human subject scores are estimated based on the authors' performance on obfuscated versions of the tasks — all input tokens are mapped to random symbols. These scores may appear surprisingly low in some of these experiments. Although the task examples presented in Section 6.3.2 seem easy to understand. We rely heavily on our prior knowledge about the symbols to understand the patterns — the words in tasks 5–10 or the numbers in tasks 3 and 4. These symbols are randomly remapped in our human experiments, and more examples, as well as a good memory, are needed to understand the tasks and learn the mapping itself, hence the slower learning.

It is interesting to note that RNNs also seem to perform better than LSTMs and Transformers at the beginning of the training in all tasks but the first two. Even though the Transformer is nowadays generally considered a superior model, vanilla RNNs may still remain competitive in the very low data and computation regimes. This is especially pronounced for tasks 8, 9, and 10, where the RNN test accuracy curve starts increasing significantly 1000 steps before the LSTM. After several epochs, the Transformer still outperforms other alternatives in terms of test accuracy on most tasks.

We note that we implicitly assume a fixed cost per training iteration in our experiments and that each training example is seen once. Without these requirements, one could achieve higher WADE results at the cost of additional computations and memory usage by using *replay*-inspired methods (Gepperth and Karaoguz 2016; Hinton and Plaut 1987; Rebuffi et al. 2017; Robins 1993) that retrain the models with past stored inputs. The results in Table 6.5 used each input sequence once.
<figure><img src="image_69.png" /><figcaption>**Figure 6.5** – Average learning curves and WADE scores (shown in parentheses in the legend) for each task in the benchmark. The dark blue curves represent the best elementary cellular automata (CA) rule, and the green curves represent the echo-state networks (ESN). Note that the x-axis is logarithmic, showing ten times more training steps for the RNN and LSTM. Shaded areas represent one standard deviation around the average over the 100 different experiments.</figcaption></figure>
## 6.10 Reservoir cellular automata (ReCA) results

We present some detailed results from our experiments with reservoir cellular automata. First, general statistics about ECA performance on the five first tasks (tasks with ID 1 to 5).

<figure><img src="image_70.png" /><figcaption>**Figure 6.6** – Average test accuracies across rules, hyperparameters, and runs for each task. The best solution for each task is shown in red.</figcaption></figure>

Fig. 6.6 shows a summary of the accuracy scores for each task. Score distributions vary a lot from task to task because of the different output spaces (binary for Periodic, Inc-per, and QA and multi-modal for the others).

Next, we give a more in-depth analysis of the best performing ECAs on the first two tasks.

### 6.10.1 Binary sequences

The binary sequence task should be the simplest to solve. Since it requires some memory, we expect some CA rules with very chaotic behavior — like ECA rule 30 — to fail at it. We observed that the best rules are consistent with the periodic and ordered types.

The four best rules displayed in figure 6.7 all implement a similar mechanism, using translations of cells from one column to the next at every step. This translation is a memory mechanism, because it shifts any cell that was turned on in reaction to input
<figure><img src="image_71.png" /><figcaption>**Figure 6.7** – Top performing rules and hyperparameters for the binary periodic sequence task. All of the best rules seem to make use of a lateral translation, which is an effective memory mechanism. Rule 2, 130 and 194 only differ by 1 transition in their rule function.</figcaption></figure>

before it could be overwritten by a subsequent input that would be mapped to the same grid position.

<table><caption>**Table 6.7** – Top 10 rules for the periodic binary sequence task (ordered left to right) — best hyper-parameter combination. Many rules get close to the best possible accuracy.</caption><thead><tr><th rowspan="2">Rule</th><th colspan="5">Top 10 rules</th></tr><tr><th>38</th><th>24</th><th>231</th><th>152</th><th>66</th></tr></thead><tbody><tr><th>Average accuracy</th><td>0.969</td><td>0.97</td><td>0.97</td><td>0.97</td><td>0.97</td></tr><tr><td></td><td>189</td><td>194</td><td>52</td><td>130</td><td>2</td></tr><tr><td></td><td>0.97</td><td>0.97</td><td>0.97</td><td>0.971</td><td>0.971</td></tr></tbody></table>

## 6.10.2 Symbol counting

The easy version of this task yielded the most surprising results: some CA rules unexpectedly reach very good scores. These top rules are reliably found to have the best accuracy scores, even when using powerful decoders. The best performing rule of all the possible ECAs is rule 37.

As shown in Figure 6.8, the two best rules seem to employ a similar “computing mechanism” to solve the task. They seem to grow tree-shaped structures that sometimes become wider. One hypothesis for the success of these two rules is that they encode information about the number of symbols observed in the width of these tree structures. RC is useful for this kind of analysis because it has some level of interpretability. The
<figure><img src="image_72.png" /><figcaption>**Figure 6.8** — The two best performing rules for the easy symbol counting task (.82 average accuracy).</figcaption></figure>

weights of the output decoding layer can inform us of which of the components of the CAs internal state are the most important for the task being solved. However, even with this tool, it can still be hard to disentangle the effect of each component and their interactions.

<table><caption>**Table 6.8** — Top 10 rules for the easy symbol counting task (ordered left to right) — best hyper-parameter combination. Notice the three best rules are largely better than most of the others.</caption><thead><tr><th rowspan="2">Rule</th><th colspan="5">Top 10 rules</th></tr><tr><th>28</th><th>92</th><th>220</th><th>70</th><th>198</th></tr></thead><tbody><tr><th>Average accuracy</th><td>0.571</td><td>0.572</td><td>0.573</td><td>0.574</td><td>0.582</td></tr><tr><td></td><td>156</td><td>78</td><td>123</td><td>91</td><td>37</td></tr><tr><td></td><td>0.594</td><td>0.598</td><td>0.643</td><td>0.721</td><td>0.807</td></tr></tbody></table>

## 6.11 Conclusions

Learning speed and data efficiency are essential components of any learning system. Our learning speed metric can offer a novel perspective on several machine learning models. Instead of focusing on pure performance, measuring and comparing the data efficiency of different models will hopefully lead to better systems for online and continual learning.

Even with the right metric, it is difficult to thoroughly evaluate the ability of a model to learn efficiently. Our benchmark evaluates a range of problem difficulties which would be challenging to construct by combining or manipulating existing datasets. However, the tasks remain easy to understand and use. Since the tasks are language-based, they can be further mixed or chained to create continuous learning problems and may also be easily extended in a follow-up work.
We study lesser-known machine learning models based on evolving states of complex systems that can learn through self-organization. A complex dynamical system comprises many interacting agents and evolves over time according to a fixed update rule. These agents can be hidden neurons of a RNN or nodes in a graph. Such systems often exhibit emergent global dynamics resulting from the actions of its parts rather than the decisions of a central controller. These dynamics lead to surprisingly complex behavior, which can be random, chaotic, or may lead to unbounded growth of complexity (Nino Boccara 2010). Due to these properties, reservoir computing systems may be a promising alternative that addresses the shortcomings of standard supervised models.

Surprisingly, such models achieve remarkable learning efficiency compared to the more standard sequentially supervised models trained with stochastic gradient-based learning. Complex systems-based models consistently outperform sequential supervised methods and even achieve better learning efficiency than humans on some tasks. They demonstrate more efficient learning on our benchmark at a fraction of the computational and data cost of the conventional models. We believe that more advanced models of this type could lead to more robust and data-efficient machine learning in the future, especially in low-data applications or problems where supervision is limited. Complex systems are underexplored and seem worth further investigating for building the next generation of learning algorithms.
# Conclusion

In this chapter, we summarize our contributions in the thesis.

## 7.1 Contributions

In this thesis, we have developed some tools to better understand and make use of the computations that occur within complex systems. We summarize our contributions in the following.

- In Chapter 2, we gave an overview of the cellular automaton (CA) model and the specific challenges it poses. We review the deep connection between CAs and recurrent neural networks (RNNs) and how this can be used to apply CAs in reservoir computing (RC). Next, in Chapter 3, we place our work within the vast body of literature on complex systems, complexity, emergence, and learning.

- In Chapter 4, we define a novel metric of complexity for complex systems. The metric is inspired by principles of compression and algorithmic complexity. It uses the ability of small neural networks to learn a model of the local structures in a system, and the evolution of the predictive power of that model as the system evolves over time. We evaluated the quality of this metric by measuring its correlation with human perception of complexity. We find a higher correlation with human annotations than alternative methods on a dataset of CAs rules labeled as complex or not. We use the metric to discover new CAs rules with surprisingly complex behavior semi-automatically.

- In Chapter 5, we built on the work of Chapter 4 to work on the specific challenges posed by working with large-scale systems such as cellular automata. In these systems, qualitatively different behavior may emerge at various scales. To allow dealing with these large systems and apply complexity measures and classification
methods on a range of scales, we developed three coarse-graining methods based on
simple statistical analysis, clustering algorithms and autoencoder neural networks
that can reduce the size of a system while retaining useful information.

— In Chapter 6, we tackled the issue of using complex systems for general-purpose task solving, using the RC paradigm. We also developed a metric for the speed of learning of machine learning systems. Using that metric, we looked at the data efficiency of some well-known algorithms rather than their task-based performance only. Surprisingly, RC models using random frozen RNNs or CAs are significantly more efficient than other alternatives on a range of tasks. We evaluated this on some standard language datasets and introduced our own dataset of progressively more complex tasks. Efficiency is a crucial property in low data and compute settings, and our work showed that some overlooked methods may actually be competitive in these situations.
# Future Work

This chapter outlines potential future directions for extending our work. Our thesis has investigated the connections between complex systems, open-ended evolution, and learning. While these fields have been studied for some time, many open problems remain, some of them poorly understood, making this research exploratory in nature. We hope that our work can advance our understanding of learning and adaptation in natural and artificial systems, leading to the development of more effective and efficient learning algorithms in the future.

## 8.1 Evolving cellular automata for complexity

The metric of complexity developed in Chapter 4 and the others presented in Section 3.1 often gives a single value output from a system's evolution over time. Similarly to how Melanie Mitchell, James P Crutchfield, and Das (1996) evolves CAs rules to solve a particular task, it seems appealing to use complexity as a fitness function for a genetic algorithm. Such an algorithm would generate new rules that are progressively more complex (according to the complexity metric).

It is difficult to apply this principle in practice. Because many complexity metrics such as the algorithmic complexity 3.1.6 are approximating some uncomputable ideal value. Candidate systems that maximize a particular metric are often unsatisfying because they exploit a particular flaw of that approximation. This could be accounted for in future work using multiple complementary complexity metrics or using another surrogate metrics, such as the ability to learn to solve auxiliary tasks and generalize from basic tasks to harder ones. This approach motivated our work in Chapter 6, where we design a benchmark of progressively more complex tasks that could be used to evaluate the ability of a system to perform complex computations.
## 8.2 Feedback reservoir computing

In Chapter 6, we explored the applications of the reservoir computing paradigm to Cellular automata (CAs). In general, RC assumes a purely forward model, which means that inputs are fed into the reservoir and outputs are decoded from it. The trainable decoder layer is trained offline on a training dataset and is then fixed during testing. We illustrate the principle of RC in Figure 8.1a. This structure is often sufficient for supervised tasks when a sufficiently large training dataset is available.

<figure><img src="image_73.png" /><figcaption>**Figure 8.1** – Comparison of regular reservoir computing with feedback reservoir computing. Time flows from left to right on both Figures.</figcaption></figure>

A straightforward extension that could make the RC systems fully autonomous would be to transmit an error signal within the reservoir state at each output. This extension we call *feedback reservoir computing* is illustrated in Figure 8.1b alongside the standard RC model 8.1a. An ideal system would use an internal learning algorithm embedded within the reservoir state update function and act on the reservoir state, to adjust its future outputs in response to an error signal. This would enable the system to gradually enhance its performance over time. The only mechanism that should be built into this system would be an incentive to minimize the error signals received by adaptation. The main limitation of this idea is that the design of such a system with built-in adaptation is not easy. We do not know of a mechanism that can enable autonomous adaptation
and improvement without external input. The error signal is a type of external input, but it is not specified how the system should use the signal. Our work on complex systems points towards cellular automata and other complex systems as candidates for supporting such a mechanism, which would rely on the growth of complexity.

## 8.3 Learning in dynamical systems

By examining the learning process in complex systems, neural networks, and the reservoir computing framework from a unified perspective, we can identify a generalization that provides a valuable perspective on the problem of learning in dynamical systems. This generalization allows us to consider the various components of these systems in a more integrated manner, enabling us to develop a more comprehensive understanding of the underlying mechanisms of learning without having to focus on a particular dynamical system.

This form of learning occurs dynamically as a system is simulated or run. Rather than using traditional parameter updates, it takes place in the system's state or “activations”, resulting in what we refer to as *learning in dynamical systems*. This process is analogous to an inner loop or “thinking phase”, during which the system can self-organize by manipulating its current state without external changes to its parameters. This type of learning is already present in various machine learning systems, including some recurrent neural networks (RNNs), which use short-term dynamical learning to solve language-based tasks (see Section 8.3). Transformers are another type of neural network that has been popular for processing text sequences. The memory of the transformer is not an emergent byproduct of the training process of the neural network because the attention mechanism is directly processing a "window" of input tokens. Emergent memory is also present in some form in the RC framework and in the update rule of gradient-based learning algorithms. Although effective, this form of learning is often not studied or optimized to the same extent as more conventional methods of parameter optimization.

**Generic model.** We give a general description of a model of learning in dynamical systems. A dynamical system is described by a sequence of variables $S_t$ taking values in some state space $S$ at times indexed by $t$. In the most general setting, the state space
can be real-valued or discrete, and the time index may also be continuous or discrete. An evolution function $f$ specifies the state of the dynamical system at time $t$ given a history of states for $t' < t$. It may be deterministic or stochastic.

We study the special case of discrete-time dynamical systems where the current state depends on the previous state.

$$ \forall t \in \mathbb{N}, \quad S_{t+1} = f(S_t) \qquad (8.1) $$

The inputs $x \in \mathcal{X}$ can be used to condition the update rule and enable the dynamical system to interact with an environment. The space $\mathcal{X}$ can be chosen arbitrarily, for example, the space of real vectors in dimension $n$, $\mathcal{X} = \mathbb{R}^n$. For an input $x$, we can write the new dynamical update equation

$$ S_{t+1} = f(S_t, x). \qquad (8.2) $$

Outputs can be observed from the current state $S_t$ with a decoding function $D$. We define the output for time step $t$,

$$ y_t = D(S_t). \qquad (8.3) $$

Depending on the use cases, alternate representations may be considered where the output depends on two or more time steps or an input vector $x$. We give a few well-known examples of learning in dynamical systems from the field of machine learning.

### Dynamical learning in RNNs
We study the example of a question-answering task with a pre-trained RNN. It is easy to see that a RNN can be written fully using equation 8.2 and equation 8.3. The task of answering questions is about reading information from a prompt and answering a question that involves recalling some data from the prompt. An example of such a prompt and question:

<figure><img src="image_74.png" /></figure>

More advanced question answering requires reasoning and advanced processing of the prompt. In the above example, it would suffice to remember the words of the prompt.
We consider a trained RNN evaluated on a set of question-answering tests. If the data set was designed correctly, the network should not have prior information about a sentence/question pair before reading it. The relevant piece of information of the prompt has to be stored within the values of the hidden state of the RNN and not in the weights of the neural network since they are not changed during this phase. This transient learning that enables the RNN to memorize the beginning of the prompt is exactly the type of dynamical learning that we describe above. RNNs are trained offline to achieve this, but once they are trained, learning happens dynamically.

Modern RNNs are not designed to take full advantage of this memory property and will progressively overwrite the memory if run for more timesteps. Still, they illustrate the type of learning we want to emphasize. We expect advanced systems to be able to keep that memory and also be capable of manipulating stored information to construct a reasoning and form novel concepts.

**Supervised learning with stochastic gradient descent.** We consider another example: a single hidden layer neural network with weight matrices $W_1 \in \mathbb{R}^{n \times d}$ and $W_2 \in \mathbb{R}^{d \times o}$. We train the network with standard backpropagation and stochastic gradient descent with a learning rate $\tau$. The neural network is represented by a function $F$, and the loss function between the network output and the label is written as $\mathcal{L}$.

Using the notation of Section 8.3, we define $S_t = (W_1^{(t)}, W_2^{(t)}) \in \mathbb{R}^{n \times d} \times \mathbb{R}^{d \times o}$ containing the neural network parameters at step $t$ of the training. We assume that the training pairs $(X_k, y_k)$ are numbered according to their selection order for the stochastic gradient descent algorithm. The stochastic gradient update function for the state $S_t$ is:

$$S_{t+1} = f(S_t, X_t, y_t) = \left( W_1^{(t)} - \tau \frac{\partial \mathcal{L}(F(X_t), y_t)}{\partial W_1^{(t)}}, W_2^{(t)} - \tau \frac{\partial \mathcal{L}(F(X_t), y_t)}{\partial W_2^{(t)}} \right). \quad (8.4)$$

Note that the function $f$ is deterministic for a given ordering of training pairs. Therefore, the stochasticity of $f$ is contained in the numbering of training examples.

We note that $f$ is a fixed update function (from the dynamical system point of view of the training pipeline, a training input/output pair $(X, y)$ is a pair of input values). In supervised learning, the function $f$ causes the state to converge to a fixed point. This property is desired when solving a target task characterized by a loss $\mathcal{L}$. Because of
<figure><img src="image_75.png" /><figcaption>**Figure 8.2** – Learning happens within the “activations” of this dynamical system, which in this example are the weights of a neural network being updated with the stochastic gradient descent algorithm (SGD). The fixed update function depends on an input pair $(X, y)$ and the previous state vector $S = (W_1, W_2)$.</figcaption></figure>

that convergence property, a neural network cannot be expected to produce any novel
behavior after the end of its training. On the contrary, we know that other complex
dynamical systems that we study in this thesis, like cellular automata, may exhibit a
behavior of increasing complexity during their development, with no sign of convergence
towards a stable state.
<figure><img src="image_76.png" /></figure>

Bibliography

Abelson, Harold, Don Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas F. Knight Jr, Radhika Nagpal, Erik Rauch, Gerald Jay Sussman, and Ron Weiss (2000). « Amorphous Computing ». In: *Communications of the ACM* 43.6, pp. 74–82 (Cited on pages 62, 69).

Adams, Alyssa, Hector Zenil, Paul C. W. Davies, and Sara Imari Walker (Apr. 20, 2017). « Formal Definitions of Unbounded Evolution and Innovation Reveal Universal Mechanisms for Open-Ended Evolution in Dynamical Systems ». In: *Scientific Reports* 7.1, p. 997. ISSN: 2045-2322. DOI: 10.1038/s41598-017-00810-8 (Cited on page 31).

Allen, Peter M. and Mark Strathern (2003). « Evolution, Emergence, and Learning in Complex Systems ». In: *Emergence* 5.4, pp. 8–33 (Cited on page 115).

Alomar, M. L., V. Canals, V. Martínez-Moll, and J. L. Rosselló (Sept. 2014). « Low-Cost Hardware Implementation of Reservoir Computers ». In: *2014 24th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS)*. 2014 24th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS), pp. 1–5. DOI: 10.1109/PATMOS.2014.6951899 (Cited on page 37).

Anderson, P. W. (Aug. 4, 1972). « More Is Different ». In: *Science* 177.4047, pp. 393–396. ISSN: 0036-8075, 1095-9203. DOI: 10.1126/science.177.4047.393. pmid: 17796623 (Cited on page 93).

Andre, David, Forrest H. Bennett, and John R. Koza (July 28, 1996). « Discovery by Genetic Programming of a Cellular Automata Rule That Is Better than Any Known Rule for the Majority Classification Problem ». In: *Proceedings of the 1st Annual Conference on Genetic Programming*. Cambridge, MA, USA: MIT Press, pp. 3–11. ISBN: 978-0-262-61127-5 (Cited on page 65).
Antonik, Piotr (2018). *Application of FPGA to Real-Time Machine Learning: Hardware Reservoir Computers and Software Image Processing*. Springer Theses. Cham: Springer International Publishing. ISBN: 978-3-319-91052-9 978-3-319-91053-6. DOI: 10.1007/978-3-319-91053-6 (Cited on page 37).

Antonik, Piotr, Nicolas Marsal, Daniel Brunner, and Damien Rontani (Nov. 2019). « Human Action Recognition with a Large-Scale Brain-Inspired Photonic Computer ». In: *Nature Machine Intelligence* 1.11 (11), pp. 530-537. ISSN: 2522-5839. DOI: 10.1038/s42256-019-0110-8 (Cited on page 38).

Antonik, Piotr, Anteo Smerieri, Francois Duport, Marc Haelterman, and Serge Massar (June 19, 2015). « FPGA Implementation of Reservoir Computing with Online Learning ». In: 24th Belgian-Dutch Conference on Machine Learning (Benelearn). Delft, Netherlands (Cited on page 37).

Antunes, Luis, Lance Fortnow, Dieter van Melkebeek, and N. V. Vinodchandran (Apr. 4, 2006). « Computational Depth: Concept and Applications ». In: *Theoretical Computer Science*. Foundations of Computation Theory (FCT 2003) 354.3, pp. 391–404. ISSN: 0304-3975. DOI: 10.1016/j.tcs.2005.11.033 (Cited on page 49).

Antunes, Luís and Lance Fortnow (June 1, 2009). « Sophistication Revisited ». In: *Theory of Computing Systems* 45.1, pp. 150–161. ISSN: 1433-0490. DOI: 10.1007/s00224-007-9095-5 (Cited on page 52).

Arata, Hideki, Yoshiaki Takai, Nami K. Takai, and Tsuyoshi Yamamoto (1999). « Free-Form Shape Modeling by 3D Cellular Automata ». In: *Proceedings Shape Modeling International'99. International Conference on Shape Modeling and Applications*. IEEE, pp. 242–247 (Cited on page 22).

Babson, Neil and Christof Teuscher (Dec. 15, 2019). « Reservoir Computing with Complex Cellular Automata ». In: *Complex Systems* 28.4, pp. 433–455. ISSN: 08912513. DOI: 10.25088/ComplexSystems.28.4.433 (Cited on page 40).

Bäck, Thomas and Hans-Paul Schwefel (1993). « An Overview of Evolutionary Algorithms for Parameter Optimization ». In: *Evolutionary computation* 1.1, pp. 1–23 (Cited on page 5).
Bagley, R.J. and J.D. Farmer (1991). « Spontaneous Emergence of a Metabolism ». In: *Artificial Life* II X, pp. 93–140 (Cited on page 60).

Baldi, Pierre and Kurt Hornik (Jan. 1989). « Neural Networks and Principal Component Analysis: Learning from Examples without Local Minima ». In: *Neural Networks* 2.1, pp. 53–58. ISSN: 08936080. DOI: 10.1016/0893-6080(89)90014-2 (Cited on page 100).

Banzhaf, Wolfgang, Frank D. Francone, Robert E. Keller, and Peter Nordin (1998). *Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications*. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. 470 pp. ISBN: 978-1-55860-510-7 (Cited on page 55).

Beaulieu, Shawn, Lapo Frati, Thomas Miconi, Joel Lehman, Kenneth O. Stanley, Jeff Clune, and Nick Cheney (Mar. 3, 2020). « Learning to Continually Learn ». arXiv: 2002.09571 [cs, stat] (Cited on page 32).

Beckers, Ralph, Owen E. Holland, and Jean-Louis Deneubourg (2000). « Fom Local Actions to Global Tasks: Stigmergy and Collective Robotics ». In: *Prerational Intelligence: Adaptive Behavior and Intelligent Systems Without Symbols and Logic, Volume 1, Volume 2 Prerational Intelligence: Interdisciplinary Perspectives on the Behavior of Natural and Artificial Systems, Volume 3*. Ed. by Holk Cruse, Jeffrey Dean, and Helge Ritter. Studies in Cognitive Systems. Dordrecht: Springer Netherlands, pp. 1008–1022. ISBN: 978-94-010-0870-9. DOI: 10.1007/978-94-010-0870-9_63 (Cited on page 53).

Bedau, Mark A., Nicholas Gigliotti, Tobias Janssen, Alec Kosik, Ananthan Nambiar, and Norman Packard (Apr. 1, 2019). « Open-Ended Technological Innovation ». In: *Artificial Life* 25.1, pp. 33–49. ISSN: 1064-5462. DOI: 10.1162/artl_a_00279 (Cited on page 58).

Bedau, Mark A., John S. McCaskill, Norman H. Packard, and Steen Rasmussen (2000). « A Less Abstract Artificial Chemistry ». In: *Artificial Life VII: Proceedings of the Seventh International Conference on Artificial Life*. MIT Press, pp. 49–53. ISBN: 978-0-262-29107-1 (Cited on page 61).
Bennett, Charles H. (1988). « Dissipation, Information, Computational Complexity and the Definition of Organization ». In: *Emerging Syntheses In Science*. CRC Press. ISBN: 978-0-429-49259-4 (Cited on page 49).

— (1995). « Logical Depth and Physical Complexity ». In: *The Universal Turing Machine A Half-Century Survey*. Ed. by Rolf Herken. Red. by Rolf Herken. Vol. 2. Vienna: Springer Vienna, pp. 207–235. ISBN: 978-3-211-82637-9 978-3-7091-6597-3. DOI: 10.1007/978-3-7091-6597-3_8 (Cited on pages 49, 75, 115).

Berlekamp, Elwyn R., John Horton Conway, and Richard K. Guy (2001). *Winning Ways for Your Mathematical Plays*. 2nd ed. Natick, Mass: A.K. Peters. 4 pp. ISBN: 978-1-56881-130-7 978-1-56881-142-0 978-1-56881-143-7 978-1-56881-144-4 (Cited on page 108).

Bertschinger, Nils and Thomas Natschläger (July 2004). « Real-Time Computation at the Edge of Chaos in Recurrent Neural Networks ». In: *Neural Computation* 16.7, pp. 1413–1436. ISSN: 0899-7667. DOI: 10.1162/089976604323057443. pmid: 15165396 (Cited on page 37).

Bilotta, Eleonora and Pietro Pantano (Mar. 2011). « ARTIFICIAL MICRO-WORLDS PART II: CELLULAR AUTOMATA GROWTH DYNAMICS ». In: *International Journal of Bifurcation and Chaos* 21.03, pp. 619–645. ISSN: 0218-1274, 1793-6551. DOI: 10.1142/S0218127411028672 (Cited on page 74).

Boas, Sonja E. M., Yi Jiang, Roeland M. H. Merks, Sotiris A. Prokopiou, and Elisa-
beth G. Rens (2018). « Cellular Potts Model: Applications to Vasculogenesis and
Angiogenesis ». In: *Probabilistic Cellular Automata: Theory, Applications and Future
Perspectives*. Ed. by Pierre-Yves Louis and Francesca R. Nardi. Emergence, Complex-
ity and Computation. Cham: Springer International Publishing, pp. 279–310. ISBN:
978-3-319-65558-1. DOI: 10.1007/978-3-319-65558-1_18 (Cited on page 21).

Boccara, N., J. Nasser, and M. Roger (July 1, 1991). « Particlelike Structures and Their Interactions in Spatiotemporal Patterns Generated by One-Dimensional Deterministic Cellular-Automaton Rules ». In: *Physical Review A* 44.2, pp. 866–875. ISSN: 1050-2947, 1094-1622. DOI: 10.1103/PhysRevA.44.866 (Cited on page 103).
Boccara, Nino (Sept. 9, 2010). *Modeling Complex Systems*. Springer Science & Business Media. 500 pp. ISBN: 978-1-4419-6562-2. Google Books: [boUorPmcbKMC](https://books.google.com/books?id=BOUorPmcbKMC) (Cited on pages 115, 142).

Booker, Lashon B. (2004). *Perspectives on Adaptation in Natural and Artificial Systems* (*Proceedings Volume in the Santa Fe Institute Studies in the Sciences of comPlexity*. New York, NY, USA: Oxford University Press, Inc. ISBN: 978-0-19-516293-6 (Cited on page 72).

Booker, Lashon B., David E. Goldberg, and John H. Holland (1989). « Classifier Systems and Genetic Algorithms ». In: *Artificial intelligence* 40.1-3, pp. 235–282 (Cited on pages 55, 64).

Bottou, Léon, Frank E. Curtis, and Jorge Nocedal (2018). « Optimization Methods for Large-Scale Machine Learning ». In: *Siam Review* 60.2, pp. 223–311 (Cited on page 114).

Boyd, S. and L. Chua (Nov. 1985). « Fading Memory and the Problem of Approximating Nonlinear Operators with Volterra Series ». In: *IEEE Transactions on Circuits and Systems* 32.11, pp. 1150–1161. ISSN: 1558-1276. DOI: 10.1109/TCS.1985.1085649 (Cited on page 36).

Buckman, Jacob, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee (2018). « Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion ». In: *Advances in neural information processing systems* 31 (Cited on page 116).

Buliga, Marius and Louis H. Kauffman (July 30, 2014). « Chemlambda, Universality and Self-Multiplication ». In: *Artificial Life 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems*, pp. 490–497. DOI: 10.7551/978-0-262-32621-6-ch079. arXiv: 1403.8046 [cs, math] (Cited on page 61).

Buonomano, Dean V. and Michael M. Merzenich (Feb. 17, 1995). « Temporal Information Transformed into a Spatial Code by a Neural Network with Realistic Properties ». In: *Science* 267.5200, pp. 1028–1030. ISSN: 0036-8075, 1095-9203. DOI: 10.1126/science.7863330 (Cited on page 35).
Butera, William Joseph (2002). « Programming a Paintable Computer ». PhD thesis.
USA: Massachusetts Institute of Technology (Cited on page 69).

Carlini, Nicholas (Apr. 1, 2020). *Digital Logic Gates on Conway's Game of Life - Part 1.*
URL: https://nicholas.carlini.com/writing/2020/digital-logic-game-of-life.html (visited on 11/15/2022) (Cited on page 64).

Ceccatto, H. A. and B. A. Huberman (Jan. 1988). « The Complexity of Hierarchical Systems ». In: *Physica Scripta* 37.1, p. 145. ISSN: 1402-4896. DOI: 10.1088/0031-8949/37/1/021 (Cited on page 49).

Chaitin, Gregory J (1977). « Algorithmic Information Theory ». In: *IBM journal of research and development* 21.4, pp. 350–359. ISSN: 0018-8646 (Cited on page 47).

— (Jan. 1969). « On the Length of Programs for Computing Finite Binary Sequences: Statistical Considerations ». In: *J. ACM* 16.1, pp. 145–159. ISSN: 0004-5411. DOI: 10.1145/321495.321506 (Cited on page 47).

— (Dec. 1987). « Toward a Mathematical Definition of "Life" ». In: *Information, Randomness & Incompleteness*. Vol. Volume 8. World Scientific Series in Computer Science Volume 8. WORLD SCIENTIFIC, pp. 86–104. ISBN: 978-9971-5-0479-3. DOI: 10.1142/9789814434058_0011 (Cited on page 46).

— (1990). *Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory*. Vol. 8. World Scientific (Cited on pages 44, 47, 49).

Chan, Bert Wang-Chak (May 4, 2019). « Lenia - Biology of Artificial Life ». arXiv: 1812.05433 [nlin] (Cited on page 22).

Chang, Hao-Hsuan, Hao Song, Yang Yi, Jianzhong Zhang, Haibo He, and Lingjia Liu (Apr. 2019). « Distributive Dynamic Spectrum Access Through Deep Reinforcement Learning: A Reservoir Computing-Based Approach ». In: *IEEE Internet of Things Journal* 6.2, pp. 1938–1948. ISSN: 2327-4662. DOI: 10.1109/JIOT.2018.2872441 (Cited on page 38).

Channon, Alastair (2003). « Improving and Still Passing the ALife Test: Component-normalised Activity Statistics Classify Evolution in Geb as Unbounded ». In: *Proceed-
*ings of Artificial Life VIII, Sydney, RK Standish, MA Bedau, and HA Abbass, (eds.), MIT Press: Cambridge, MA, pp. 173–181 (Cited on pages 60, 72).

Chevalier-Boisvert, Maxime, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio (2018). « Babyai: A Platform to Study the Sample Efficiency of Grounded Language Learning ». arXiv: 1810.08272 (Cited on page 116).

Cho, Kyunghyun, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio (2014). « On the Properties of Neural Machine Translation: Encoder–Decoder Approaches ». In: *Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation*, pp. 103–111 (Cited on page 124).

Cisneros, Hugo (Aug. 3, 2021). *Open-Ended Creation of Hybrid Creatures with Neural Cellular Automata*. Hugo Cisneros' blog. URL: https://hugocisneros.com/blog/open-ended-creation-of-hybrid-creatures-with-neural-cellular-automata/ (Cited on pages 67, 68).

Cisneros, Hugo, Tomas Mikolov, and Josef Sivic (Nov. 28, 2022). « Benchmarking Learning Efficiency in Deep Reservoir Computing ». In: *Proceedings of The 1st Conference on Lifelong Learning Agents*. Conference on Lifelong Learning Agents (CoLLAs 2022). Vol. 199. PMLR, pp. 532–547 (Cited on pages 11, 12).

Cisneros, Hugo, Josef Sivic, and Tomas Mikolov (Dec. 2019). « Evolving Structures in Complex Systems ». In: *2019 IEEE Symposium Series on Computational Intelligence (SSCI)*. 2019 IEEE Symposium Series on Computational Intelligence (SSCI). Xiamen, China: IEEE, pp. 230–237. ISBN: 978-1-72812-485-8. DOI: 10.1109/SSCI44817.2019.9002840 (Cited on pages 11, 12, 102, 105, 115).

— (July 1, 2020). « Visualizing Computation in Large-Scale Cellular Automata ». In: *Artificial Life Conference Proceedings*. ALife 2020. Vol. 32. MIT Press, pp. 239–247. DOI: 10.1162/isal_a_00277 (Cited on pages 11, 12, 99).

Cook, Matthew (2004). « Universality in Elementary Cellular Automata ». In: *Complex Systems*, p. 40 (Cited on pages 17, 19, 20, 108).
Coore, Daniel (1999). « Botanical Computing: A Developmental Approach to Generating Interconnect Topologies on an Amorphous Computer ». PhD thesis. Massachusetts Institute of Technology (Cited on page 70).

Crutchfield, J. P. and M. Mitchell (Nov. 7, 1995). « The Evolution of Emergent Compu-
tation. » In: *Proceedings of the National Academy of Sciences* 92.23, pp. 10742–10746.
ISSN: 0027-8424, 1091-6490. DOI: **10.1073/pnas.92.23.10742** (Cited on page **65**).

Crutchfield, James P. (Aug. 1, 1994). « The Calculi of Emergence: Computation, Dynamics and Induction ». In: *Physica D: Nonlinear Phenomena* 75.1, pp. 11–54. ISSN: 0167-2789. DOI: **10.1016/0167-2789(94)90273-9** (Cited on pages **50, 51**).

— (Jan. 2012). « Between Order and Chaos ». In: *Nature Physics* 8.1 (1), pp. 17–24.
ISSN: 1745-2481. DOI: **10.1038/nphys2190** (Cited on page **50**).

Crutchfield, James P. and James E. Hanson (Dec. 1993). « Turbulent Pattern Bases for Cellular Automata ». In: *Physica D: Nonlinear Phenomena* 69.3-4, pp. 279–301. ISSN: 01672789. DOI: **10.1016/0167-2789(93)90092-F** (Cited on pages **51, 102**).

Crutchfield, James P. and Cosma Rohilla Shalizi (1999). « Thermodynamic Depth of Causal States: Objective Complexity via Minimal Representations ». In: *Physical review E* 59.1, p. 275 (Cited on pages **50, 51**).

Crutchfield, James P. and Karl Young (July 10, 1989). « Inferring Statistical Complexity ». In: *Physical Review Letters* 63.2, pp. 105–108. ISSN: 0031-9007. DOI: **10.1103/PhysRevLett.63.105** (Cited on pages **50, 51**).

Cully, Antoine and Yiannis Demiris (2017). « Quality and Diversity Optimization: A Unifying Modular Framework ». In: *IEEE Transactions on Evolutionary Computation* 22.2, pp. 245–259 (Cited on page **56**).

Curry, Haskell B. (1958). *Combinatory Logic*. Amsterdam: North-Holland Pub. Co.
(Cited on page **61**).

Daley, R. P. (Nov. 1, 1973). « Minimal-Program Complexity of Sequences with Restricted Resources ». In: *Information and Control* 23.4, pp. 301–312. ISSN: 0019-9958. DOI: **10.1016/S0019-9958(73)80001-4** (Cited on page **48**).
Daley, Robert (June 1, 1977). « On the Inference of Optimal Descriptions ». In: *Theoretical Computer Science* 4.3, pp. 301–319. ISSN: 0304-3975. DOI: 10.1016/0304-3975(77)90015-9 (Cited on page 48).

Das, Rajarshi, Melanie Mitchell, and James P. Crutchfield (1994). « A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata ». In: *Parallel Problem Solving from Nature — PPSN III*. Ed. by Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 344–353. ISBN: 978-3-540-49001-2. DOI: 10.1007/3-540-58484-6_278 (Cited on page 65).

De Wolf, Tom and Tom Holvoet (2005). « Emergence Versus Self-Organisation: Different Concepts but Promising When Combined ». In: *Engineering Self-Organising Systems*. Ed. by Sven A. Brueckner, Giovanna Di Marzo Serugendo, Anthony Karageorgos, and Radhika Nagpal. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 1–15. ISBN: 978-3-540-31901-6. DOI: 10.1007/11494676_1 (Cited on page 52).

De Haan, J. (Dec. 1, 2006). « How Emergence Arises ». In: *Ecological Complexity*. Complexity and Ecological Economics 3.4, pp. 293–301. ISSN: 1476-945X. DOI: 10.1016/j.ecocom.2007.02.003 (Cited on page 53).

Dennett, D. C. (1996). *Darwin's Dangerous Idea: Evolution and the Meanings of Life*. 1. Touchstone ed. A Touchstone Book. New York: Simon & Schuster. 586 pp. ISBN: 978-0-684-82471-0 978-0-684-80290-9 (Cited on page 57).

Deutsch, David (1985). « Quantum Theory, the Church–Turing Principle and the Universal Quantum Computer ». In: *Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences* 400.1818, pp. 97–117 (Cited on page 49).

Di Caprio, Dung, Janusz Stafiej, Giorgio Luciano, and Laurent Arurault (2016). « 3D Cellular Automata Simulations of Intra and Intergranular Corrosion ». In: *Corrosion Science* 112, pp. 438–450 (Cited on page 22).

Dittrich, Peter, Jens Ziegler, and Wolfgang Banzhaf (July 2001). « Artificial Chemistries—A Review ». In: *Artificial Life* 7.3, pp. 225–275. ISSN: 1064-5462. DOI: 10.1162/106454601753238636 (Cited on page 61).
Dominey, P., M. Arbib, and J. P. Joseph (1995). « A Model of Corticostriatal Plasticity for Learning Oculomotor Associations and Sequences ». In: *Journal of Cognitive Neuroscience* 7.3, pp. 311–336. ISSN: 0898-929X. DOI: 10.1162/jocn.1995.7.3.311. pmid: 23961864 (Cited on page 37).

Dominey, Peter F. (Aug. 1, 1995). « Complex Sensory-Motor Sequence Learning Based on Recurrent State Representation and Reinforcement Learning ». In: *Biological Cybernetics* 73.3, pp. 265–274. ISSN: 1432-0770. DOI: 10.1007/BF00201428 (Cited on page 38).

Donahue, Colin, Cory Merkel, Qutaiba Saleh, Levs Dolgovs, Yu Kee Ooi, Dhireesha Kudithipudi, and Bryant Wysocki (May 2015). « Design and Analysis of Neuromemristive Echo State Networks with Limited-Precision Synapses ». In: *2015 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA)*. 2015 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA), pp. 1–6. DOI: 10.1109/CISDA.2015.7208623 (Cited on page 37).

Doncieux, Stéphane, Alban Laflaquière, and Alexandre Coninx (July 13, 2019). « Novelty Search: A Theoretical Perspective ». In: *Proceedings of the Genetic and Evolutionary Computation Conference*. GECCO '19: Genetic and Evolutionary Computation Conference. Prague Czech Republic: ACM, pp. 99–106. ISBN: 978-1-4503-6111-8. DOI: 10.1145/3321707.3321752 (Cited on page 56).

Dong, Jonathan, Mushegh Rafayelyan, Florent Krzakala, and Sylvain Gigan (Jan. 2020). « Optical Reservoir Computing Using Multiple Light Scattering for Chaotic Systems Prediction ». In: *IEEE Journal of Selected Topics in Quantum Electronics* 26.1, pp. 1–12. DOI: 10.1109/JSTQE.2019.2936281 (Cited on page 38).

Dyson, Freeman J. (1999). *Origins of Life*. Rev. ed. Cambridge [England] ; New York: Cambridge University Press. 100 pp. ISBN: 978-0-521-62668-2 (Cited on page 57).

Efros, A.A. and T.K. Leung (1999). « Texture Synthesis by Non-Parametric Sampling ». In: *Proceedings of the Seventh IEEE International Conference on Computer Vision*. Proceedings of the Seventh IEEE International Conference on Computer Vision.
Kerkyra, Greece: IEEE, 1033-1038 vol.2. ISBN: 978-0-7695-0164-2. DOI: 10.1109/ICCV.1999.790383 (Cited on page 80).

Eigen, Manfred and Peter Schuster (1979). *The Hypercycle*. Berlin, Heidelberg: Springer. ISBN: 978-3-540-09293-3 978-3-642-67247-7. DOI: 10.1007/978-3-642-67247-7 (Cited on page 57).

Elman, Jeffrey L. (1990). « Finding Structure in Time ». In: *Cognitive Science* 14.2, pp. 179-211. ISSN: 1551-6709. DOI: 10.1207/s15516709cog1402_1 (Cited on pages 57, 114, 124, 130).

Eloranta, Kari and Esa Nummelin (Dec. 1992). « The Kink of Cellular Automaton Rule 18 Performs a Random Walk ». In: *Journal of Statistical Physics* 69.5-6, pp. 1131-1136. ISSN: 0022-4715, 1572-9613. DOI: 10.1007/BF01058766 (Cited on page 102).

Evans, S. C., G. J. Saulnier, and Stephen F. Bush (2003). « A New Universal Two Part Code for Estimation of String Kolmogorov Complexity and Algorithmic Minimum Sufficient Statistic ». In: *DIMACS Workshop on Complexity and Inference* (Cited on page 48).

Feder, M., N. Merhav, and M. Gutman (July 1992). « Universal Prediction of Individual Sequences ». In: *IEEE Transactions on Information Theory* 38.4, pp. 1258-1270. ISSN: 1557-9654. DOI: 10.1109/18.144706 (Cited on page 48).

Feldman, David P and James P Crutchfield (Feb. 9, 1998). « Measures of Statistical Complexity: Why? » In: *Physics Letters A* 238.4, pp. 244-252. ISSN: 0375-9601. DOI: 10.1016/S0375-9601(97)00855-4 (Cited on page 50).

Flamm, Christoph, Alexander Ullrich, Heinz Ekker, Martin Mann, Daniel Högerl, Markus Rohrschneider, Sebastian Sauer, Gerik Scheuermann, Konstantin Klemm, Ivo L Hofacker, and Peter F Stadler (Dec. 2010). « Evolution of Metabolic Networks: A Computational Frame-Work ». In: *Journal of Systems Chemistry* 1.1, p. 4. ISSN: 1759-2208. DOI: 10.1186/1759-2208-1-4 (Cited on page 60).

Floyd, Robert W. and L. S. Steinberg (1976). « An Adaptive Algorithm for Spatial Gray Scale ». In: *Journal of the Society for Information Display* 17, pp. 75-77 (Cited on page 98).
Fogel, Lawrence J., Alvin J. Owens, and Michael J. Walsh (1966). *Artificial Intelligence through Simulated Evolution*. Artificial Intelligence through Simulated Evolution. Oxford, England: John Wiley & Sons, pp. xii, 170. xii, 170 (Cited on page 5).

Fontana, W and L W Buss (Jan. 18, 1994). « What Would Be Conserved If "the Tape Were Played Twice"? » In: *Proceedings of the National Academy of Sciences* 91.2, pp. 757-761. DOI: 10.1073/pnas.91.2.757 (Cited on page 61).

Gács, Peter (1986). « Reliable Computation with Cellular Automata ». In: *Journal of Computer and System Sciences* 32.1, pp. 15–78 (Cited on page 66).

— (Apr. 1, 2001). « Reliable Cellular Automata with Self-Organization ». In: *Journal of Statistical Physics* 103.1, pp. 45–267. ISSN: 1572-9613. DOI: 10.1023/A:1004823720305 (Cited on page 66).

Gandin, Ch-A. and Michel Rappaz (1997). « A 3D Cellular Automaton Algorithm for the Prediction of Dendritic Grain Growth ». In: *Acta Materialia* 45.5, pp. 2187–2195 (Cited on page 22).

Gardner, Martin (Oct. 1970). « Mathematical Games ». In: *Scientific American* 223.4, pp. 120–123. ISSN: 0036-8733. DOI: 10.1038/scientificamerican1070-120 (Cited on pages 20, 92).

Garzon, Max and Fernanda Botelho (1993). « Real Computation with Cellular Automata ». In: *Cellular Automata and Cooperative Systems*. Springer, pp. 191–202 (Cited on page 22).

Gell-Mann, Murray (1988). « Simplicity and Complexity in the Description of Nature ». In: *Engineering and Science* 51.3, pp. 2–9 (Cited on page 48).

Gepperth, Alexander and Cem Karaoguz (Oct. 1, 2016). « A Bio-Inspired Incremental Learning Architecture for Applied Perceptual Problems ». In: *Cognitive Computation* 8.5, pp. 924–934. ISSN: 1866-9964. DOI: 10.1007/s12559-016-9389-5 (Cited on page 137).

Gilpin, William (Sept. 9, 2018). « Cellular Automata as Convolutional Neural Networks ». arXiv: 1809.02942 [cond-mat, physics:nlin, physics:physics] (Cited on pages 27, 34, 66).
Glover, Tom Eivind, Pedro Lind, Anis Yazidi, Evgeny Osipov, and Stefano Nichele (2021). « The Dynamical Landscape of Reservoir Computing with Elementary Cellular Automata ». In: *ALIFE 2021: The 2021 Conference on Artificial Life*. MIT Press (Cited on page 128).

Goldberg, David E. (Jan. 1, 1987). « Simple Genetic Algorithms and the Minimal Deceptive Problem ». In: *Genetic Algorithms and Simulated Annealing*. 1st ed. Los Altos, CA: Pitman, pp. 74–88. ISBN: 978-0-273-08771-7 (Cited on page 57).

Goldstein, Jeffrey (2011). « Emergence in Complex Systems ». In: *The sage handbook of complexity and management*, pp. 65–78 (Cited on page 115).

Gomes, Jorge, Pedro Mariano, and Anders Lyhne Christensen (July 11, 2015). « Devising Effective Novelty Search Algorithms: A Comprehensive Empirical Study ». In: *Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation*. GECCO '15. New York, NY, USA: Association for Computing Machinery, pp. 943–950. ISBN: 978-1-4503-3472-3. DOI: 10.1145/2739480.2754736 (Cited on page 56).

Gomes, Jorge, Paulo Urbano, and Anders Lyhne Christensen (Sept. 1, 2013). « Evolution of Swarm Robotics Systems with Novelty Search ». In: *Swarm Intelligence* 7.2, pp. 115–144. ISSN: 1935-3820. DOI: 10.1007/s11721-013-0081-z (Cited on page 55).

Goodfellow, Ian J., Mehdi Mirza, Xia Da, Aaron C. Courville, and Yoshua Bengio (2014). « An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks ». In: *2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings*. Ed. by Yoshua Bengio and Yann LeCun (Cited on page 117).

Gosper, R.Wm. (Jan. 1984). « Exploiting Regularities in Large Cellular Spaces ». In: *Physica D: Nonlinear Phenomena* 10.1-2, pp. 75–80. ISSN: 01672789. DOI: 10.1016/0167-2789(84)90251-3 (Cited on pages 93, 95).

Grassberger, Peter (Sept. 1986). « Toward a Quantitative Theory of Self-Generated Complexity ». In: *International Journal of Theoretical Physics* 25.9, pp. 907–938. ISSN: 0020-7748, 1572-9575. DOI: 10.1007/BF00668821 (Cited on pages 43, 46, 93).
Grassberger, Peter (July 3, 1989a). « Problems in Quantifying Self-Generated Complexity ». In: *Helvetica Physica Acta* 62, pp. 489–511. DOI: 10.5169/SEALS-116045 (Cited on page 44).

— (1989b). « Randomness, Information, and Complexity ». In: *Proceedings of the 5th Mexican School on Statistical Physics*. Mexican School on Statistical Physics (EMFE). arXiv: 1208.3459 (Cited on page 75).

Graves, Alex, Greg Wayne, and Ivo Danihelka (2014). « Neural Turing Machines ». arXiv: 1410.5401 (Cited on page 116).

Grunwald, Peter (2007). *The Minimum Description Length Principle*. Adaptive Computation and Machine Learning. Cambridge, Mass: MIT Press. 703 pp. ISBN: 978-0-262-07281-6 (Cited on page 76).

Gutowitz, Howard (Dec. 1, 1995). « Cellular Automata and the Sciences of Complexity (Part I): A Review of Some Outstanding Problems in the Theory of Cellular Automata ». In: *Complexity* 1.5, pp. 16–22. ISSN: 1076-2787. DOI: 10.1002/cplx.6130010505 (Cited on page 44).

Gutowitz, Howard A. (1991). « Transients, Cycles, and Complexity in Cellular Automata ». In: *Physical Review A* 44.12, R7881 (Cited on page 19).

Gutowitz, Howard A. and Christopher G. Langton (1988). « Methods for Designing Cellular Automata with” Interesting” Behavior ». In: *CNLS News Letter* (Cited on page 46).

Hammerschmidt, Katrin, Caroline J. Rose, Benjamin Kerr, and Paul B. Rainey (Nov. 2014). « Life Cycles, Fitness Decoupling and the Evolution of Multicellularity ». In: *Nature* 515.7525, pp. 75–79. ISSN: 0028-0836, 1476-4687. DOI: 10.1038/nature13884 (Cited on page 5).

Hamming, R. W. (Apr. 1950). « Error Detecting and Error Correcting Codes ». In: *Bell System Technical Journal* 29.2, pp. 147–160. ISSN: 00058580. DOI: 10.1002/j.1538-7305.1950.tb00463.x (Cited on page 100).
Hanson, James E. and James P. Crutchfield (Mar. 1992). « The Attractor-Basin Portrait of a Cellular Automaton ». In: *Journal of Statistical Physics* 66.5-6, pp. 1415-1462. ISSN: 0022-4715, 1572-9613. DOI: 10.1007/BF01054429 (Cited on pages 95, 102-104).

— (Apr. 15, 1997). « Computational Mechanics of Cellular Automata: An Example ». In: *Physica D: Nonlinear Phenomena*. Lattice Dynamics 103.1, pp. 169-189. ISSN: 0167-2789. DOI: 10.1016/S0167-2789(96)00259-X (Cited on pages 51, 95, 102, 103, 106).

Harao, Masateru and Shoichi Noguchi (1973). « A Consideration on Cellular Automata with Errors ». In: *Committee on Automaton, IECE Japan, AL* 73, p. 15 (Cited on page 66).

— (Oct. 1, 1975). « Fault Tolerant Cellular Automata ». In: *Journal of Computer and System Sciences* 11.2, pp. 171-185. ISSN: 0022-0000. DOI: 10.1016/S0022-0000(75)80066-3 (Cited on page 66).

Hasslacher, Brosl (1987). « Discrete Fluids ». In: *Los Alamos Science* (Special Issue), pp. 175-217 (Cited on page 53).

Hauser, Helmut, Auke J. Ijspeert, Rudolf M. Füchslin, Rolf Pfeifer, and Wolfgang Maass (Dec. 1, 2011). « Towards a Theoretical Foundation for Morphological Computation with Compliant Bodies ». In: *Biological Cybernetics* 105.5, pp. 355-370. ISSN: 1432-0770. DOI: 10.1007/s00422-012-0471-0 (Cited on page 37).

Herel, David, Dominika Zogatova, Matej Kripner, and Tomas Mikolov (July 18, 2022). « Emergence of Novelty in Evolutionary Algorithms ». In: *ALIFE 2022: The 2022 Conference on Artificial Life*. MIT Press. DOI: 10.1162/isal_a_00501 (Cited on page 57).

Hinton, Geoffrey E. (Sept. 1989). « Connectionist Learning Procedures ». In: *Artificial Intelligence* 40.1-3, pp. 185-234. ISSN: 00043702. DOI: 10.1016/0004-3702(89)90049-0 (Cited on page 100).

Hinton, Geoffrey E. and David C. Plaut (1987). « Using Fast Weights to Deblur Old Memories ». In: *Proceedings of the Ninth Annual Conference of the Cognitive Science Society*, pp. 177-186 (Cited on page 137).
Hinton, Geoffrey E. and Terrence J. Sejnowski (May 24, 1999). *Unsupervised Learning: Foundations of Neural Computation*. MIT Press. 420 pp. ISBN: 978-0-262-58168-4. Google Books: [yj04Y0lje4cC](https://books.google.com/books?id=yj04Y0lje4cC) (Cited on page 3).

Hochreiter, Sepp and Jürgen Schmidhuber (Nov. 1, 1997). « Long Short-Term Memory ». In: *Neural Computation* 9.8, pp. 1735–1780. ISSN: 0899-7667. DOI: [10.1162/neco.1997.9.8.1735](https://doi.org/10.1162/neco.1997.9.8.1735) (Cited on pages 114, 116, 117, 124, 130, 135).

Holland, John H. (1992). *Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence*. 1st MIT Press ed. Complex Adaptive Systems. Cambridge, Mass: MIT Press. 211 pp. ISBN: 978-0-262-08213-6 978-0-262-58111-0 (Cited on page 57).

— (2000). *Emergence: From Chaos to Order*. Oxford University Press. 276 pp. ISBN: 978-0-19-286211-2. Google Books: [VjKtpujRGuAC](https://books.google.com/books?id=VjKtpujRGuAC) (Cited on page 53).

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman (2007). *Introduction to Automata Theory, Languages, and Computation*. 3rd ed. Boston: Pearson/Addison Wesley. 535 pp. ISBN: 978-0-321-45536-9 978-0-321-46225-1 978-0-321-45537-6 (Cited on page 47).

Hudcová, Barbora and Tomas Mikolov (July 1, 2020). « Classification of Complex Systems Based on Transients ». In: ALIFE 2020: The 2020 Conference on Artificial Life. MIT Press, pp. 367–375. DOI: [10.1162/isal_a_00260](https://doi.org/10.1162/isal_a_00260) (Cited on pages 18, 19).

— (July 19, 2021). « Computational Hierarchy of Elementary Cellular Automata ». In: ALIFE 2021: The 2021 Conference on Artificial Life. MIT Press. DOI: [10.1162/isal_a_00447](https://doi.org/10.1162/isal_a_00447) (Cited on page 19).

— (Mar. 16, 2022). « Classification of Discrete Dynamical Systems Based on Transients ». In: *Artificial Life* 27.3–4, pp. 220–245. ISSN: 1064-5462. DOI: [10.1162/artl_a_00342](https://doi.org/10.1162/artl_a_00342) (Cited on page 18).

Hutton, Tim J. (Jan. 2007). « Evolvable Self-Reproducing Cells in a Two-Dimensional Artificial Chemistry ». In: *Artificial Life* 13.1, pp. 11–30. ISSN: 1064-5462, 1530-9185. DOI: [10.1162/artl.2007.13.1.11](https://doi.org/10.1162/artl.2007.13.1.11) (Cited on page 60).
*Igblan - Life Universal Computer* (2022). URL: http://www.igblan.free-online.co.uk/igblan/ca/ (visited on 11/02/2022) (Cited on page 20).

Ikegami, Takashi, Yasuhiro Hashimoto, and Mizuki Oka (2019). « Open-Ended Evolution and a Mechanism of Novelties in Web Services ». In: *Artificial Life* 25.2, pp. 168–177. ISSN: 1530-9185. DOI: 10.1162/artl_a_00287. pmid: 31150293 (Cited on page 58).

Ilachinski, Andrew (July 3, 2001). *Cellular Automata: A Discrete Universe*. World Scientific Publishing Company. 842 pp. ISBN: 978-981-310-256-9. Google Books: BPY7DQAAQBAJ (Cited on page 27).

Ingólfsson, Helgi I., Cesar A. Lopez, Jaakko J. Uusitalo, Djurre H. de Jong, Srinivasa M. Gopal, Xavier Periole, and Siewert J. Marrink (May 2014). « The Power of Coarse Graining in Biomolecular Simulations ». In: *Wiley Interdisciplinary Reviews: Computational Molecular Science* 4.3, pp. 225–248. ISSN: 17590876. DOI: 10.1002/wcms.1169 (Cited on page 94).

Ishiguro, Akio, Akinobu Fujii, and Peter Eggenberger Hotz (Mar. 1, 2003). « Neuromodulated Control of Bipedal Locomotion Using a Polymorphic CPG Circuit ». In: *Adaptive Behavior* 11.1, pp. 7–17. ISSN: 1059-7123. DOI: 10.1177/10597123030111001 (Cited on page 32).

Israeli, Navot and Nigel Goldenfeld (Feb. 20, 2004). « On Computational Irreducibility and the Predictability of Complex Physical Systems ». In: *Physical Review Letters* 92.7, p. 074105. ISSN: 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.92.074105. arXiv: nlin/0309047 (Cited on page 94).

— (Feb. 6, 2006). « Coarse-Graining of Cellular Automata, Emergence, and the Predictability of Complex Systems ». In: *Physical Review E* 73.2, p. 026203. ISSN: 1539-3755, 1550-2376. DOI: 10.1103/PhysRevE.73.026203. arXiv: nlin/0508033 (Cited on page 94).

Jaeger, Herbert (2001). « The “Echo State” Approach to Analysing and Training Recurrent Neural Networks-with an Erratum Note ». In: *Bonn, Germany: German National Research Center for Information Technology GMD Technical Report* 148.34, p. 13 (Cited on pages 36, 38, 115, 126, 135).
Jaeger, Herbert (Jan. 1, 2002). « Adaptive Nonlinear System Identification with Echo State Networks ». In: *Proceedings of the 15th International Conference on Neural Information Processing Systems*. NIPS'02. Cambridge, MA, USA: MIT Press, pp. 609–616 (Cited on page 38).

— (Feb. 1, 2012). *Long Short-Term Memory in Echo State Networks: Details of a Simulation Study*. Jacobs University Bremen (Cited on pages 39, 40, 126).

Jalalvand, Azarakhsh, Glenn Van Wallendael, and Rik Van De Walle (June 2015). « Real-Time Reservoir Computing Network-Based Systems for Detection Tasks on Visual Contents ». In: *2015 7th International Conference on Computational Intelligence, Communication Systems and Networks*. 2015 7th International Conference on Computational Intelligence, Communication Systems and Networks, pp. 146–151. DOI: 10.1109/CICSyN.2015.35 (Cited on page 38).

Jennings, N. R. (1999). « Agent-Based Computing: Promise and Perils ». In: 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (01/01/99). In collab. with N. R. Jennings, pp. 1429–1436 (Cited on page 62).

Johnson, Neil F. (2009). *Simply Complexity: A Clear Guide to Complexity Theory*. Oxford: Oneworld. 236 pp. ISBN: 978-1-85168-630-8 (Cited on page 59).

Jordan, Michael I. (1997). « Serial Order: A Parallel Distributed Processing Approach ». In: *Advances in Psychology*. Vol. 121. Elsevier, pp. 471–495. ISBN: 978-0-444-81931-4. DOI: 10.1016/S0166-4115(97)80111-2 (Cited on page 57).

Joulin, Armand and Tomas Mikolov (Dec. 7, 2015). « Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets ». In: *Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1*. NIPS'15. Cambridge, MA, USA: MIT Press, pp. 190–198 (Cited on page 117).

Kanazawa, Satoshi (2004). « General Intelligence as a Domain-Specific Adaptation. » In: *Psychological review* 111.2, p. 512 (Cited on page 114).

Kanno, Kazutaka and Atsushi Uchida (Mar. 8, 2022). « Photonic Reinforcement Learning Based on Optoelectronic Reservoir Computing ». In: *Scientific Reports* 12.1 (1), p. 3720. ISSN: 2045-2322. DOI: 10.1038/s41598-022-07404-z (Cited on page 38).
Kari, Jarkko J. (2012). « Basic Concepts of Cellular Automata ». In: *Handbook of Natural Computing*. Ed. by Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok. Berlin, Heidelberg: Springer, pp. 3–24. ISBN: 978-3-540-92910-9. DOI: 10.1007/978-3-540-92910-9_1 (Cited on page 16).

Kauffman, Stuart (1995). *At Home in the Universe: The Search for Laws of Self-organization and Complexity*. Oxford University Press. 348 pp. ISBN: 978-0-19-509599-9 (Cited on page 53).

Kelly, David, Mark Dillingham, Andrew Hudson, and Karoline Wiesner (2012). « A New Method for Inferring Hidden Markov Models from Noisy Time Sequences ». In: *PloS One* 7.1, e29703. ISSN: 1932-6203. DOI: 10.1371/journal.pone.0029703. pmid: 22247783 (Cited on page 51).

Kingma, Diederik P. and Jimmy Ba (2015). « Adam: A Method for Stochastic Optimization ». In: *3rd International Conference on Learning Representations, ICLR 2015*, *San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings*. Ed. by Yoshua Bengio and Yann LeCun (Cited on pages 125, 130, 131, 133).

Kirby, Kevin G. (1991). « Context Dynamics in Neural Sequential Learning ». In: *Proc. Florida AI Research Symposium (FLAIRS) 1991*. Florida AI Research Symposium, pp. 66–70 (Cited on page 35).

Kistemaker, Steijn and Shimon Whiteson (July 12, 2011). « Critical Factors in the Performance of Novelty Search ». In: *Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation*. GECCO ’11. New York, NY, USA: Association for Computing Machinery, pp. 965–972. ISBN: 978-1-4503-0557-0. DOI: 10.1145/2001576.2001708 (Cited on page 56).

Kitayama, Ken-ichi, Masaya Notomi, Makoto Naruse, Koji Inoue, Satoshi Kawakami, and Atsushi Uchida (Sept. 9, 2019). « Novel Frontier of Photonics for Data Processing—Photonic Accelerator ». In: *APL Photonics* 4.9, p. 090901. DOI: 10.1063/1.5108912 (Cited on page 38).

Kleyko, Denis, E. Paxon Frady, and Friedrich T. Sommer (Oct. 7, 2020). « Cellular Automata Can Reduce Memory Requirements of Collective-State Computing ». arXiv: 2010.03585 [cs] (Cited on page 40).
Kmiecik, Sebastian, Dominik Gront, Michal Kolinski, Lukasz Wieteska, Aleksandra Elzbieta Dawid, and Andrzej Kolinski (July 27, 2016). « Coarse-Grained Protein Models and Their Applications ». In: *Chemical Reviews* 116.14, pp. 7898–7936. ISSN: 0009-2665, 1520-6890. DOI: 10.1021/acs.chemrev.6b00163 (Cited on page 94).

Ko, Ker-I (Jan. 1, 1986). « On the Notion of Infinite Pseudorandom Sequences ». In: *Theoretical Computer Science* 48, pp. 9–33. ISSN: 0304-3975. DOI: 10.1016/0304-3975(86)90081-2 (Cited on page 48).

Kolmogorov, A. N. (Jan. 1968). « Three Approaches to the Quantitative Definition of Information ». In: *International Journal of Computer Mathematics* 2.1-4, pp. 157–168. ISSN: 0020-7160, 1029-0265. DOI: 10.1080/00207166808803030 (Cited on pages 47, 77).

Koppel, Moshe (1988). « Structure ». In: *The Universal Turing Machine: A Half-Century Survey*. R. Herken. Vol. 2. Oxford University Press, pp. 403–419. ISBN: 978-3-211-82637-9 (Cited on page 51).

Koppel, Moshe and Henri Atlan (Aug. 1, 1991). « An Almost Machine-Independent Theory of Program-Length Complexity, Sophistication, and Induction ». In: *Information Sciences* 56.1, pp. 23–33. ISSN: 0020-0255. DOI: 10.1016/0020-0255(91)90021-L (Cited on pages 51, 115).

Kowaliw, Taras (2008). « Measures of Complexity for Artificial Embryogeny ». In: *Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation - GECCO '08*. The 10th Annual Conference. Atlanta, GA, USA: ACM Press, p. 843. ISBN: 978-1-60558-130-9. DOI: 10.1145/1389095.1389259 (Cited on page 76).

Koza, J (1992). « Evolution of Subsumption Using Genetic Programming ». In: *Proc. First European Conference on Artificial Life Towards a Practice of Autonomous Systems, 1992*. European Conference on Artificial Life Towards a Practice of Autonomous Systems. MIT Press (Cited on page 65).

Koza, John R. (June 1, 1994). « Genetic Programming as a Means for Programming Computers by Natural Selection ». In: *Statistics and Computing* 4.2, pp. 87–112. ISSN: 1573-1375. DOI: 10.1007/BF00175355 (Cited on page 55).
Kramer, Mark A. (Feb. 1991). « Nonlinear Principal Component Analysis Using Autoas-sociative Neural Networks ». In: *AIChE Journal* 37.2, pp. 233–243. ISSN: 0001-1541, 1547-5905. DOI: 10.1002/aic.690370209 (Cited on page 100).

Krizhevsky, Alex and Geoffrey E. Hinton (2009). *Learning Multiple Layers of Features from Tiny Images*. University of Toronto (Cited on page 117).

Kruszewski, Germán and Tomas Mikolov (Mar. 16, 2022). « Emergence of Self-Reproducing Metabolisms as Recursive Algorithms in an Artificial Chemistry ». In: *Artificial Life* 27.3-4, pp. 277–299. ISSN: 1064-5462. DOI: 10.1162/artl_a_00355 (Cited on page 61).

Langdon, William B. and Riccardo Poli (2002). *Foundations of Genetic Programming*. Berlin, Heidelberg: Springer. ISBN: 978-3-642-07632-9 978-3-662-04726-2. DOI: 10.1007/978-3-662-04726-2 (Cited on page 55).

Langton, Christopher G. (Jan. 1, 1984). « Self-Reproduction in Cellular Automata ». In: *Physica D: Nonlinear Phenomena* 10.1, pp. 135–144. ISSN: 0167-2789. DOI: 10.1016/0167-2789(84)90256-2 (Cited on pages 60, 73, 92).

— (Oct. 1, 1986). « Studying Artificial Life with Cellular Automata ». In: *Physica D: Nonlinear Phenomena*. Proceedings of the Fifth Annual International Conference 22.1, pp. 120–149. ISSN: 0167-2789. DOI: 10.1016/0167-2789(86)90237-X (Cited on pages 23, 53).

— ed. (1989). *Artificial Life: The Proceedings of an Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems*, Held September, 1987, in Los Alamos, New Mexico. Santa Fe Institute Studies in the Sciences of Complexity v. 6. Redwood City, Calif: Addison-Wesley Pub. Co., Advanced Book Program. 655 pp. ISBN: 978-0-201-09346-9 978-0-201-09356-8 (Cited on page 57).

— (June 1990). « Computation at the Edge of Chaos: Phase Transitions and Emergent Computation ». In: *Physica D: Nonlinear Phenomena* 42.1-3, pp. 12–37. ISSN: 0167-2789. DOI: 10.1016/0167-2789(90)90064-V (Cited on pages 8, 23, 45, 73, 87).
« Editor's Introduction » (Oct. 1993). In: *Artificial Life* 1 (1_2). Ed. by Christopher G. Langton, pp. v-viii. ISSN: 1064-5462, 1530-9185. DOI: 10.1162/artl.1993.1.1_2.v (Cited on page 71).

Lawrence, Peter A. (1992). *The Making of a Fly: The Genetics of Animal Design*. Oxford [England] ; Cambridge, Mass., USA: Blackwell Science. 228 pp. ISBN: 978-0-632-03048-4 (Cited on page 70).

Legenstein, Robert and Wolfgang Maass (Apr. 1, 2007). « Edge of Chaos and Prediction of Computational Performance for Neural Circuit Models ». In: *Neural Networks*. Echo State Networks and Liquid State Machines 20.3, pp. 323-334. ISSN: 0893-6080. DOI: 10.1016/j.neunet.2007.04.017 (Cited on page 37).

Lehman, Joel and Kenneth O. Stanley (July 7, 2010). « Efficiently Evolving Programs through the Search for Novelty ». In: *Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation*. GECCO '10. New York, NY, USA: Association for Computing Machinery, pp. 837-844. ISBN: 978-1-4503-0072-8. DOI: 10.1145/1830483.1830638 (Cited on page 56).

— (June 2011a). « Abandoning Objectives: Evolution Through the Search for Novelty Alone ». In: *Evolutionary Computation* 19.2, pp. 189-223. ISSN: 1063-6560, 1530-9304. DOI: 10.1162/EVCO_a_00025 (Cited on pages 53, 55, 56).

— (2011b). « Evolving a Diversity of Virtual Creatures through Novelty Search and Local Competition ». In: *Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation*, pp. 211-218 (Cited on page 53).

Lempel, A. and J. Ziv (Jan. 1976). « On the Complexity of Finite Sequences ». In: *IEEE Transactions on Information Theory* 22.1, pp. 75-81. ISSN: 0018-9448. DOI: 10.1109/TIT.1976.1055501 (Cited on pages 48, 74).

Levitt, Michael and Arieh Warshel (Feb. 1975). « Computer Simulation of Protein Folding ». In: *Nature* 253.5494, pp. 694-698. ISSN: 0028-0836, 1476-4687. DOI: 10.1038/253694a0 (Cited on page 94).

Li, Wentian and Norman H. Packard (1990). « The Structure of the Elementary Cellular Automata Rule Space ». In: *Complex Systems* 4.3, p. 17 (Cited on page 17).
Li, Wentian, Norman H. Packard, and Christopher G. Langton (Sept. 2, 1990). « Transition Phenomena in Cellular Automata Rule Space ». In: *Physica D: Nonlinear Phenomena* 45.1, pp. 77–94. ISSN: 0167-2789. DOI: 10.1016/0167-2789(90)90175-0 (Cited on pages 46, 73).

Liapis, Antonios, Georgios N. Yannakakis, and Julian Togelius (Mar. 1, 2015). « Constrained Novelty Search: A Study on Game Content Generation ». In: *Evolutionary Computation* 23.1, pp. 101–129. ISSN: 1063-6560. DOI: 10.1162/EVCO_a_00123 (Cited on page 56).

Lindgren, Kristian and Mats G. Nordahl (1988). « Complexity Measures and Cellular Automata ». In: p. 32 (Cited on page 46).

Lloyd, Seth and Heinz Pagels (Nov. 1, 1988). « Complexity as Thermodynamic Depth ». In: *Annals of Physics* 188, pp. 186–213. ISSN: 0003-4916. DOI: 10.1016/0003-4916(88)90094-2 (Cited on pages 49, 50).

Lorenz, Dirk M., Alice Jeng, and Michael W. Deem (June 2011). « The Emergence of Modularity in Biological Systems ». In: *Physics of life reviews* 8.2, pp. 129–160. ISSN: 1571-0645. DOI: 10.1016/j.plrev.2011.02.003. pmid: 21353651 (Cited on page 5).

Lukoševičius, Mantas and Herbert Jaeger (2009). « Reservoir Computing Approaches to Recurrent Neural Network Training ». In: *Computer Science Review* 3.3, pp. 127–149 (Cited on page 36).

LuValle, Brian J. (Mar. 28, 2019). « The Effects of Boundary Conditions on Cellular Automata ». In: *Complex Systems* 28.1, pp. 97–124. ISSN: 08912513. DOI: 10.25088/ComplexSystems.28.1.97 (Cited on page 75).

Maas, Andrew L., Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts (2011). « Learning Word Vectors for Sentiment Analysis ». In: *The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA*. Ed. by Dekang Lin, Yuji Matsumoto, and Rada Mihalcea. The Association for Computer Linguistics, pp. 142–150 (Cited on pages 115, 116).
Maass, Wolfgang, Thomas Natschläger, and Henry Markram (Nov. 1, 2002). « Real-Time Computing Without Stable States: A New Framework for Neural Computation Based on Perturbations ». In: *Neural Computation* 14.11, pp. 2531–2560. ISSN: 0899-7667, 1530-888X. DOI: 10.1162/089976602760407955 (Cited on pages 36, 124).

— (2004). « Fading Memory and Kernel Properties of Generic Cortical Microcircuit Models ». In: *Journal of Physiology, Paris* 98.4-6, pp. 315–330. ISSN: 0928-4257. DOI: 10.1016/j.jphysparis.2005.09.020. pmid: 16310350 (Cited on page 37).

Mahoney, Matthew V (2000). « Fast Text Compression with Neural Networks ». In: *FLAIRS*. FLAIRS Conference, p. 5 (Cited on pages 74, 80).

Maley, C. C. (July 13, 1999). « Four Steps toward Open-Ended Evolution ». In: *Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 2*. GECCO’99. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., pp. 1336–1343. ISBN: 978-1-55860-611-1 (Cited on page 58).

Margem, Mrwan and Osman Gedik (Dec. 17, 2018). « Reservoir Computing Based on Cellular Automata (ReCA) in Sequence Learning ». In: *Journal of cellular automata* 14, pp. 153–170 (Cited on page 40).

Margem, Mrwan and Ozgür Yilmaz (2017). *An Experimental Study on Cellular Automata Reservoir in Pathological Sequence Learning Tasks*. Jul (Cited on page 40).

Martinenghi, Romain, Sergei Rybalko, Maxime Jacquot, Yanne K. Chembo, and Laurent Larger (June 15, 2012). « Photonic Nonlinear Transient Computing with Multiple-Delay Wavelength Dynamics ». In: *Physical Review Letters* 108.24, p. 244101. DOI: 10.1103/PhysRevLett.108.244101 (Cited on page 38).

Martinez, Genaro J., Andrew Adamatzky, and Harold V. McIntosh (Oct. 8, 2014). « Complete Characterization of Structure of Rule 54 ». In: *Complex Systems* 23.3. ISSN: 0891-2513 (Cited on page 103).

Mason, A, A Nicoll, and K Stratford (Jan. 1, 1991). « Synaptic Transmission between Individual Pyramidal Neurons of the Rat Visual Cortex in Vitro ». In: *The Journal of Neuroscience* 11.1, pp. 72–84. ISSN: 0270-6474, 1529-2401. DOI: 10.1523/JNEUROSCI.11-01-00072.1991 (Cited on page 35).
McDonald, Nathan (May 2017). « Reservoir Computing & Extreme Learning Machines Using Pairs of Cellular Automata Rules ». In: *2017 International Joint Conference on Neural Networks (IJCNN)*. 2017 International Joint Conference on Neural Networks (IJCNN), pp. 2429–2436. DOI: 10.1109/IJCNN.2017.7966151 (Cited on page 41).

McMullin, Barry and Francisco J. Varela (1997). « Rediscovering Computational Autopoiesis ». In: *Fourth European Conference on Artificial Life*, pp. 38–47 (Cited on page 62).

Merkel, Cory, Qutaiba Saleh, Colin Donahue, and Dhireesha Kudithipudi (Jan. 1, 2014).
« Memristive Reservoir Computing Architecture for Epileptic Seizure Detection ». In: *Procedia Computer Science*. 5th Annual International Conference on Biologically Inspired Cognitive Architectures, 2014 BICA 41, pp. 249–254. ISSN: 1877-0509. DOI: 10.1016/j.procs.2014.11.110 (Cited on page 37).

Mikolov, Tomas, Armand Joulin, and Marco Baroni (2018). « A Roadmap Towards Machine Intelligence ». In: *Computational Linguistics and Intelligent Text Processing*. Ed. by Alexander Gelbukh. Lecture Notes in Computer Science. Cham: Springer International Publishing, pp. 29–61. ISBN: 978-3-319-75477-2. DOI: 10.1007/978-3-319-75477-2_2 (Cited on page 71).

Miller, Geoffrey F., Peter M. Todd, and Shailesh U. Hegde (1989). « Designing Neural Networks Using Genetic Algorithms. » In: *ICGA*. Vol. 89, pp. 379–384 (Cited on page 5).

Minsky, Marvin and Seymour A. Papert (1972). *Perceptrons: An Introduction to Computational Geometry*. 2nd edition. Cambridge MA: The MIT Press. ISBN: 0-262-63022-2.
DOI: 10.7551/mitpress/11301.001.0001 (Cited on page 116).

Mitchell, Melanie (Jan. 24, 2005). « Computation in Cellular Automata: A Selected Review ». In: *Gramß, Tino, Stefan Bornholdt, Michael Groß, Melanie Mitchell, and Thomas Pellizzari. Non-Standard Computation*. Weinheim, FRG: Wiley-VCH Verlag GmbH & Co. KGaA, pp. 95–140. ISBN: 978-3-527-60296-4. DOI: 10.1002/3527602968.ch4 (Cited on page 33).

Mitchell, Melanie, James P Crutchfield, and Rajarshi Das (1996). « Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work ». In: *Proceedings of*
*the First International Conference on Evolutionary Computation and Its Applications.*
First International Conference on Evolutionary Computation and Its Applications (EvCA '96). Moscow, Russia, p. 14 (Cited on pages 53, 64, 65, 108, 145).

Mitchell, Melanie, James P. Crutchfield, and Peter T. Hraber (Aug. 1, 1994). « Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments ». In: *Physica D: Nonlinear Phenomena* 75.1, pp. 361–391. ISSN: 0167-2789. DOI: 10.1016/0167-2789(94)90293-3 (Cited on page 65).

Mitchell, Melanie, Peter Hraber, and James P. Crutchfield (Mar. 31, 1993). « Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations ». arXiv: adap-org/9303003 (Cited on page 65).

Morán, Alejandro, Christiam F. Frasser, and Josep L. Rosselló (June 21, 2018). « Rese-
voir Computing Hardware with Cellular Automata ». arXiv: 1806.04932 [nlin]
(Cited on page 41).

Mordvintsev, Alexander, Ettore Randazzo, Eyvind Niklasson, and Michael Levin (Feb. 11, 2020). « Growing Neural Cellular Automata ». In: *Distill* 5.2, e23. ISSN: 2476-0757. DOI: 10.23915/distill.00023 (Cited on pages 22, 27, 28, 32, 34, 66).

Moree, Pieter and Herman J. J. te Riele (2004). « The Hexagonal versus the Square Lattice ». In: *Mathematics of Computation* 73.245, pp. 451–473. ISSN: 0025-5718. JSTOR: 4099880 (Cited on page 23).

Moreno, Matthew Andres and Charles Ofria (May 1, 2019). « Toward Open-Ended Fraternal Transitions in Individuality ». In: *Artificial Life* 25.2, pp. 117–133. ISSN: 1064-5462. DOI: 10.1162/artl_a_00284 (Cited on page 58).

Mota, Francisco, Scott Aaronson, Luís Antunes, and André Souto (2013). « Sophistication as Randomness Deficiency ». In: *Descriptional Complexity of Formal Systems*. Ed. by Helmut Jurgensen and Rogério Reis. Red. by David Hutchison et al. Vol. 8031. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 172–181. ISBN: 978-3-642-39309-9 978-3-642-39310-5. DOI: 10.1007/978-3-642-39310-5_17 (Cited on pages 51, 52).
Mouret, Jean-Baptiste and Stéphane Doncieux (2012). « Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study ». In: *Evolutionary Computation* 20.1, pp. 91–133. DOI: 10.1162/EVCO_a_00048 (Cited on pages 56, 57).

Müller-Schloer, Christian, ed. (2011). *Organic Computing: A Paradigm Shift for Complex Systems*. Autonomic Systems. Basel: Birkhäuser. 627 pp. ISBN: 978-3-0348-0129-4 (Cited on page 62).

Nagpal, Radhika (2001). « Programmable Self-Assembly: Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics ». PhD thesis. USA: Massachusetts Institute of Technology. 1 p. (Cited on page 69).

— (July 15, 2002). « Programmable Self-Assembly Using Biologically-Inspired Multiagent Control ». In: *Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 1*. AAMAS ’02. New York, NY, USA: Association for Computing Machinery, pp. 418–425. ISBN: 978-1-58113-480-3. DOI: 10.1145/544741.544839 (Cited on pages 62, 70).

— (2008). « Programmable Pattern-Formation and Scale-Independence ». In: *Unifying Themes in Complex Systems IV*. Ed. by Ali A. Minai and Yaneer Bar-Yam. Berlin, Heidelberg: Springer, pp. 275–282. ISBN: 978-3-540-73849-7. DOI: 10.1007/978-3-540-73849-7_31 (Cited on page 62).

Nakane, Ryosho, Gouhei Tanaka, and Akira Hirose (2018). « Reservoir Computing With Spin Waves Excited in a Garnet Film ». In: *IEEE Access* 6, pp. 4462–4469. ISSN: 2169-3536. DOI: 10.1109/ACCESS.2018.2794584 (Cited on page 38).

Nehaniv, Chrystopher L. (2003). « Evolution in Asynchronous Cellular Automata ». In: *Proceedings of the Eighth International Conference on Artificial Life*, pp. 65–73 (Cited on page 21).

Neumann, J. von (Dec. 31, 1956). « Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components ». In: *Automata Studies. (AM-34)*. Ed. by C. E. Shannon and J. McCarthy. Princeton University Press, pp. 43–98. ISBN: 978-1-4008-82618-003 (Cited on page 66).
Ng, Andrew Y., Michael I. Jordan, and Yair Weiss (Jan. 3, 2001). « On Spectral Clustering: Analysis and an Algorithm ». In: *Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic*. NIPS'01. Cambridge, MA, USA: MIT Press, pp. 849–856 (Cited on page 116).

Nguyen, Cuong V., Yingzhen Li, Thang D. Bui, and Richard E. Turner (2017). « Variational Continual Learning ». In: *CoRR abs/1710.10628*. arXiv: 1710.10628 (Cited on page 117).

Nichele, Stefano and Magnus S. Gundersen (Feb. 13, 2017). « Reservoir Computing Using Non-Uniform Binary Cellular Automata ». arXiv: 1702.03812 [cs] (Cited on pages 41, 127).

Nichele, Stefano and Andreas Molund (2017a). « Deep Learning with Cellular Automaton-Based Reservoir Computing ». In: *0891-2513*. ISSN: 0891-2513. DOI: http://dx.doi.org/10.25088/ComplexSystems.26.4.319 (Cited on pages 41, 127).

— (Mar. 8, 2017b). « Deep Reservoir Computing Using Cellular Automata ». arXiv: 1703.02806 [cs] (Cited on page 41).

Niklasson, Eyvind, Alexander Mordvintsev, Ettore Randazzo, and Michael Levin (Feb. 11, 2021). « Self-Organising Textures ». In: *Distill* 6.2, e00027–003. DOI: 10.23915/distill.00027.003 (Cited on page 67).

Nishio, Hidenosuke and Youichi Kobuchi (Oct. 1, 1975). « Fault Tolerant Cellular Spaces ». In: *Journal of Computer and System Sciences* 11.2, pp. 150–170. ISSN: 0022-0000. DOI: 10.1016/S0022-0000(75)80065-1 (Cited on page 66).

Ofria, Charles and Claus O. Wilke (2004). « Avida: A Software Platform for Research in Computational Evolutionary Biology ». In: *Artificial Life* 10.2, pp. 191–229. ISSN: 1064-5462. DOI: 10.1162/106454604773563612. pmid: 15107231 (Cited on pages 60, 72).

Ostrovsky, B., G. Crooks, M. A. Smith, and Y. Bar-Yam (Apr. 1, 2001). « Cellular Automata for Polymer Simulation with Application to Polymer Melts and Polymer Collapse Including Implications for Protein Folding ». In: *Parallel Computing*. Cel-
lular Automata: From Modeling to Applications 27.5, pp. 613–641. ISSN: 0167-8191.
DOI: 10.1016/S0167-8191(00)00081-8 (Cited on page 61).

Ottavi, H. and O. Parodi (Apr. 1989). « Simulation of the Ising Model by Cellular Automata ». In: *Europhysics Letters (EPL)* 8.8, pp. 741–746. ISSN: 0295-5075. DOI: 10.1209/0295-5075/8/8/006 (Cited on page 21).

Packard, Norman, Mark A. Bedau, Alastair Channon, Takashi Ikegami, Steen Rasmussen, Kenneth O. Stanley, and Tim Taylor (May 1, 2019). « An Overview of Open-Ended Evolution: Editorial Introduction to the Open-Ended Evolution II Special Issue ». In: *Artificial Life* 25.2, pp. 93–103. ISSN: 1064-5462. DOI: 10.1162/artl_a_00291 (Cited on page 57).

Packard, Norman H and Stephen Wolfram (1985). « Two-Dimensional Cellular Automata ». In: *Journal of Statistical Physics* 38.5/6, p. 46 (Cited on page 73).

Packard, Norman H. (1988). « Adaptation toward the Edge of Chaos ». In: *Dynamic patterns in complex systems* 212, pp. 293–301 (Cited on page 64).

Packel, Edward W. and Henryk Woźniakowski (1987). « Recent Developments in Information-Based Complexity ». In: *Bulletin of the American Mathematical Society* 17.1, pp. 9–36. ISSN: 0273-0979, 1088-9485. DOI: 10.1090/S0273-0979-1987-15511-X (Cited on page 47).

Pan, Peng-Zhi, Xia-Ting Feng, and John A. Hudson (2009). « Study of Failure and Scale Effects in Rocks under Uniaxial Compression Using 3D Cellular Automata ». In: *International Journal of Rock Mechanics and Mining Sciences* 46.4, pp. 674–685 (Cited on page 22).

Paquot, Y., F. Duport, A. Smerieri, J. Dambre, B. Schrauwen, M. Haelterman, and S. Massar (Feb. 27, 2012). « Optoelectronic Reservoir Computing ». In: *Scientific Reports* 2.1 (1), p. 287. ISSN: 2045-2322. DOI: 10.1038/srep00287 (Cited on page 38).

Parisì, German I., Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter (May 2019). « Continual Lifelong Learning with Neural Networks: A Review ». In: *Neural Networks* 113, pp. 54–71. ISSN: 08936080. DOI: 10.1016/j.neunet.2019.01.012. arXiv: 1802.07569 (Cited on page 4).
Pascanu, Razvan and Herbert Jaeger (Mar. 1, 2011). « A Neurodynamical Model for Working Memory ». In: *Neural Networks* 24.2, pp. 199–207. ISSN: 0893-6080. DOI: 10.1016/j.neunet.2010.10.003 (Cited on page 37).

Pathak, Deepak, Chris Lu, Trevor Darrell, Phillip Isola, and Alexei A Efros (2019). « Learning to Control Self-Assembling Morphologies: A Study of Generalization via Modularity ». In: *NeurIPS*. NeurIPS, p. 13 (Cited on page 72).

Pattee, Howard H. and Hiroki Sayama (Apr. 2019). « Evolved Open-Endedness, Not Open-Ended Evolution ». In: *Artificial Life* 25.1, pp. 4–8. ISSN: 1064-5462, 1530-9185. DOI: 10.1162/artl_a_00276 (Cited on page 58).

Pesavento, Umberto (July 1, 1995). « An Implementation of von Neumann’s Self-Reproducing Machine ». In: *Artificial Life* 2.4, pp. 337–354. ISSN: 1064-5462. DOI: 10.1162/artl.1995.2.4.337 (Cited on page 60).

Pfeifer, Rolf, Josh Bongard, and Simon Grand (2007). *How the Body Shapes the Way We Think: A New View of Intelligence*. Cambridge, Mass: MIT Press. 394 pp. ISBN: 978-0-262-16239-5 (Cited on page 37).

Pivato, Marcus (Feb. 22, 2007). « Spectral Domain Boundaries in Cellular Automata ». arXiv: math/0507091 (Cited on page 103).

Poli, Riccardo and Brian Logan (1996). « On the Relations between Search and Evolutionary Algorithms ». In: *COGNITIVE SCIENCE RESEARCH PAPERS-UNIVERSITY OF BIRMINGHAM CSRP* (Cited on page 53).

Potoyan, Davit A., Alexey Savelyev, and Garegin A. Papoian (Jan. 2013). « Recent Successes in Coarse-Grained Modeling of DNA: Coarse-grained Modeling of DNA ». In: *Wiley Interdisciplinary Reviews: Computational Molecular Science* 3.1, pp. 69–83. ISSN: 17590876. DOI: 10.1002/wcms.1114 (Cited on page 94).

Pugh, Justin K., Lisa B. Soros, and Kenneth O. Stanley (2016). « Quality Diversity: A New Frontier for Evolutionary Computation ». In: *Frontiers in Robotics and AI* 3. ISSN: 2296-9144. DOI: 10.3389/frobt.2016.00040 (Cited on page 56).

Rafayelyan, Mushegh, Jonathan Dong, Yongqi Tan, Florent Krzakala, and Sylvain Gigan (Nov. 20, 2020). « Large-Scale Optical Reservoir Computing for Spatiotemporal
Chaotic Systems Prediction ». In: *Physical Review X* 10.4, p. 041037. DOI: 10.1103/PhysRevX.10.041037 (Cited on page 38).

Randazzo, Ettore, Alexander Mordvintsev, Eyvind Niklasson, Michael Levin, and Sam Greydanus (Aug. 27, 2020). « Self-Classifying MNIST Digits ». In: *Distill* 5.8, e00027.002. ISSN: 2476-0757. DOI: 10.23915/distill.00027.002 (Cited on pages 32, 67).

Ray, Thomas S. (Jan. 1, 1991). « An Approach to the Synthesis of Life ». In: *Artificial Life II*. 1st ed. C. G. Langton et al. (Eds.) Addison-Wesley Publishing Co, pp. 371–408 (Cited on pages 58, 60, 72).

Rebuffi, Sylvestre-Alvise, Alexander Kolesnikov, Georg Sperl, and Christoph H. Lampert (2017). « Icarl: Incremental Classifier and Representation Learning ». In: *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, pp. 2001–2010 (Cited on page 137).

Rényi, Alfréd (Jan. 1, 1961). « On Measures of Entropy and Information ». In: *Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics* 4.1, pp. 547–562 (Cited on page 46).

Richards, Fred C., Thomas P. Meyer, and Norman H. Packard (Sept. 2, 1990). « Extracting Cellular Automaton Rules Directly from Experimental Data ». In: *Physica D: Nonlinear Phenomena* 45.1, pp. 189–202. ISSN: 0167-2789. DOI: 10.1016/0167-2789(90)90182-0 (Cited on page 64).

Richardson, Kyle, Hai Hu, Lawrence Moss, and Ashish Sabharwal (2020). « Probing Natural Language Inference Models through Semantic Fragments ». In: *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 34. 05, pp. 8713–8721 (Cited on page 117).

Risi, Sebastian, Charles E. Hughes, and Kenneth O. Stanley (2010). « Evolving Plastic Neural Networks with Novelty Search ». In: *Adaptive Behavior* 18.6, pp. 470–491 (Cited on page 55).

Robins, Anthony (1993). « Catastrophic Forgetting in Neural Networks: The Role of Rehearsal Mechanisms ». In: *Proceedings 1993 The First New Zealand International*
*Two-Stream Conference on Artificial Neural Networks and Expert Systems*. IEEE, pp. 65–68 (Cited on page 137).

Rumelhart, David E., Geoffrey E. Hinton, and Ronald J. Williams (1985). *Learning Internal Representations by Error Propagation*. California Univ San Diego La Jolla Inst for Cognitive Science (Cited on page 116).

Rupe, Adam and James P. Crutchfield (July 2018). « Local Causal States and Discrete Coherent Structures ». In: *Chaos: An Interdisciplinary Journal of Nonlinear Science* 28.7, p. 075312. ISSN: 1054-1500, 1089-7682. DOI: 10.1063/1.5021130. arXiv: 1801.00515 (Cited on page 103).

Ryabov, Vladimir and Dmitry Nerukh (Sept. 2011). « Computational Mechanics of Molecular Systems: Quantifying High-Dimensional Dynamics by Distribution of Poincaré Recurrence Times ». In: *Chaos: An Interdisciplinary Journal of Nonlinear Science* 21.3, p. 037113. ISSN: 1054-1500. DOI: 10.1063/1.3608125 (Cited on page 51).

Salzberg, Chris and Hiroki Sayama (2004). « Complex Genetic Evolution of Artificial Self-Replicators in Cellular Automata ». In: *Complex*. 10.2, pp. 33–39. DOI: 10.1002/cplx.20060 (Cited on page 60).

San Miguel, M., J. H. Johnson, J. Kertesz, K. Kaski, A. Díaz-Guilera, R. S. MacKay, V. Loreto, P. Érdi, and D. Helbing (Nov. 1, 2012). « Challenges in Complex Systems Science ». In: *The European Physical Journal Special Topics* 214.1, pp. 245–271. ISSN: 1951-6401. DOI: 10.1140/epjst/e2012-01694-y (Cited on page 6).

Sapin, Emmanuel, Olivier Bailleux, and Chabrier Jean-Jacques (2003). « Research of a Cellular Automaton Simulating Logic Gates by Evolutionary Algorithms ». In: *Genetic Programming*. Ed. by Conor Ryan, Terence Soule, Maarten Keijzer, Edward Tsang, Riccardo Poli, and Ernesto Costa. Red. by G. Goos, J. Hartmanis, and J. van Leeuwen. Vol. 2610. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 414–423. ISBN: 978-3-540-00971-9 978-3-540-36599-0. DOI: 10.1007/3-540-36599-0_39 (Cited on page 108).

Sayama, Hiroki (1999). « A New Structurally Dissolvable Self-Reproducing Loop Evolving in a Simple Cellular Automata Space ». In: *Artificial Life* 5.4, pp. 343–365. ISSN: 1064-5462. DOI: 10.1162/106454699568818. pmid: 10829086 (Cited on page 60).
— (Apr. 2011). « Seeking Open-Ended Evolution in Swarm Chemistry ». In: *2011 IEEE Symposium on Artificial Life (ALIFE)*. 2011 Ieee Symposium On Artificial Life - Part Of 17273 - 2011 Ssci. Paris, France: IEEE, pp. 186–193. ISBN: 978-1-61284-062-8. DOI: 10.1109/ALIFE.2011.5954667 (Cited on pages 60, 61).

— (May 1, 2019). « Cardinality Leap for Open-Ended Evolution: Theoretical Consideration and Demonstration by Hash Chemistry ». In: *Artificial Life* 25.2, pp. 104–116. ISSN: 1064-5462. DOI: 10.1162/artl_a_00283 (Cited on page 58).

Schmidhuber, Jürgen (2002). « The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions ». In: *Computational Learning Theory*. Ed. by Jyrki Kivinen and Robert H. Sloan. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 216–228. ISBN: 978-3-540-45435-9. DOI: 10.1007/3-540-45435-7_15 (Cited on page 48).

Schmidhuber, Jürgen and S. Heil (Jan. 1996). « Sequential Neural Text Compression ». In: *IEEE Transactions on Neural Networks* 7.1, pp. 142–146. ISSN: 1045-9227. DOI: 10.1109/72.478398 (Cited on page 80).

Schmidhuber, Jürgen, Daan Wierstra, Matteo Gagliolo, and Faustino Gomez (Mar. 1, 2007). « Training Recurrent Networks by Evolino ». In: *Neural Computation* 19.3, pp. 757–779. ISSN: 0899-7667. DOI: 10.1162/neco.2007.19.3.757 (Cited on page 37).

Schomaker, Lambert R. B. (1990). « Neural Network Models of Temporal Pattern Generation. » In: *Conference on Sequencing and Timing of Human Movement*. Wassenaar (The Netherlands): NIAS. Wassenaar, The Netherlands, p. 27 (Cited on page 35).

— (1991). « Simulation and Recognition of Handwriting Movements ». Nijmegen, Netherlands: Radboud University. 223 pp. (Cited on page 35).

— (Feb. 1, 1992). « A Neural Oscillator-Network Model of Temporal Pattern Generation ». In: *Human Movement Science* 11.1, pp. 181–192. ISSN: 0167-9457. DOI: 10.1016/0167-9457(92)90059-K (Cited on page 35).
Schönfinkel, M. (Sept. 1, 1924). « Über die Bausteine der mathematischen Logik [About the building blocks of mathematical logic] ». In: *Mathematische Annalen* 92.3, pp. 305–316. ISSN: 1432-1807. DOI: 10.1007/BF01448013 (Cited on page 61).

Secretan, Jimmy, Nicholas Beato, David B. D'Ambrosio, Adelein Rodriguez, Adam Campbell, Jeremiah T. Folsom-Kovarik, and Kenneth O. Stanley (2011). « Picbreeder: A Case Study in Collaborative Evolutionary Exploration of Design Space ». In: *Evolutionary Computation* 19.3, pp. 373–403. ISSN: 1530-9304. DOI: 10.1162/EVCO_a_00030. pmid: 20964537 (Cited on page 68).

Shalizi, Cosma Rohilla and James P. Crutchfield (Aug. 1, 2001). « Computational Mechanics: Pattern and Prediction, Structure and Simplicity ». In: *Journal of Statistical Physics* 104.3, pp. 817–879. ISSN: 1572-9613. DOI: 10.1023/A:1010388907793 (Cited on page 51).

Shalizi, Cosma Rohilla, Robert Haslinger, Jean-Baptiste Rouquier, Kristina Lisa Klinkner, and Christopher Moore (Mar. 2, 2006). « Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems ». In: *Physical Review E* 73.3. ISSN: 1539-3755, 1550-2376. DOI: 10.1103/PhysRevE.73.036104 (Cited on page 95).

Shalizi, Cosma Rohilla, Kristina Lisa Shalizi, and Robert Haslinger (Sept. 10, 2004). « Quantifying Self-Organization with Optimal Predictors ». In: *Physical Review Letters* 93.11, p. 118701. ISSN: 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.93.118701. arXiv: nlin/0409024 (Cited on pages 51, 95).

Shannon, Claude E. and Warren Weaver (1975). *The Mathematical Theory of Communication*. Urbana: University of Illinois Press. 125 pp. ISBN: 978-0-252-72548-7 (Cited on pages 45, 49).

Shaw, Robert (1984). *The Dripping Faucet as a Model Chaotic System*. The Science Frontier Express Series. Santa Cruz, CA: Aerial Press. 111 pp. ISBN: 978-0-942344-05-9 (Cited on page 46).

Siegelmann, Hava T. and Eduardo D. Sontag (1992). « On the Computational Power of Neural Nets ». In: *Proceedings of the Fifth Annual Workshop on Computational Learning Theory*, pp. 440–449 (Cited on page 34).
Simon, Herbert A. (1962). « The Architecture of Complexity ». In: *Proceedings of the American Philosophical Society* 106.6, pp. 467–482. ISSN: 0003-049X. JSTOR: 985254 (Cited on page 109).

Sims, Karl (1994). « Evolving Virtual Creatures ». In: *SIGGRAPH*. DOI: 10.1145/192161.192167 (Cited on pages 60, 72).

Sipper, Moshe (May 1, 1996). « Co-Evolving Non-Uniform Cellular Automata to Perform Computations ». In: *Physica D: Nonlinear Phenomena* 92.3, pp. 193–208. ISSN: 0167-2789. DOI: 10.1016/0167-2789(95)00286-3 (Cited on page 65).

Smith, Alvy Ray (July 1, 1971). « Simple Computation-Universal Cellular Spaces ». In: *Journal of the ACM* 18.3, pp. 339–353. ISSN: 0004-5411. DOI: 10.1145/321650.321652 (Cited on page 63).

Smith, John Maynard and Eors Szathmary (Mar. 16, 2000). *The Origins of Life: From the Birth of Life to the Origin of Language*. OUP Oxford. 191 pp. ISBN: 978-0-19-164732-1 (Cited on page 5).

Soh, Harold and Yiannis Demiris (June 2012). « Iterative Temporal Learning and Prediction with the Sparse Online Echo State Gaussian Process ». In: *The 2012 International Joint Conference on Neural Networks (IJCNN)*. The 2012 International Joint Conference on Neural Networks (IJCNN), pp. 1–8. DOI: 10.1109/IJCNN.2012.6252504 (Cited on page 38).

Soler-Toscano, Fernando, Hector Zenil, Jean-Paul Delahaye, and Nicolas Gauvrit (May 8, 2014). « Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines ». In: *PLOS ONE* 9.5, e96223. ISSN: 1932-6203. DOI: 10.1371/journal.pone.0096223 (Cited on pages 75, 93).

Solomonoff, R.J. (Mar. 1964a). « A Formal Theory of Inductive Inference. Part I ». In: *Information and Control* 7.1, pp. 1–22. ISSN: 00199958. DOI: 10.1016/S0019-9958(64)90223-2 (Cited on page 47).

— (June 1964b). « A Formal Theory of Inductive Inference. Part II ». In: *Information and Control* 7.2, pp. 224–254. ISSN: 00199958. DOI: 10.1016/S0019-9958(64)90131-7 (Cited on page 47).
Solomonoff, Ray J. (1960). « A Preliminary Report on a General Theory of Inductive Inference ». In: Zator Company Cambridge, MA (Cited on page 47).

Soltoggio, Andrea, John A Bullinaria, Claudio Mattiussi, Peter Durr, and Dario Flore-
ano (2008). « Evolutionary Advantages of Neuromodulated Plasticity in Dynamic,
Reward-based Scenarios ». In: p. 8 (Cited on page 32).

Soros, Lisa B. and Kenneth O. Stanley (July 30, 2014). « Identifying Necessary Conditions for Open-Ended Evolution through the Artificial Life World of Chromaria ». In: *Artificial Life 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems*. Artificial Life 14: International Conference on the Synthesis and Simulation of Living Systems. The MIT Press, pp. 793-800. ISBN: 978-0-262-32621-6. DOI: 10.7551/978-0-262-32621-6-ch128 (Cited on pages 59, 60, 72).

Soros, Lisa B., Kenneth O. Stanley, and Joel Lehman (Dec. 19, 2017). *Open-Endedness: The Last Grand Challenge You've Never Heard Of*. O'Reilly Media. URL: https://www.oreilly.com/radar/open-endedness-the-last-grand-challenge-youve-never-heard-of/ (visited on 05/10/2021) (Cited on page 57).

Spector, Lee, Jon Klein, and Mark Feinstein (2007). « Division Blocks and the Open-ended Evolution of Development, Form, and Behavior ». In: *Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation* (London, England). GECCO '07. New York, NY, USA: ACM, pp. 316–323. ISBN: 978-1-59593-697-4. DOI: 10.1145/1276958.1277019 (Cited on pages 60, 72).

Srivastava, Rupesh Kumar, Jonathan Masci, Sohrob Kazerounian, Faustino J. Gomez, and Jürgen Schmidhuber (2013). « Compete to Compute ». In: *Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013*. Proceedings of a Meeting Held December 5-8, 2013, Lake Tahoe, Nevada, United States. Ed. by Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, pp. 2310–2318 (Cited on page 117).

Stanley, Kenneth O. (Aug. 1, 2019). « Why Open-Endedness Matters ». In: *Artificial Life* 25.3, pp. 232–235. ISSN: 1064-5462. DOI: 10.1162/artl_a_00294 (Cited on page 57).
Stanley, Kenneth O. and Joel Lehman (2015). *Why Greatness Cannot Be Planned: The Myth of the Objective*. Cham, Switzerland: Springer International Publishing. 141 pp. ISBN: 978-3-319-15523-4 (Cited on page 6).

Stanley, Kenneth O. and Risto Miikkulainen (June 2002). « Evolving Neural Networks through Augmenting Topologies ». In: *Evolutionary Computation* 10.2, pp. 99–127. ISSN: 1063-6560, 1530-9304. DOI: 10.1162/106365602320169811 (Cited on page 57).

Sudhakaran, Shyam, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, and Sebastian Risi (June 4, 2021). « Growing 3D Artefacts and Functional Machines with Neural Cellular Automata ». arXiv: 2103.08737 [cs] (Cited on page 22).

Sugano, Chihiro, Kazutaka Kanno, and Atsushi Uchida (Jan. 2020). « Reservoir Computing Using Multiple Lasers With Feedback on a Photonic Integrated Circuit ». In: *IEEE Journal of Selected Topics in Quantum Electronics* 26.1, pp. 1–9. ISSN: 1558-4542. DOI: 10.1109/JSTQE.2019.2929179 (Cited on page 38).

Tanaka, Gouhei, Toshiyuki Yamane, Jean Benoit Héroux, Ryosho Nakane, Naoki Kanazawa, Seiji Takeda, Hidetoshi Numata, Daiju Nakano, and Akira Hirose (July 1, 2019). « Recent Advances in Physical Reservoir Computing: A Review ». In: *Neural Networks* 115, pp. 100–123. ISSN: 0893-6080. DOI: 10.1016/j.neunet.2019.03.005 (Cited on pages 35, 36, 38).

Taylor, Matthew E. and Peter Stone (2007). « Cross-Domain Transfer for Reinforcement Learning ». In: *Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007*. Ed. by Zoubin Ghahramani. Vol. 227. ACM International Conference Proceeding Series. ACM, pp. 879–886. DOI: 10.1145/1273496.1273607 (Cited on page 115).

Taylor, Matthew E., Peter Stone, and Yaxin Liu (2007). « Transfer Learning via Inter-Task Mappings for Temporal Difference Learning ». In: *J. Mach. Learn. Res.* 8, pp. 2125–2167 (Cited on page 115).

Taylor, Tim (Jan. 1, 2002). « Chapter 1 - Creativity in Evolution: Individuals, Interactions, and Environments ». In: *Creative Evolutionary Systems*. Ed. by Peter J Bentley and David W. Corne. The Morgan Kaufmann Series in Artificial Intelli-
gence. San Francisco: Morgan Kaufmann, pp. 79–108. ISBN: 978-1-55860-673-9. DOI: 10.1016/B978-155860673-9/50037-9 (Cited on page 60).

Taylor, Tim (July 27, 2015). *Requirements for Open-Ended Evolution in Natural and Artificial Systems*. DOI: 10.48550/arXiv.1507.07403. arXiv: 1507.07403 [cs, q-bio]. URL: http://arxiv.org/abs/1507.07403 (visited on 11/09/2022). preprint (Cited on page 59).

Taylor, Tim et al. (Aug. 2016). « Open-Ended Evolution: Perspectives from the OEE Workshop in York ». In: *Artificial Life* 22.3, pp. 408–423. ISSN: 1064-5462. DOI: 10.1162/ARTL_a_00210 (Cited on pages 57, 59).

Torrejon, Jacob et al. (July 2017). « Neuromorphic Computing with Nanoscale Spintronic Oscillators ». In: *Nature* 547.7664 (7664), pp. 428–431. ISSN: 1476-4687. DOI: 10.1038/nature23011 (Cited on page 38).

Traub, J. F., G. W. Wasilkowski, and H. Woźniakowski (1983). *Information, Uncertainty, Complexity*. Reading, Mass: Addison-Wesley Pub. Co., Advanced Book Program/World Science Division. 176 pp. ISBN: 978-0-201-07890-9 (Cited on page 47).

Tsalides, Ph, P. J. Hicks, and T. A. York (Nov. 1, 1989). « Three-Dimensional Cellular Automata and VLSI Applications ». In: *IEE Proceedings E (Computers and Digital Techniques)* 136.6, pp. 490–495. ISSN: 2053-7948. DOI: 10.1049/ip-e.1989.0067 (Cited on page 22).

Tsertsvadze, G. N. (1964). « Stochastic Automata and the Problem of Constructing Reliable Automata from Unreliable Elements. i(Reliable Finite Automata Design from Unreliable Elements, Using Stochastic Automaton Model) ». In: *Automation and Remote Control* 25, pp. 198–210 (Cited on page 66).

Tyson, J. J. (Mar. 13, 2013). *The Belousov-Zhabotinskii Reaction*. Springer Science & Business Media. 138 pp. ISBN: 978-3-642-93046-1. Google Books: hIPqCAAAQBAJ (Cited on page 53).

Vandoorne, Kristof, Joni Dambre, David Verstraeten, Benjamin Schrauwen, and Peter Bienstman (Sept. 2011). « Parallel Reservoir Computing Using Optical Amplifiers ».
In: *IEEE Transactions on Neural Networks* 22.9, pp. 1469–1481. ISSN: 1941-0093.
DOI: 10.1109/TNN.2011.2161771 (Cited on page 38).

Vandoorne, Kristof, Wouter Dierckx, Benjamin Schrauwen, David Verstraeten, Roel Baets, Peter Bienstman, and Jan Van Campenhout (July 21, 2008). « Toward Optical Signal Processing Using Photonic Reservoir Computing ». In: *Optics Express* 16.15, pp. 11182–11192. ISSN: 1094-4087. DOI: 10.1364/OE.16.011182 (Cited on page 38).

Vandoorne, Kristof, Pauline Mechet, Thomas Van Vaerenbergh, Martin Fiers, Geert Mor-
thier, David Verstraeten, Benjamin Schrauwen, Joni Dambre, and Peter Bienstman
(Mar. 24, 2014). « Experimental Demonstration of Reservoir Computing on a Silicon
Photonics Chip ». In: *Nature Communications* 5.1 (1), p. 3541. ISSN: 2041-1723. DOI:
10.1038/ncomms4541 (Cited on page 38).

Varela, Francisco G., Humberto R. Maturana, and Ricardo Uribe (1991). « Autopoiesis: The Organization of Living Systems, Its Characterization and a Model ». In: *Facets of Systems Science*. Springer, pp. 559–569 (Cited on page 62).

Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin (Dec. 5, 2017). « Attention Is All You Need ». arXiv: 1706.03762 [cs] (Cited on pages 114, 124, 130, 135).

Verstraeten, D., B. Schrauwen, D. Stroobandt, and J. Van Campenhout (Sept. 30, 2005). « Isolated Word Recognition with the Liquid State Machine: A Case Study ». In: *Information Processing Letters*. Applications of Spiking Neural Networks 95.6, pp. 521–528. ISSN: 0020-0190. DOI: 10.1016/j.ipl.2005.05.019 (Cited on page 38).

Verstraeten, David, Benjamin Schrauwen, and Dirk Stroobandt (2005). « Reservoir Computing with Stochastic Bitstream Neurons ». In: *Proceedings of the 16th Annual ProRISC Workshop*, pp. 454–459 (Cited on page 37).

Vichniac, Gérard Y. (Jan. 1, 1984). « Simulating Physics with Cellular Automata ». In: *Physica D: Nonlinear Phenomena* 10.1, pp. 96–116. ISSN: 0167-2789. DOI: 10.1016/0167-2789(84)90253-7 (Cited on page 21).

Vispoel, Milan, Aisling J. Daly, and Jan M. Baetens (Apr. 1, 2022). « Progress, Gaps and Obstacles in the Classification of Cellular Automata ». In: *Physica D: Nonlinear*
*Phenomena* 432, p. 133074. ISSN: 0167-2789. DOI: 10.1016/j.physd.2021.133074
(Cited on page 18).

Vitanyi, P.M. (Oct. 2006). « Meaningful Information ». In: *IEEE Transactions on Information Theory* 52.10, pp. 4617–4626. ISSN: 1557-9654. DOI: 10.1109/TIT.2006.881729 (Cited on page 51).

Von Neumann, John and Arthur W. Burks (1966). « Theory of Self-Reproducing Automata ». In: *IEEE Transactions on Neural Networks* 5.1, pp. 3–14 (Cited on pages 4, 13, 60, 63, 73, 92).

Wang, Yaqing, Quanming Yao, James T. Kwok, and Lionel M. Ni (2020). « Generalizing from a Few Examples: A Survey on Few-Shot Learning ». In: *ACM computing surveys (csur)* 53.3, pp. 1–34 (Cited on page 116).

Weiss, Ron, George Homsy, and Radhika Nagpal (1998). « Programming Biological Cells ». In: *Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems*. International Conference on Architectural Support for Programming Languages and Operating Systems, p. 1 (Cited on page 69).

Weiss, Ron, George E. Homsy, and Thomas F. Knight (2002). « Toward in Vivo Digital Circuits ». In: *Evolution as Computation*. Ed. by Laura F. Landweber and Erik Winfree. Red. by G. Rozenberg, Th. Bäck, A. E. Eiben, J. N. Kok, and H. P. Spaink. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 275–295. ISBN: 978-3-642-63081-1 978-3-642-55606-7_14 (Cited on page 69).

Weston, Jason, Antoine Bordes, Sumit Chopra, and Tomas Mikolov (2016). « Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks ». In: *4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings*. Ed. by Yoshua Bengio and Yann LeCun (Cited on page 117).

Williame, Jérôme, Artur Difini Accioly, Damien Rontani, Marc Sciamanna, and Joo-
Von Kim (June 10, 2019). « Chaotic Dynamics in a Macrospin Spin-Torque Nano-
Oscillator with Delayed Feedback ». In: *Applied Physics Letters* 114.23, p. 232405.
ISSN: 0003-6951. DOI: 10.1063/1.5095630 (Cited on page 38).
Winograd, Shmuel and Jack D. Cowan (1963). *Reliable Computation in the Presence of Noise*. Mit Press Cambridge, Mass. (Cited on page 66).

Woese, Carl (June 9, 1998). « The Universal Ancestor ». In: *Proceedings of the National Academy of Sciences* 95.12, pp. 6854–6859. DOI: 10.1073/pnas.95.12.6854 (Cited on page 5).

Wolf, S. A., D. D. Awschalom, R. A. Buhrman, J. M. Daughton, S. von Molnár, M. L. Roukes, A. Y. Chtchelkanova, and D. M. Treger (Nov. 16, 2001). « Spintronics: A Spin-Based Electronics Vision for the Future ». In: *Science* 294.5546, pp. 1488–1495. DOI: 10.1126/science.1065389 (Cited on page 38).

Wolfram, Stephen (July 1, 1983). « Statistical Mechanics of Cellular Automata ». In: *Reviews of Modern Physics* 55.3, pp. 601–644. ISSN: 0034-6861. DOI: 10.1103/RevModPhys.55.601 (Cited on pages 20, 45, 46, 126).

— (Jan. 1, 1984). « Universality and Complexity in Cellular Automata ». In: *Physica D: Nonlinear Phenomena* 10.1, pp. 1–35. ISSN: 0167-2789. DOI: 10.1016/0167-2789(84)90245-8 (Cited on pages 16, 17, 73).

— (2002). *A New Kind of Science*. Champaign, IL: Wolfram Media. 1197 pp. ISBN: 978-1-57955-008-0 (Cited on pages 8, 19, 96, 108, 126).

Wolpert, L. (Oct. 1, 1969). « Positional Information and the Spatial Pattern of Cellular Differentiation ». In: *Journal of Theoretical Biology* 25.1, pp. 1–47. ISSN: 0022-5193. DOI: 10.1016/S0022-5193(69)80016-0 (Cited on page 70).

Woolley, Brian G. and Kenneth O. Stanley (July 12, 2011). « On the Deleterious Effects of a Priori Objectives on Evolution and Representation ». In: *Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation*. GECCO ’11. New York, NY, USA: Association for Computing Machinery, pp. 957–964. ISBN: 978-1-4503-0557-0. DOI: 10.1145/2001576.2001707 (Cited on page 68).

Wuensche, Andrew (1999). « Classifying Cellular Automata Automatically: Finding Gliders, Filtering, and Relating Space-Time Patterns, Attractor Basins, and the Z Parameter ». In: *Complexity* 4.3, pp. 47–66. ISSN: 1099-0526. DOI: 10.1002/(SICI)
1099-0526(199901/02)4:3<47::AID-CPLX9>3.0.CO;2-V (Cited on pages 19, 95, 102).

Wuensche, Andrew (2011). *Exploring Discrete Dynamics*. Luniver Press (Cited on page 102).

Wuensche, Andrew and Mike Lesser (1992). *The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata*. Santa Fe Institute Studies in the Sciences of Complexity. Reference Volume v. 1. Reading, Mass: Addison-Wesley. 250 pp. ISBN: 978-0-201-55740-4 (Cited on pages 18, 19).

Wulff, N. H. and J. A. Hertz (1993). « Learning Cellular Automaton Dynamics with Neural Networks ». In: *Advances in Neural Information Processing Systems*, pp. 631–638 (Cited on page 27).

Wyffels, F. and B. Schrauwen (June 1, 2010). « A Comparative Study of Reservoir Computing Strategies for Monthly Time Series Prediction ». In: *Neurocomputing*. Subspace Learning / Selected Papers from the European Symposium on Time Series Prediction 73.10, pp. 1958–1964. ISSN: 0925-2312. DOI: 10.1016/j.neucom.2010.01.016 (Cited on page 38).

Yaeger, Larry (1994). « Computational Genetics, Physiology, Metabolism, Neural Systems, Learning, Vision, and Behavior or Poly World: Life in a New Context ». In: *Santa Fe Institute Studies in the Sciences of Complexity*. Vol. 17. Addison-Wesley Publishing Co, pp. 263–263 (Cited on pages 60, 72).

Yamazaki, Tadashi and Shigeru Tanaka (Apr. 2007). « The Cerebellum as a Liquid State Machine ». In: *Neural Networks: The Official Journal of the International Neural Network Society* 20.3, pp. 290–297. ISSN: 0893-6080. DOI: 10.1016/j.neunet.2007.04.004. pmid: 17517494 (Cited on page 37).

Yang, Xiao, Wanlong Chen, and Frank Z. Wang (May 1, 2016). « Investigations of the Staircase Memristor Model and Applications of Memristor-Based Local Connections ». In: *Analog Integrated Circuits and Signal Processing* 87.2, pp. 263–273. ISSN: 1573-1979. DOI: 10.1007/s10470-016-0715-3 (Cited on page 37).
Yarats, Denis, Amy Zhang, Ilya Kostrikov, Brandon Amos, Joelle Pineau, and Rob Fergus (2019). « Improving Sample Efficiency in Model-Free Reinforcement Learning from Images ». arXiv: 1910.01741 (Cited on page 116).

Yildiz, Izzet B., Herbert Jaeger, and Stefan J. Kiebel (Nov. 1, 2012). « Re-Visiting the Echo State Property ». In: *Neural Networks* 35, pp. 1–9. ISSN: 0893-6080. DOI: 10.1016/j.neunet.2012.07.005 (Cited on page 36).

Yilmaz, Özgür (Oct. 1, 2014). « Reservoir Computing Using Cellular Automata ». arXiv: 1410.0162 [cs] (Cited on pages 40, 41, 115, 127, 128, 135).

Zeleny, Milan (1977). « Self-Organization of Living Systems: A Formal Model of Autopoiesis ». In: *International journal of general system* 4.1, pp. 13–28 (Cited on page 62).

Zenil, Hector (2010). « Compression-Based Investigation of the Dynamical Properties of Cellular Automata and Other Systems ». In: *Complex Systems* 19.1 (Cited on pages 17, 19, 48, 74, 76, 85, 86, 93).

— (Sept. 1, 2014). « What Is Nature-Like Computation? A Behavioural Approach and a Notion of Programmability ». In: *Philosophy & Technology* 27.3, pp. 399–421. ISSN: 2210-5441. DOI: 10.1007/s13347-012-0095-2 (Cited on page 75).

Zenil, Hector, Jean-Paul Delahaye, and Cédric Gaucherel (2012). « Image Characterization and Classification by Physical Complexity ». In: *Complexity* 17.3, pp. 26–42. ISSN: 1099-0526. DOI: 10.1002/cplx.20388 (Cited on page 75).

Zenil, Hector, Fernando Soler-Toscano, Jean-Paul Delahaye, and Nicolas Gauvrit (Sept. 30, 2015). « Two-Dimensional Kolmogorov Complexity and an Empirical Validation of the Coding Theorem Method by Compressibility ». In: *PeerJ Computer Science* 1, e23. ISSN: 2376-5992. DOI: 10.7717/peerj-cs.23 (Cited on pages 75, 80, 93).

Zenil, Hector and Elena Villarreal-Zapata (Sept. 1, 2013). « Asymptotic Behavior and Ratios of Complexity in Cellular Automata ». In: *International Journal of Bifurcation and Chaos* 23.09, p. 1350159. ISSN: 0218-1274. DOI: 10.1142/S0218127413501599 (Cited on page 75).
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.

## MOTS CLÉS

Apprentissage automatique ★ Intelligence artificielle ★ Systèmes complexes ★ Complexité

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

## KEYWORDS

Machine learning ★ Artificial Intelligence ★ Complex systems ★ Complexity