From a description of one of the simplest models of computation
(deterministic finite 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 there 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.
The original LaTeX source was processed with Latex2HTML and
subsequently tweaked. Mathematical formulae are represented as inline
PNG images. When adequate web-browsers exist, I will provide a MathML
version.
If you are interested in printing this document, the original postscript
file is available for download. It has been compressed using GZip. I
have never encountered a postscript viewer that can not read gzipped
postscript files. You should not have to do anything special to this
file. If you require an uncompressed version, please email me.
Jeremy Avnet; brainsik;
email: jeremy-www@theory.org
Fri Dec 15 11:28:21 PST 2000