# Onset of Chaos¶

Note

This is an in-progress translation of Sean Whalen’s original document. His work is itself a work in progress pending notes and modifications from Jim Crutchfield.

A Cellular Automaton (CA) is a spatially extended dynamical system represented
by a lattice of cells where each cell is in one of several possible *states*.
Often, the lattice is of one or two dimensions and each cell takes a value of
“on” or “off”. At each time step the state of each cell is updated as a function
of its neighbor’s states. The function used to update a cell is called a *rule*;
there may be multiple such rules. One well known rule set is Conway’s Game of
Life. This and many other rules can be explored using the cross-platform tool
Golly.

Christopher Langton, a pioneer of Artificial Intelligence, studied one
dimensional cellular automata in the early 90s. Langton examined why certain
rules resulted in periodic, random, or highly structured behavior. He proposed
that CA rules approaching a *phase transition* between ordered and disordered
behavior are capable of universal (Turing complete) computation. There are
several interpretations of what computation means in this context; perhaps the
most straightforward views a rule as a program and the initial grid values (the
*initial configuration*) as the program’s input.

Langton described the computational capability of a CA using three properties: 1) memory, 2) transmission, and 3) information processing. The space of rules was studied using a parameter that gives the fraction of a CA’s rules resulting in an “on” state for a cell. He argued that diverging correlation times and lengths were necessary for memory and transmission, and these were maximized by values of between 0 (complete order) and 1 (complete disorder). For example, Conway’s Game of Life has and is capable of universal computation given certain initial conditions. Other rules with different values may also permit universal computation. There is no standard value of that characterizes universal computation across all CAs, but values maximizing memory and transmission tend to exist near the “edge of chaos” between order and disorder. Shalizi gives a critique of the historical misappropriation of the “edge of chaos” label.

If you’ll forgive the resolution, the following figure from Langton’s “Life at the Edge of Chaos” illustrates these ideas using Wolfram’s universality classes:

The parameterization of rule-space using ties complexity to
structure rather than randomness, and is similar to Crutchfield’s *statistical
complexity* and Grassberger’s *effective measure complexity*. A
completely disordered (random) system can be described simply in probabilistic
terms, as can a completely ordered system, but those systems in between exhibit
more structured behavior and thus require more elaborate models. Crutchfield and
Young made these ideas explicit in several papers including “Inferring
Statistical Complexity” and
“Computation at the Onset of Chaos”.
This page serves as a tutorial for approximating the results from “Inferring
Statistical Complexity” (henceforth ISC) using the Computational Mechanics in
Python library.

## Figure 1: Reconstructing the Route to Chaos¶

ISC demonstrates a -like phase transition in the period doubling behavior of the logistic map . They observe this transition for progressively chaotic values of the parameter , generating a symbolic time series via the generating partition and feeding this into the subtree merging -machine reconstruction algorithm. From the -machine, the entropy rate and statistical complexity of the underlying data stream is calculated and plotted.

It is recommended the reader is familiar with the above terminology before proceeding. We also assume you’ve gone through the introductory CMPy tutorial. An interactive visualization of period doubling in the logistic map can be found here, for those interested. The first figure we’ll reproduce is below:

These -machines are topologically reconstructed: morphs (subtrees) are equivalent if branch symbols match regardless of the associated probability.

Before we really get down into it, we first we import a few things:

```
from cmpy import *
from cmpy.inference import *
from cmpy.machines.algorithms.convert import DFA_from_MealyHMM
from cmpy.machines.algorithms.dfaminimize import minimize_hopcroft
import numpy
from networkx import relabel_nodes
```

Our first task is obtaining data from the logistic map and applying the generating partition:

```
def logistic_generate(r, data_length=100000):
data = range(data_length)
x = numpy.random.random()
# skip transients
for i in xrange(10000):
x = r * x * (1 - x)
for i in xrange(data_length):
data[i] = 0 if x < 0.5 else 1
x = r * x * (1 - x)
return data
```

Next we infer machines for the given values:

```
def infer_machine(r, morph_length):
tm = TreeMerger()
m = tm.infer(logistic_generate(r), morphLength=morph_length, treeDepth=2*morph_length+1)
top_m = minimize_hopcroft(DFA_from_MealyHMM(m.reduce(), probability=False))
nodes = top_m.nodes()
top_m = relabel_nodes(top_m, dict(zip(sorted(nodes), range(len(nodes)))))
return m.to_recurrent_eM(), top_m
for morph_length, r in zip([16, 6, 6, 6], [3.569945671, 3.67859, 3.7, 4]):
_, m = infer_machine(r, morph_length)
m.draw()
```

The resulting machine for is `here`

due to size. Note that states 47 and 48 transition back to the start state on
any symbol, denoted with transition symbol * . For we have:

and for :

and finally for :

## Figure 2: Complexity-Entropy Diagram¶

The next figure plots an estimate of the entropy rate against the statistical complexity of the inferred -machine for 193 realizations of the logistic map’s generating partition, using progressively chaotic values:

Entropy rate is estimated using length- blocks:

The plot is relatively straightforward: we generate a list of values,
generate partitioned data, infer the -machine, and store the
entropy estimate and statistical complexity. To create the diagram, we pass
these values to matplotlib’s `plot()`

function.

```
rs = numpy.linspace(3, 4, 193)
morph_length = 6
h_mus = []
c_mus = []
for r in rs:
m, _ = infer_machine(r, morph_length)
h_mus.append(m.block_entropies([16])[0]/16)
c_mus.append(m.statistical_complexity())
pylab.plot(h_mus, c_mus, '.')
pylab.ylabel('$C_\mu$')
pylab.show()
```

This approximates the figure from ISC since we have different data and parameter values, but the overall structure should be similar — complexity grows towards the cited peak at followed by a gradual decrease as moves toward complete chaos. This conceptually maps back to Langton’s plot of versus complexity for Wolfram’s CA universality classes: