Abstract:

From a description of one of the simplest models of computation (discrete, finite state automata), a complex dynamical system is formed. Known as a cellular automaton, it has been proved that these systems can harbor the conditions necessary for universal computation. An exploration is made into the dynamics of cellular automata in order to answer the question: is their a deep connection between the theories of dynamical systems and computation? Is there an analog for the notion of universal computation in dynamical systems theory? The thermodynamic notion of a phase-transition is proposed as the model in which computation and dynamics commingle. Christopher Langton's thesis, Chaos at the Edge of Computation, represents the culmination of the ideas presented within.

Computation, Dynamics and the Phase-Transition

Jeremy Avnet

jeremy (at) theory.org

Date: 6th June 2000

Key words and phrases: Cellular automata, complexity, computability, computation, decidability, dynamical systems, Halting Problem, phase-transition, Wolfram classes