Not in chaos, at the λ=0.273 vicinity of it

Photo – “O caos é uma ordem por decifrar” (Portuguese), that is… “Chaos is an order yet to be deciphered“, a quote from the Nobel Prize in Literature (1998) José Saramago [Lisbon, V. Ramos, 2013].

In 1990 (*), on one of his now famous works, Christopher Langton (link) decided to ask an important question. 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. He then asked: Under what conditions might we expect physical systems to support such computational primitives?

Naturally, the question is difficult to address directly. Instead, he decided to reformulate the question in the context of a class of formal abstractions of physical systems: cellular automata (CAs). First, he introduce cellular automata and a simple scheme for parametrising (lambda parameter, λ) the space of all possible CA rules. Then he applied this parametrisation scheme to the space of possible one-dimensional CAs in a qualitative survey of the different dynamical regimes existing in CA rule space and their relationship to one another.

By presenting a quantitative picture of these structural relationships, using data from an extensive survey of two-dimensional CAs, he finally review the observed relationships among dynamical regimes, discussing their implications for the more general question raised above.  Langton found out that for a 2-state, 1-r neighbourhood, 1D cellular automata the optimal λ value is close to 0.5. For a 2-state, Moore neighbourhood, 2D cellular automata, like Conway’s Life, the λ value is then 0.273.

We then find that by selecting an appropriate parametrisation of the space of CAs, 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, Langton observed that CAs exhibiting the most complex behaviour – both qualitatively and quantitatively- are found generically in the vicinity of this phase transition. Most importantly, he observed 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. He concludes:

(…) These observations suggest that  there is  a fundamental connection between phase transitions and computation, leading to the following hypothesis concerning the emergence of computation in  physical systems: 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, especially in the vicinity of a second-order or “critical” transition. (…)

Moreover, we observe surprising similarities between the behaviours of computations and systems near phase transitions, finding analogs of computational complexity classes and the halting problem (Turing) within the phenomenology of phase transitions. Langton, concludes that there is a fundamental connection between computation and phase transitions, especially second-order or “critical” transitions, discussing some of the implications for our understanding of nature if such a connection is borne out.

The full paper (*), Christopher G. Langton. “Computation at the edge of chaos”. Physica D, 42, 1990, is available online, here [PDF].

Quadtree self-portrait

“How we engage the dance between structure and flow becomes our unique creative signature“, ~ Michelle James, VA, USA, 2010.

[…] Abstract.: The problem of sending the maximum amount of flow q between two arbitrary nodes s and t of complex networks along links with unit capacity is studied, which is equivalent to determining the number of link-disjoint paths between s and t. The average of q over all node pairs with smaller degree kmin is <q>=kmin ~= c.kmin for large kmin with c a constant implying that the statistics of q is related to the degree distribution of the network. The disjoint paths between hub nodes are found to be distributed among the links belonging to the same edge-biconnected component, and q can be estimated by the number of pairs of edge-biconnected links incident to the start and terminal node. The relative size of the giant edge-biconnected component of a network approximates to the coefficient c. The applicability of our results to real world networks is tested for the Internet at the autonomous system level. […], in D.-S. Lee and H. Rieger, “Maximum flow and topological structure of complex networks“, EPL Journal, Europhysics Letters, Vol. 73, Number 3, p.471, 2006. [link] …

“Artificial Life 101” lesson nº1: emerge yourself a experimental “fire” and observe it carefully till the end.

… The other day I decided to work for almost 48 hours in a row and at the end… to sleep a few hours. When I woke up… – the day (e.g. “flow“) was almost gone, and night (e.g. “structure“) approaching fast -. So I decided, to grab the last sun rays… ; growing up, I guess…