You are currently browsing the tag archive for the ‘Cellular Automata’ tag.

Saramago Caos quote - Lisbon, Vitorino Ramos 2013Photo – “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].

von Neumann

There is thus this completely decisive property of complexity, that there exists a critical size below which the process of synthesis is degenerative, but above which the phenomenon of synthesis, if properly arranged, can become explosive, in other words, where syntheses of automata can proceed in such a manner that each automaton will produce other automata which are more complex and of higher potentialities than itself“. ~ John von Neumann, in his 1949 University of Illinois lectures on the Theory and Organization of Complicated Automata [J. von Neumann, Theory of self-reproducing automata, 1949 Univ. of Illinois Lectures on the Theory and Organization of Complicated Automata, ed. A.W. Burks (University of Illinois Press, Urbana, IL, 1966).].

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.

[...] People should learn how to play Lego with their minds. Concepts are building bricks [...] V. Ramos, 2002.

@ViRAms on Twitter


Blog Stats

  • 244,569 hits