Computational Mechanics of Input-Output Processes:
Structured transformations and the ε-transducer

Nix Barnett
James P. Crutchfield

Complexity Sciences Center
Mathematics Department
Physics Department
University of California at Davis
Davis, CA 95616

ABSTRACT: Computational mechanics quantifies structure in a stochastic process via its causal states, leading to the process's minimal, optimal predictor—the ε-machine. We extend computational mechanics to communication channels between two processes, obtaining an analogous optimal model—the ε-transducer—of the stochastic mapping between them. Here, we lay the foundation of a structural analysis of communication channels, treating joint processes and processes with input. The result is a principled structural analysis of mechanisms that support information flow between processes. It is the first in a series on the structural information theory of memoryful channels, channel composition, and allied conditional information measures.

Nix Barnett and James P. Crutchfield, "Computational Mechanics of Input-Output Processes: Structured transformations and the ε-transducer", Journal of Statistical Physics 161:2 (2015) 404-451.
[pdf] 655 KB
Santa Fe Institute Working Paper 14-12-046. [cond-mat.stat-mech].