THE CALCULI OF EMERGENCE - COMPUTATION, DYNAMICS AND INDUCTION

Defining structure and detecting the emergence of complexity in nature are inherently subjective, though essential, scientific activities. D espite the difficulties, these problems can be analyzed in terms of ho w model-building observers infer from measurements the computational c apabilities embedded in nonlinear processes; An observer's notion of w hat is ordered, what is random, and what is complex in its environment depends directly on its computational resources: the amount of raw me asurement data, of memory, and of time available for estimation and in ference. The discovery of structure in an environment depends more cri tically 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 findi ng regularity in data. This paper presents an overview of an inductive framework-hierarchical epsilon-machine reconstruction-in which the em ergence of complexity is associated with the innovation of new computa tional model classes. Complexity metrics for detecting structure and q uantifying 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 non deterministic processes, and cellular automata pattern recognition. Th ey demonstrate how. finite inference resources drive the innovation of new structures and so lead to the emergence of complexity.