Causal states, 1989 to 2003.

The answer to a hand-chosen representation was to let the process define its own states: group histories by the future they predict.

1. 1989

   Causal states and the epsilon-machine

   Crutchfield and Young define the causal state, the machine built from causal states (the epsilon-machine), and statistical complexity: how much information a process stores. Computational mechanics is named.

   J. P. Crutchfield and K. Young, Inferring statistical complexity, Physical Review Letters 63 (1989) 105-108.

2. 1990

   Computation at the onset of chaos

   At the boundary between order and chaos, processes carry the most structure, and their machines grow without limit.

   J. P. Crutchfield and K. Young, Computation at the onset of chaos, in W. Zurek (ed.), Entropy, Complexity, and the Physics of Information, SFI Studies in the Sciences of Complexity VIII (1990) 223-269.

3. 1994

   A hierarchy of machines

   When one level of model runs out, the next is built over its states: an account of how new structure emerges.

   J. P. Crutchfield, The calculi of emergence: computation, dynamics, and induction, Physica D 75 (1994) 11-54.

4. 1999 and 2001

   The proof: minimal and optimal

   Shalizi and Crutchfield prove that the causal states are the unique, minimal representation that predicts a process as well as anything can.

   J. P. Crutchfield and C. R. Shalizi, Physical Review E 59 (1999) 275-283; C. R. Shalizi and J. P. Crutchfield, Computational mechanics: pattern and prediction, structure and simplicity, Journal of Statistical Physics 104 (2001) 817-879.

5. 2002 and 2003

   Learning the states from data

   An algorithm recovers causal states from a time series, and the convergence of entropy measures shows what finite data can and cannot reveal.

   C. R. Shalizi, K. L. Shalizi and J. P. Crutchfield, Pattern discovery in time series, part I, arXiv:cs.LG/0210025 (2002); J. P. Crutchfield and D. P. Feldman, Regularities unseen, randomness observed, CHAOS 13 (2003) 25-54.