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

Abstract

Computations are dynamical systems. The formal study of dynamical systems has revealed a spectrum of behaviors ranging from fixed-point dynamics to fully developed chaos. How does computation--especially universal computation--fit into this spectrum of dynamical behaviors? This thesis addresses the question via the study of Cellular Automata (CA). CA are discrete space/time dynamical systems which (a) exhibit the full spectrum of dynamical behaviors, and (b) are known to support universal computation. Therefore, if we can locate the CA which support computation in the full spectrum of CA dynamics, we may learn a great deal about the general relationship between computation and dynamics. We find that, with an appropriate parameterization of the space of CA, we can order CA dynamical behaviors from fixed-point, through periodic, to chaotic behavior. We also find that there exists a phase-transition in this sequence, located between the periodic and the chaotic rules. The dynamics in the vicinity of this phase-transition are the most complex exhibited anywhere in the spectrum, both qualitatively and quantitatively. These complex rules exhibit many of the properties deemed necessary to support computation, and therefore we are able to identify computation with a phase-transition in the space of CA. We are also able to explain the existence of--and relationships between--previously suggested classes of CA behavior (such as the four Wolfram classes) in terms of this phase-transition in the space of CA. The results reported here suggest a general relationship between computation and phase-transitions, especially second-order phase-transitions. When viewed from this perspective, one is able to explain a great deal of the phenomenology of computation, such as the existence of complexity classes, computability classes, and the Halting problem. This view also leads to some new suggestions about the nature and origin of such complex natural phenomena as Life and Intelligence.