Computational Mechanics: Pattern and Prediction, Structure and Simplicity

Cosma Rohilla Shalizi and James P. Crutchfield
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA

Abstract

Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation---an epsilon-machine---is the minimal one consistent with accurate prediction. We establish several results on epsilon-machine optimality and uniqueness and on how epsilon-machines compare to alternative representations. Further results relate measures of randomness and structural complexity obtained from epsilon-machines to those from ergodic and information theories.

Citation

C. R. Shalizi and J. P. Crutchfield Computational Mechanics: Pattern and Prediction, Structure and Simplicity, Journal of Statistical Physics 104 (2001) 817-879. Santa Fe Insitute Working Paper 99-07-044. arXiv.org/abs/cond-mat/9907176.

To transfer a copy of the entire paper click on its title.