Computation at the edge of chaos: Phase transitions and emergent computation

https://doi.org/10.1016/0167-2789(90)90064-VGet rights and content

Abstract

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. Under what conditions might we expect physical systems to support such computational primitives?

This paper presents research on cellular automata which suggests that the optimal conditions for the support of information transmission, storage, and modification, are achieved in the vicinity of a phase transition. We observe surprising similarities between the behaviors of computations and systems near phase transitions, finding analogs of computational complexity classes and the halting problem within the phenomenology of phase transitions.

We conclude that there is a fundamental connection between computation and phase transitions, especially second-order or “critical” transitions, and discuss some of the implications for our understanding of nature if such a connection is borne out.

References (30)

  • J.P. Crutchfield et al.

    Computation at the onset of chaos

  • E. Fredkin et al.

    Conservative logic

    Int. J. Theor. Phys.

    (1982)
  • M. Gardner

    Mathematical games: The fantastic combinations of John Conway's new solitaire game ‘Life’

    Sci. Am.

    (October 1979)
  • M.R. Garey et al.

    Computers and Intractability

    (1979)
  • L.L. Gatlin

    Information Theory and the Living System

    (1972)
  • Cited by (1183)

    View all citing articles on Scopus
    View full text