A Computational Mechanics Reading List

Best Of:

J. P. Crutchfield and K. Young, "Inferring Statistical Complexity," Physical Review Letters 63 (1989) 105-108

The first paper on comp. mech., describing causal states, machine reconstruction, applications to chaotic maps, etc. Since this is all packed into four pages, a bit of a hard read.

J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction," Physica D 75 (1994) 11-54

The big progammatic paper with technical details.

K. Young and J. P. Crutchfield, "Fluctuation Spectroscopy," Chaos, Solitons, and Fractals 4 (1993) 5-39

Applying thermodynamic formalism to machine reconstruction and estimating statistical properties of the process you're interested in.

D. P. Feldman and J. P. Crutchfield, "Discovering Noncritical Organization: Statistical Mechanical, Information Theoretic, and Computational Views of Patterns in One-Dimensional Spin Systems," Santa Fe Institute Working Paper 98-04-026

Applying comp. mech. to a classic system in statistical mechanics. Good if you already know stat. mech., or need to convince someone who does that there's something new here; also, very careful exposition of information theory and of causal states.

J. E. Hanson and J. P. Crutchfield, "Computational Mechanics of Cellular Automata: An Example," Physica D (1997)

Like it says.

J. P. Crutchfield and C. R. Shalizi, "Thermodynamic Depth of Causal States: Objective Complexity via Minimal Representation," Physical Review E59 (1999): 275--283 = arxiv:cond-mat/9808147

Damn me for pride if you like, but this is the first publication of the three optimality proofs from the first lecture, in the course of showing that someone else's complexity measure isn't very good. "We subsume what we do not obliterate."

C. R. Shalizi and J. P. Crutchfield, "Computational Mechanics: Pattern and Prediction, Structure and Simplicity," Journal of Statistical Physics 104 (2001): 816--879 = arxiv:cond-mat/9907176

Long paper with the mathematical foundations of computational mechanics (somewhat more detailed and rigorous than the lecture notes accompanying this page), plus non-technical discussions of the philosophical Deep Issues and the connections to everybody else's Neat Ideas.

For people who think you're doing engineering calculations:

J. P. Crutchfield, "Discovering Coherent Structures in Nonlinear Spatial Systems," in A. Brandt, S. Ramberg, and M. Shlesinger (eds.), Nonlinear Dynamics of Ocean Waves, Singapore: World Scientific, 1992, pp. 190-216

Simple description of causal states and machine-reconstruction.

J. P. Crutchfield, "Is Anything Ever New? Considering Emergence," G. Cowan, D. Pines, and D. Melzner (eds.), Complexity: Metaphors, Models, and Reality, SFI Series in the Sciences of Complexity proceedings vol. XIX, Redwood City, Calif.: Addison-Wesley,1994, pp. 479-497.

"The Calculi of Emergence" with all the technical details removed; comprehensible to architects and trustees.

For overachievers:

J. E. Hanson and J. P. Crutchfield, "The Attractor-Basin Portrait of a Cellular Automaton," J. Statistical Physics 66 (1992) 1415-1462

There's also an important "Postscript" only in the archive.

D. R. Upper, Theory and Algorithms for Hidden Markov Models and Generalized Hidden Markov Models, Ph.D. Dissertation, Mathematics Department, University of California (February 1997).

Over two hundred pages of theorem-proof, theorem-proof.

Useful ancillary reading:

Remo Badii and Antonio Politi, Complexity: Hierarchical Structures and Scaling in Physics. Cambrige Nonlinear Science Series, vol. 6. Cambridge UP, 1997.

Closest thing to a (competent) textbook on complexity and complexity measures to be had. Also has good stuff on the connections between formal languages and dynamical systems. (There's a full review by your humble lecturer.)

Christian Beck and Friedrich Schlögl, Thermodynamics of Chaotic Systems: An Introduction. Cambridge Nonlinear Science Series, vol. 4. Cambridge UP, 1993.

Symbolic dynamics and applications of the thermodynamic formalism to chaotic systems. Actually readable.

Eugene Charniak, Statistical Language Learning. MIT Press, 1993.

Fitting different language classes to data. It's presented as teaching computers human languages, but the tricks are easily adapted to our work.

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory. NY: Wiley, 1991.

The only book on information theory you will ever need. Also covers Kolmogorov complexity.

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation.Reading, Mass.: Addison-Wesley, 1979.

Standard text on formal languages and automata theory.

Jorma Rissanen, Stochastic Complexity in Statistical Inquiry. Singapore: World Scientific, 1989.

Reviewed by your humble lecturer.

Inspirational:

Daniel Dennett, "Real Patterns," Journal of Philosophy 88 (1991) 27-51

Reprinted in Brainchildren (MIT Press, 1998), which is reviewed by your humble lecturer.

Wesley Salmon, Scientific Explanation and the Causal Structure of the World. Princeton UP, 1984.

Causal states are an example of what Salmon calls a "statistical relevance basis for causal explanation."