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. (Not on line.)

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,'' J. Stat. Phys. (1998) submitted.
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: When Paddling around in Occam's Pool, Shallowness Is a Virtue,'' SFI working paper 98-06-047

So sue me; 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.''

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 ``[ps]'' 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.

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.

Inspirational:

Mario Bunge, Causality and Modern Science. NY: Dover, n.d.

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

Reprinted in Brainchildren (MIT Press, 1998).

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.''

Vaporware

J. P. Crutchfield and J. E. Hanson, Computational Mechanics of Cellular Process. Princeton UP.

The Princeton catalogue says this book is already available, but don't believe it.

C. R. Shalizi and J. P. Crutchfield, ``Foundations of Computational Mechanics''

More rigor than you can shake a stick at. Unfortunately it's not written yet, but will be.