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

Samuel was an aLife(r)

Interesting how this Samuel Beckett (1906–1989) quote to his work is so close to the research on Artificial Life (aLife), as well as how Christopher Langton (link) approached the field, on his initial stages, fighting back and fourth with his Lambda parameter (“Life emerges at the Edge of Chaos“) back in the 80’s. According to Langton‘s findings, at the edge of several ordered states and the chaotic regime (lambda=0,273) the information passing on the system is maximal, thus ensuring life. Will not wait for Godot. Here:

“Beckett was intrigued by chess because of the way it combined the free play of imagination with a rigid set of rules, presenting what the editors of the Faber Companion to Samuel Beckett call a “paradox of freedom and restriction”. That is a very Beckettian notion: the idea that we are simultaneously free and unfree, capable of beauty yet doomed. Chess, especially in the endgame when the board’s opening symmetry has been wrecked and the courtiers eliminated, represents life reduced to essentials – to a struggle to survive.”(*)

(*) on Stephen Moss, “Samuel Beckett’s obsession with chess: how the game influenced his work“, The Guardian, 29 August 2013. [link]

Sand piles

Video -“Sand, sand, pile of sand” by Robert Proch (2009) – Impression without an idea, about trying to catch one (music by Pinkfreud).

Complex Adaptive Systems (CAS) are dynamic developing systems which arrange themselves according to external influences and to their own inner current state. If you are familiar with Conway’s “Game of Life“, you have an example of such a system. Complex adaptive systems arrange themselves around one or more critical factors (like in a sandpile, for example, where the pile will rearrange itself when you drop additional sand grains onto it). The theory behind these systems is related to chaos theory, but the systems are said to be “on the edge of chaos“, because they have the ability to adjust themselves (around the critical factors), unlike truly chaotic systems. One interesting thing with CA-systems is that they can suddenly rearrange themselves rather violently or criticality. Like in a sandpile which has a grain added to it, which topples onto other grains, which in turn topple onto other grains, etc. In physics, the Bak-Tang-Wiesenfeld sandpile model is the first discovered example of a dynamical system displaying self-organized criticality and is named after Per Bak [1] [2] [3], Chao Tang [1] [2] and Kurt Wiesenfeld [1] [2]. While running the model, you soon then have an avalanche effect and signatures produced equivalent to those found in nature. In fact, many phenomena in daily life are complex adaptive systems, like weather, traffic, earthquakes, eco-systems, or the stock market, and many of them share this precise 1/f noise pattern. As our brains.

[1] Per Bak, Chao Tang and Kurt Wiesenfeld (1987). “Self-organized criticality: an explanation of 1/f noise“. Physical Review Letters 59: pp. 381-384.
[2] Per Bak, Chao Tang and Kurt Wiesenfeld (1988). “Self-organized criticality“. Physical Review A 38: pp. 364-374.
[3] Per Bak (1996). How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus. ISBN 0-387-94791-4.