In order for computation to emerge spontaneously and become an important factor in the dynamics of a system, the material substrate must support the primitive functions required for computation: the transmission, storage, and modification of information. The optimal conditions for the support of those functions are achieved in the vicinity of a phase transition.
We will focus on the conditions under which this capacity to support computation itself might emerge in physical systems. Under what conditions will cellular automata support the basic operations of information transmission, storage, and modification?
By selecting an appropriate parameterization of the space of Cellular Automata (CA), one observes a phase transition between highly ordered and highly disordered dynamics, analogous to the phase transition between the solid and fluid states of matter. Furthermore, we observe that CAs exhibiting the most complex behavior -both qualitatively and quantitatively- are found generically in the vicinity of this phase transition. Most importantly, we observe that CAs in the transition region have the greatest potential for the support of information storage, transmission, and modification, and therefore for the emergence of computation.
Computation may emerge spontaneously and come to dominate the dynamics of physical systems when those systems are at or near a transition between their solid and fluid phases. This hypothesis, if borne out, has many implications for understanding the role of information in nature. Perhaps the most exciting implication is the possibility that life had its origin in the vicinity of a phase transition, and that evolution reflects the process by which life has gained local control over a successively greater number of environmental parameters affecting its ability to maintain itself at a critical balance point between order and chaos.
Wolfram has proposed the following four qualitative classes of CA behavior:
Wolfram finds the following analogs for his classes of cellular automaton behaviors in the field of dynamical systems:
This association of class IV CAs with "very long transients" will figure "critically" in what follows. Wolfram suggests that class IV CAs are capable of supporting computation, even universal computation, and that it is this capacity that makes their behavior so complex.
There is an obvious mapping of the Wolfram classes onto the spectrum of dynamical possibilities over the k space: classes I and II constitute the ordered phase, while class III constitutes the disordered phase. Because of their long transients, propagating structures, large correlation lengths, and other statistical properties, the only logical choice for the location of class IV CAs is at the transition between these two phases of dynamical behavior.
The Lambda parameter is defined as follows.
In Wolfram CA, there are K = 2 possible states (dead or alive), and a neighbourhood of N = 3 to calculate next states (the cell itself and its two adjacent cells). So there are K^N states that will define the next state of a cell. We pick an arbitrary state S, and call it the quiescent state Sq. Let there be n transitions to this special quiescent state in a rule. In this context, we define:
λ = (K^N - n) / K^N
On the other hand, we look for a measure of the complexity of the system. We choose the Mutual Information between generations:
MI = Σ ( p(x,y) · log(x) · log(y) )
Now, we wil explore the lambda space of the Wolfram CA. This example runs the CA and returns the lambda and complexity of the executed ruleset.
In the code, we have to change the ruleset (in the first lines of the "mySketch" tab). Try at least one ruleset of each wolfram's class:
Afterwards, display those values in a graph to analyze the results. Below the simulation, you have an edit field to introduce the list of pairs (lamda, complexity) for displaying a graph.
In [2]:
%%HTML
<iframe src="https://www.openprocessing.org/sketch/433886/embed/" width="640" height="348"></iframe>
In [1]:
from ipywidgets import widgets
from IPython.display import display
import numpy as np
import re
from matplotlib import pyplot as plt
%matplotlib inline
def handle_submit(sender):
all = np.fromiter((item.group() for item in re.finditer(r'\d+', text.value)), dtype=np.int64).reshape((-1, 2))
plt.plot(all[:,0],all[:,1],'o-')
text = widgets.Text(description="Values")
text.on_submit(handle_submit)
display(widgets.Label("Enter list of (Lambda,C) values as a list of tuples. E.g. \"(0,10),(1,20),(3,25)\""))
display(text)
As we survey CA rule spaces using the Lambda parameter, we encounter a phase transition between periodic and chaotic behavior, and the most complex behavior is found in the vicinity of this transition, both qualitatively and quantitatively.
Briefly, information storage involves lowering entropy while information transmission involves raising entropy. In order to compute, a system must do both, and therefore must effect a trade-off between high and low operating entropy. This trade-off is optimized in the vicinity of a phase transition.
Complexity increases with randonmess only up to a point -a phase transition- after which complexity decreases with further increases in randomness, so that total disorder is just as "simple", in a sense, as total order. Complex behavior involves a mix of order and disorder.
Information becomes an important factor in the dynamics of CAs in the vicinity of the phase transition between periodic and chaotic behavior. Only in the vicinity of this phase transition can information propagate over long distances without decaying appreciably. This allows for the long-range correlations in behavior, sensitivity to "size", extended transients, etc., which are necessary for the support of computation. By contrast, the ordered regime does not allow information to propagate at all, whereas the disordered regime propagates effects too well, causing information to decay rapidly into random noise.