» complexity » cdpt » Computation, Dynamics and the Phase-Transition - Home

Computation, Dynamics and the Phase-Transition

A Senior Thesis in Mathematics


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.

Available Formats


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.

Print-Quality (4Megs)

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:
Fri Dec 15 11:28:21 PST 2000