zbMATH — the first resource for mathematics

The calculi of emergence: Computation, dynamics and induction. (English) Zbl 0860.68046
Summary: 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 modelbuilding 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 subtlety 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 $$\varepsilon$$-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.

MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q99 Theory of computing 68Q80 Cellular automata (computational aspects) 94A17 Measures of information, entropy 68T10 Pattern recognition, speech recognition
Full Text: