###
The Calculi of Emergence:
Computation, Dynamics, and Induction

James P. Crutchfield

Physics Department

University of California

Berkeley, California 94720

**ABSTRACT: **
Defining structure and detecting the emergence of complexity in
nature are inherently subjective, though essential, scientific
activities. Despite the difficulties, these problems can be analyzed in
terms of how model-building observers infer from measurements the
computational capabilities embedded in nonlinear processes. An
observer's notion of what is ordered, what is random, and what is
complex in its environment depends directly on its computational
resources: the amount of raw measurement data, of memory, and of time
available for estimation and inference. The discovery of structure in an
environment depends more critically and subtlely, though, on how those
resources are organized. The descriptive power of the observer's chosen
(or implicit) computational model class, for example, can be an
overwhelming determinant in finding regularity in
data.

This paper presents an overview of an inductive framework --
hierarchical epsilon machine reconstruction -- in which the emergence
of complexity is associated with the innovation of new computational
model classes. Complexity metrics for detecting structure and
quantifying emergence, along with an analysis of the constraints on the
dynamics of innovation, are outlined. Illustrative examples are drawn
from the onset of unpredictability in nonlinear systems, finitary
nondeterministic processes, and cellular automata pattern recognition.
They demonstrate how finite inference resources drive the innovation of
new structures and so lead to the emergence of complexity.

J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction",
Physica D **75** (1994) 11-54. Santa Fe Institute Working Paper 94-03-016.

**Entire paper:**
[ps.gz]= 824kb
[ps]= 7117kb
[pdf]= 3796kb.

**Pages 1-47:**
[ps.gz]= 309kb
[ps]= 1231kb
[pdf]= 603kb.

**Pages 47-61:**
[ps.gz]= 436kb
[ps]= 5296kb
[pdf]= 253kb.

**NOTE: **Based on a talk given at the 36th
Oji International Seminar
on **Complex Systems -- from Complex Dynamical Systems to the Sciences
of Artificial Reality**, Fujitsu Forum, Numazu City, Japan,
5-9 April 1993.