You are currently browsing the tag archive for the ‘Langton’s “edge of chaos”’ tag.

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

“** 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…

## Recent Comments