Causal architecture, complexity and self-organization in time series and cellular automata

Abstract

All self-respecting nonlinear scientists know self-organization when they see it: except when we disagree. For this reason, if no other, it is important to put some mathematical spine into our floppy intuitive notion of self-organization. Only a few measures of self-organization have been proposed; none can be adopted in good intellectual conscience. To find a decent formalization of self-organization, we need to pin down what we mean by organization. The best answer is that the organization of a process is its causal architecture—its internal, possibly hidden, causal states and their interconnections. Computational mechanics is a method for inferring causal architecture—represented by a mathematical object called the e-machine—from observed behavior. The e-machine captures all patterns in the process which have any predictive power, so computational mechanics is also a method for pattern discovery. In this work, I develop computational mechanics for four increasingly sophisticated types of process—memoryless transducers, time series, transducers with memory, and cellular automata. In each case I prove the optimality and uniqueness of the e-machine's representation of the causal architecture, and give reliable algorithms for pattern discovery. The e-machine is the organization of the process, or at least of the part of it which is relevant to our measurements. It leads to a natural measure of the statistical complexity of processes, namely the amount of information needed to specify the state of the E-machine. Self-organization is a self-generated increase in statistical complexity. This fulfills various hunches which have been advanced in the literature, seems to accord with people's intuitions, and is both mathematically precise and operational.