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.
The reconstructed r = 3 epsilon machine for an experimental
zinc sulpide disordered crystal. The strong self-loop
transition probabilities between causal states S_0 and
S_7, as well as their large asymptotic state probabilities,
suggest that the ... 0000 ... and ... 1111 ... structures
are important. The absence of the transition between CSs
xxx and xxx implies that the 0011 sequence, and
therefore the CSC associated with the 6H structure, is not present.
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:
J. P. Crutchfield, "Between order and chaos",
Nature Physics8, 17 - 24 (2012). Jim gives a basic introduction to the notions
of computational mechanics at a level appropriate for a reader with some technical background
but not familiar with area. Highly recommended.
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 and J. P. Crutchfield,
"Computational Mechanics: Pattern and Prediction, Structure and Simplicity,"
Journal of Statistical Physics104 (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]
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.
K. Lindgren, C. Moore and M. Nordahl,
"Complexity of Two-Dimensional Patterns,"
Journal of Statistical Physics91 (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 Letters93, 118701 (2004).
K. Young, Y. Chen, J. Kornak, G. B. Matson and N. Schuff,
"Summarizing Complexity in High Dimensions,"
Physical Review Letters94, 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.