Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer

Abstract

Computational mechanics quantifies structure in a stochastic process via its causal states, leading to the process's minimal, optimal predictor---the $\epsilon$-machine. We extend computational mechanics to communication channels between two processes, obtaining an analogous optimal model---the $\epsilon$-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.

30 pages, 19 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/et1.htm; Updated to conform to published version plus additional corrections and updates

References in corpus (2)

• Work and information processing in a solvable model of Maxwell's demon
• Causation Entropy Identifies Indirect Influences, Dominance of Neighbors and Anticipatory Couplings

Cited by in corpus (37)

• Kochen-Specker Contextuality
• Quantum stochastic processes and quantum non-Markovian phenomena
• Stochastic thermodynamics of computation
• Information Flows? A Critique of Transfer Entropies
• Kolmogorov extension theorem for (quantum) causal modelling and general probabilistic theories
• Identifying Functional Thermodynamics in Autonomous Maxwellian Ratchets
• Above and Beyond the Landauer Bound: Thermodynamics of Modularity
• A practical, unitary simulator for non-Markovian complex processes
• Demon Dynamics: Deterministic Chaos, the Szilard Map, and the Intelligence of Thermodynamic Systems
• Correlation-powered Information Engines and the Thermodynamics of Self-Correction
• Quantum predictions for an unmeasured system cannot be simulated with a finite-memory classical system
• Optimal classical simulation of state-independent quantum contextuality
• Thermodynamical cost of some interpretations of quantum theory
• Resource theories of multi-time processes: A window into quantum non-Markovianity
• Using quantum theory to reduce the complexity of input-output processes
• Leveraging Environmental Correlations: The Thermodynamics of Requisite Variety
• Transient Dissipation and Structural Costs of Physical Information Transduction
• The classical-quantum divergence of complexity in modelling spin chains
• Causal Asymmetry in a Quantum World
• Non-Markovian quantum control as coherent stochastic trajectories
• Memory cost for simulating all quantum correlations of the Peres-Mermin scenario
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Contextuality and The Single-Qubit Stabilizer Formalism
• Single-shot quantum memory advantage in the simulation of stochastic processes
• Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators
• Quantum adaptive agents with efficient long-term memories
• Fraudulent White Noise: Flat power spectra belie arbitrarily complex processes
• Functional Thermodynamics of Maxwellian Ratchets: Constructing and Deconstructing Patterns, Randomizing and Derandomizing Behaviors
• Simulating extremal temporal correlations
• $\psi$-epistemic interpretations of quantum theory have a measurement problem
• Reconstructing Non-Markovian Open Quantum Evolution From Multi-time Measurements
• Surveying structural complexity in quantum many-body systems
• First and Second Laws of Information Processing by Nonequilibrium Dynamical States
• The fundamental thermodynamic bounds on finite models
• Unifilar Machines and the Adjoint Structure of Bayesian Filtering
• Classical Invasive Description of Informationally-Complete Quantum Processes
• Energetic advantages for quantum agents in online execution of complex strategies