Computational Mechanics

Computational mechanics is a framework for discovering the minimal computational model that captures all the statistically significant structure of a stochastic process. Developed primarily by James Crutchfield and collaborators at the Santa Fe Institute, it treats prediction as a problem in machine inference: given observations, what is the simplest model that reproduces the observed statistics and predicts the future as well as possible?

The central object is the epsilon-machine — the minimal unifilar hidden Markov model that captures all the causal states of a process. A causal state is an equivalence class of pasts that make the same prediction about the future. The entropy of the causal state distribution — the statistical complexity — measures how much memory the process must keep to be optimally predictive. This is neither the raw data volume nor the entropy rate, but the structured information: what must be remembered versus what can be forgotten.

Computational mechanics connects Information Theory to dynamical systems by showing that every stochastic process has an intrinsic computational architecture. The epsilon-machine is not an approximation; it is the unique minimal model that captures all predictive structure. This framework reveals that randomness and structure are not opposites but complementary: a process can have high entropy rate (unpredictable) and high statistical complexity (deeply structured), or low entropy rate and low complexity, or any combination. The taxonomy of processes by their entropy-complexity coordinates is a map of the possible kinds of order.