ScienceDirect is currently experiencing a technical issue within our User Registration service whereby access to this piece of content is temporarily denied. We are working to restore this service as soon as possible and apologize for this inconvenience!  

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


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

    • [2]
    • E. Berlekamp, J.H. Conway, R. Guy
    • Winning Ways for Your Mathematical Plays

    • Academic Press, New York (1982)

    • [3]
    • A.W. Burks
    • Essays on Cellular Automata

    • University of Illinois Press, Urbana, IL (1970)

    • [4]
    • G. Chaitin
    • J. Assoc. Comput. Mach., 13 (1966), p. 145

    • [5]
    • E.F. Codd
    • Cellular Automata

    • Academic Press, New York (1968)

    • [6]
    • J.P. Crutchfield, K. Young
    • Computation at the onset of chaos

    • W. Zurek (Ed.), Complexity, Entropy, and Physics of Information, Addison-Wesley, Reading, MA (1990)

    • [8]
    • M. Gardner
    • Mathematical games: The fantastic combinations of John Conway's new solitaire game ‘Life’

    • Sci. Am., 223 (4) (October 1979), pp. 120–123

    • [9]
    • M.R. Garey, D.S. Johnson
    • Computers and Intractability

    • Freeman, San Francisco (1979)

    • [10]
    • L.L. Gatlin
    • Information Theory and the Living System

    • Columbia Univ. Press, New York (1972)

    • [11]
    • H.A. Gutowitz
    • A hierarchical classification of cellular automata

    • H.A. Gutowitz (Ed.), Proceedings of the 1989 Cellular Automata Workshop, North-Holland, Amsterdam (1990)

    • [11]
    • Physica D, to be published.
    • [17]
    • C.G. Langton
    • Computation at the edge of chaos

    • Ph.D. Thesis, University of Michigan (1990)

    • [19]
    • W. Li
    • Analyzing Complex Systems

    • Ph.D. Thesis, Columbia University (1989)

    • [20]
    • W. Li, N.H. Packard
    • Structure of elementary cellular automata rule-space

    • Complex Systems (1990) submitted for publication

    • [21]
    • H.V. McIntosh, in: Proceedings of the 1989 Cellular Automata Workshop, ed. H.A. Gutowitz (North-Holland, Amsterdam), Physica D, to be published.
    • [22]
    • N.H. Packard
    • Adaptation toward the edge of chaos

    • Technical Report, Center for Complex Systems Research, University of Illinois (1988) CCSR-88-5

    • [23]
    • N.H. Packard, S. Wolfram
    • Two-dimensional cellular automata

    • J. Stat. Phys., 38 (1985), p. 901

    • [24]
    • A.R. Smith III
    • Simple computation-universal cellular spaces

    • J. Assoc. Comput. Mach., 18 (1971), pp. 339–353

    • [25]
    • G.Y. Vichniac, P. Tamayo, H. Hartman
    • Annealed and quenched inhomogeneous cellular automata

    • J. Stat. Phys., 45 (1986), pp. 875–883

    • [26]
    • J. von Neumann
    • Theory of self-reproducing automata

    • A.W. Burks (Ed.), 1949 University of Illinois Lectures on the Theory and Organization of Complicated Automata, University of Illinois Press, Urbana, IL (1966)

    • [27]
    • S. Wolfram
    • Statistical mechanics of cellular automata

    • Rev. Mod. Phys., 55 (1983), pp. 601–644

    • [28]
    • S. Wolfram (Ed.), Theory and Applications of Cellular Automata, World Scientific, Singapore (1986)

    • [29]
    • S. Wolfram
    • Universality and complexity in cellular automata

    • Physica D, 10 (1984), pp. 1–35

    • [30]
    • W.T. Wootters, C.G. Langton
    • Is there a sharp phase transition for deterministic cellular automata?

    • H.A. Gutowitz (Ed.), Proceedings of the 1989 Cellular Automata Workshop (1990) to appear in Physica D