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: