Enumerating Finitary Processes.

We show how to efficiently enumerate a class of finite-memory stochastic processes using the causal representation of ϵ-machines. We characterize ϵ-machines in the language of automata theory and adapt a recent algorithm for generating accessible deterministic finite automata, pruning this over-large class down to that of ϵ-machines. As an application, we exactly enumerate topological ϵ-machines up to eight states and six-letter alphabets.

The organization of intrinsic computation: complexity-entropy diagrams and the diversity of natural information processing.

Intrinsic computation refers to how dynamical systems store, structure, and transform historical and spatial information. By graphing a measure of structural complexity against a measure of randomness, complexity-entropy diagrams display the different kinds of intrinsic computation across an entire class of systems. Here, we use complexity-entropy diagrams to analyze intrinsic computation in a broad array of deterministic nonlinear and linear stochastic processes, including maps of the interval, cellular automata, and Ising spin systems in one and two dimensions, Markov chains, and probabilistic minimal finite-state machines.