Computational Mechanics is a technique to describe both temporal and spacial organization in systems. It complements and augments more traditional techniques in statistical physics by describing the structural regularies inherent in the system or data. In this way, computational mechanics goes beyond the a mere declaration of `order' or `randomness' and details how the order or randomness is manifest in the system. More specifically, computational mechanics seeks to construct the minimal model (called an ε-machine or causal state machine) capable of statistically reproducing the observed data. This approach leads one naturally to address the issue of the information processing capability of the system.

There is an ever burgeoning literature on computational mechanics -- both in terms of theoretical developments as well as applications to systems. Jim Crutchfield maintains a rather exhaustive page on computational mechanics called the Computational Mechanics Archive, and almost all papers of interest are listed there. My goal here is not to repeat that list, but rather to give a few select sources that I believe serve as an introduction to the field. I also give references to a few other sources that discuss concepts in complexity.

Tutorials & Introductory Materials:

• D. P. Feldman, A Brief Introduction to: Information Theory, Excess Entropy, and Computational Mechanics, unpublished (2002). Perhaps the best place to start with an introduction to computational mechanics is this tutorial written by Dave Feldman of the College of the Atlantic. Just as the title says, it offers a gentle introduction to information theory (a la Claude Shannon) and computational mechanics. Dave defines and discusses interpretations of Shannon entropy, excess entropy and entropy density. He also introduces the notions of causal states and ε-machines. Dave eschews any diversions into mathematical rigour and niceties, instead aiming to give the reader intuitive an understanding of information theory and computational mechanics. Highly recommended.
• D. P. Feldman, Some Foundations in Complex Systems: Tools and Concepts, The slides from a series of talks given at the Complex Systems Summer School in Qingdao, China (2004). Dave gives an overview of complex systems and techniques used to analyze them. While not really so much about computational mechanics, it does discuss some of the concepts used in computational mechanics.
• C. R. Shalizi, Two Lectures on Computational Mechanics: I. Mostly Leading Up to Casual States, unpublished (1998). Just a few pages, this lays out the basic notions in a `no frills' style. Sorta like a crib sheet.

More Advanced Materials:

• C. R. Shalizi and J. P. Crutchfield, "Computational Mechanics: Pattern and Prediction, Structure and Simplicity," Journal of Statistical Physics 104 (2001) 817-881. For those who want to cross all the t's and dot all the i's, look no further. The mathematical foundations are to be found here. Highly recommended.

Inference Algorithms:

• J. E. Hanson, Computational Mechanics of Cellular Automata, Ph.D. Dissertation, University of California, Berkeley (1993). Jim gives the best introduction to the sub-tree merging method of inferring epsilon-machines. His dissertation is available on the Computational Mechanics Archive.
• C. R. Shalizi, K. L. Shalizi and J. P. Crutchfield, "An Algorithm for Pattern Discovery in Time Series," cs.LG/0210025, (2002). The documentation for Causal State Splitting Reconstruction (CSSR) is available on the arxiv at http://arxiv.org/abs/cs.LG/0210025. The source code can be found at http://cscs.umich.edu/~crshalizi/CSSR/. When I need to find a machine from data, this is my technique of choice.
• D. P. Varn, Language Extraction from ZnS, Ph.D. Dissertation, University of Tennessee, Knoxville (2001). The first inference algorithm to use spectral data instead of a sequential series for machine reconstruction. As is want of students, especially Ph.D. students, Varn rather pedantically presents his method. Good for those wanting to understand the `nuts-and-bolts' of ε-machine spectral reconstruction.

Applications to Physical Systems:

• D. P. Varn and J. P. Crutchfield, "From finite to infinite range order via annealing: The causal architecture of deformation faulting in annealed close-packed crystals," Physics Letters A 324/4, 299-307 (2004). [abstract] Applies CSSR (see above) to the analysis of a simulated transformation in a layered material.
• D. P. Varn, G. S. Canright and J. P. Crutchfield, "Discovering planar disorder in close-packed structures from x-ray diffraction: Beyond the fault model," Physical Review B 66, 174110 (2002). [abstract]
• D. P. Feldman, Computational Mechanics of Classical Spin Systems, Ph.D. Thesis, University of California, Davis (1998).
• J. P. Crutchfield and D. P. Feldman, "Statistical Complexity of Simple 1D Spin Systems," Physical Review E 55 (1997) 1239R-1243R.
• W. M. Gonçalves, R. D. Pinto, J. C. Sartorelli and M. J. de Oliveira, "Inferring Statistical Complexity in the Dripping Faucet Experiment," Physica A 257 (1998) 385-389.

Computational Mechanics in Higher Dimensions:

• D. P. Feldman, Computational Mechanics of Classical Spin Systems, Ph.D. Thesis, University of California, Davis (1998).
• K. Lindgren, C. Moore and M. Nordahl, "Complexity of Two-Dimensional Patterns," Journal of Statistical Physics 91 (1998) 909-951.
• D. P. Feldman and J. P. Crutchfield, "Structural Information in Two-Dimensional Patterns: Entropy Convergence and Excess Entropy," Physical Review E 67, 051104 (2003).
• C. R. Shalizi, K. L. Shalizi and R. Haslinger, "Quantifying Self-Organization with Optimal Predictors," Physical Review Letters 93, 118701 (2004).
• K. Young, Y. Chen, J. Kornak, G. B. Matson and N. Schuff, "Summarizing Complexity in High Dimensions," Physical Review Letters 94, 098701 (2005).

Other Useful Sources:

• R. Badii and A. Politi, Complexity: Hierarchical Structures and Scaling in Physics, volume 6 of Cambridge Nonlinear Science Series. Cambridge University Press (1997). This has been described as the closest thing to a text in complexity that exists. Written for the mathematically sophisticated reader, it offers a nice survey of the tools and ideas used to understand complexity. Highly recommended.
• T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons (1991). All you'll ever need to know about information theory is here.
• G. W. Flake, The Computational Beauty of Nature, MIT Press (1998). Emphasizing the use of computers, this is a nice introduction fractals, chaos and complex systems.
• J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company (1979).
• C. R. Shalizi, "Methods and Techniques of Complex Systems Science: An Overview," in Complex Systems Science in Biomedicine, T. S. Deisboeck, J. Y. Kresh and T. B. Kepler, Eds. Plenum Publishing Corporation (2004). Available on the ArXiv at http://arxiv.org/abs/nlin.AO/0307015.