Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation--an e-machine--is the minimal one consistent with accurate prediction. We establish several results on e-machine...

We critique the measure of complexity introduced by Shiner, Davison, and Landsberg in Ref. [1]. In particular, we point out that it is over-universal, in the sense that it has the same dependence on disorder for structurally distinct systems. We also point out a misinterpretation of a result...

Thermodynamic depth is an appealing but flawed complexity measure. It depends on a set of macroscopic states for a system, but neither its original introduction by Lloyd and Pagels nor any follow-up work has considered how to select these states. Depth, therefore, is at root subjective....

Particle-like objects are observed to propagate and interact in many spatially extended dynamical systems. For one of the simplest classes of such systems, one-dimensional cellular automata, we establish a rigorous upper bound on the number of distinct products that these interactions can...

Computational mechanics is a method for discovering, describing and quantifying patterns, using tools from statistical physics. It contructs optimal, minimal models of stochastic processes and their underlying causal structures. These models tell us about the intrinsic computation embedded...

Discovering relevant, but possibly hidden, variables is a key step in constructing useful and predictive theories about the natural world. This brief note explains the connections between three approaches to this problem: the recently introduced information-bottleneck method, the computational...

Dynamics is not enough for cognition nor is it a substitute for information processing aspects of brain behavior. Moreover, dynamics and computation are not at odds, but are quite compatible. They can be synthesized so that any dynamical system can be analyzed in terms of its intrinsic...

We introduce a class of embedded-particle models for describing the emergent computational strategies observed in cellular automata (CAs) that were evolved for performing certain computational tasks. The models are evaluated by comparing their estimated performances with the actual performances...

We present exact results for two complementary measures of spatial structure generated by 1D spin systems with finite-range interactions. The first, excess entropy, measures the apparent spatial memory stored in configurations. The second, statistical complexity, measures the amount of memory...

We illustrate and extend the techniques of computational mechanics in explicating the structures that emerge in the space-time behavior of elementary one-dimensional cellular automaton rule 54. The CA's dominant regular domain filter is constructed to locate and classify defects in the domain....