You are currently browsing the tag archive for the ‘Halting problem’ 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].

## Recent Comments