James P. Crutchfield
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA
Talk Abstract: I review a relatively new approach to structural complexity that defines a process's causal states and gives a procedure for finding them. It turns out that the causal-state representation---an epsilon-machine---is the minimal one consistent with accurate prediction. The claim that this representation capture's all of a process's structure derives from epsilon-machine optimality and uniqueness and on how epsilon-machines compare to alternative representations. For example, one can directly relate measures of randomness and structural complexity obtained from epsilon-machines to more familiar ones from ergodic and information theories.
These notes show the basics of epsilon-machine reconstruction, illustrating the "batch" algorithm on a number of examples, both finite and infinite state.
Note: The topics missing from these notes were done at the board, as exercises. Hopefully, some diligent soul will be enticed to encode the exercises from their notes. At which point I'll include them here.