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
- [1]
Self-organized criticality
Phys. Rev. A, 38 (1988), pp. 364–374
- | |
- [2]
Winning Ways for Your Mathematical Plays
Academic Press, New York (1982)
- [3]
Essays on Cellular Automata
University of Illinois Press, Urbana, IL (1970)
- [4]
J. Assoc. Comput. Mach., 13 (1966), p. 145
- [5]
Cellular Automata
Academic Press, New York (1968)
- [6]
Computation at the onset of chaos
W. Zurek (Ed.), Complexity, Entropy, and Physics of Information, Addison-Wesley, Reading, MA (1990)
- [7]
Conservative logic
Int. J. Theor. Phys., 21 (1982), pp. 219–253
- |
- [8]
Mathematical games: The fantastic combinations of John Conway's new solitaire game ‘Life’
Sci. Am., 223 (4) (October 1979), pp. 120–123
- [9]
Computers and Intractability
Freeman, San Francisco (1979)
- [10]
Information Theory and the Living System
Columbia Univ. Press, New York (1972)
- [11]
A hierarchical classification of cellular automata
H.A. Gutowitz (Ed.), Proceedings of the 1989 Cellular Automata Workshop, North-Holland, Amsterdam (1990)
- [11]
- [12]
Local structure theory for cellular automata
Physica D, 28 (1987), pp. 18–48
- | | |
- [13]
Emergent properties in random complex automata
Physica D, 10 (1984), pp. 145–156
- | | |
- [14]
Metabolic stability and epigenesis in randomly constructed genetic nets
J. Theor. Biol., 22 (1969), pp. 437–467
- | | |
- [15]
Optimization by simulated annealing
Science, 220 (1983), pp. 671–680
- |
- [16]
Prob. Inf. Transm., 1 (1965), p. 1
- |
- [17]
Computation at the edge of chaos
Ph.D. Thesis, University of Michigan (1990)
- [18]
Studying artificial life with cellular automata
Physica D, 22 (1986), pp. 120–149
- | | |
- [19]
Analyzing Complex Systems
Ph.D. Thesis, Columbia University (1989)
- [20]
Structure of elementary cellular automata rule-space
Complex Systems (1990) submitted for publication
- [21]
- [22]
Adaptation toward the edge of chaos
Technical Report, Center for Complex Systems Research, University of Illinois (1988) CCSR-88-5
- [23]
Two-dimensional cellular automata
J. Stat. Phys., 38 (1985), p. 901
- [24]
Simple computation-universal cellular spaces
J. Assoc. Comput. Mach., 18 (1971), pp. 339–353
- [25]
Annealed and quenched inhomogeneous cellular automata
J. Stat. Phys., 45 (1986), pp. 875–883
- [26]
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]
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]
Universality and complexity in cellular automata
Physica D, 10 (1984), pp. 1–35
- [30]
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
Copyright © 1990 Published by Elsevier B.V.