Computational Mechanics Lectures
A Computational Mechanics Reading List
All of these can be had from the Computational
Mechanics Archive unless otherwise noted.
- 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,
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
- 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
- C. R. Shalizi and J. P. Crutchfield, "Computational Mechanics:
Pattern and Prediction, Structure and Simplicity," Journal of Statistical
Physics 104 (2001): 816--879
- 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:
Also in the archive.
- 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.
Still more in the archive.
- 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
- Fitting different language classes to data. It's presented as
teaching computers human languages, but the tricks are easily adapted to our
- 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
- 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.
That is, some philosophers.
- 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."