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

Advertisements

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

@ViRAms on Twitter

  • RT @whyvert: An experiment that IQ → cooperation: In a repeated prisoner's dilemma game, the high IQ group cooperated far more than the low… | 1 day ago
  • RT @ValerioCapraro: What makes a cooperative society? - Good heart? Adherence to social norms? Intelligence? - A new paper in J Political E… | 1 day ago
  • RT @mikenning: Saw this on a machine learning page. @j2bryson You'll like this. https://t.co/Jn7KPZ0sIf | 2 days ago
  • RT @zackbloom: We live in a post-parody society where it's impossible to invent anything more ridiculous than reality https://t.co/HPGekRKE… | 3 days ago
  • RT @ricard_sole: When synthetic networks are artificially evolved to achieve larger complexity, a natural compromise between modularity and… | 6 days ago
  • RT @alexvespi: New paper analyze the “connection between the way in which individuals explore new resources and exploit known assets in the… | 1 week ago
  • RT @ricard_sole: Living systems seem to inhabit the critical boundary separating order from disorder. Why is that? How do they get there? H… | 1 week ago
  • RT @barabasi: @aaronclauset Every 5 years someone is shocked to re-discover that a pure power law does not fit many networks. True: Real ne… | 1 week ago
  • RT @janeygak: The idea of financial planning began with the raising of livestock. Why? It required an extraordinary level of mathematical s… | 1 week ago
  • RT @aaronclauset: 👏 I was rejected by 9 of 11 graduate schools I applied to, 5 of 6 postdocs, and 11 of 12 faculty jobs. Luck has a huge ro… | 1 week ago

Archives

Blog Stats

  • 247,249 hits