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.