Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation

Abstract

We adapt tools from information theory to analyze how an observer comes to synchronize with the hidden states of a finitary, stationary stochastic process. We show that synchronization is determined by both the process's internal organization and by an observer's model of it. We analyze these components using the convergence of state-block and block-state entropies, comparing them to the previously known convergence properties of the Shannon block entropy. Along the way, we introduce a hierarchy of information quantifiers as derivatives and integrals of these entropies, which parallels a similar hierarchy introduced for block entropy. We also draw out the duality between synchronization properties and a process's controllability. The tools lead to a new classification of a process's alternative representations in terms of minimality, synchronizability, and unifilarity.

25 pages, 13 figures, 1 table

References in corpus (1)

• Exact Synchronization for Finite-State Sources

Cited by in corpus (21)

• Anatomy of a Bit: Information in a Time Series Observation
• Identifying Functional Thermodynamics in Autonomous Maxwellian Ratchets
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• Optimal classical simulation of state-independent quantum contextuality
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Thermodynamics of complexity and pattern manipulation
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• Transient Dissipation and Structural Costs of Physical Information Transduction
• Information Symmetries in Irreversible Processes
• The classical-quantum divergence of complexity in modelling spin chains
• Causal Asymmetry in a Quantum World
• Information Anatomy of Stochastic Equilibria
• How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Spectral Simplicity of Apparent Complexity, Part II: Exact Complexities and Complexity Spectra
• Spectral Simplicity of Apparent Complexity, Part I: The Nondiagonalizable Metadynamics of Prediction
• The Elusive Present: Hidden Past and Future Dependency and Why We Build Models
• Prediction and Generation of Binary Markov Processes: Can a Finite-State Fox Catch a Markov Mouse?
• The fundamental thermodynamic bounds on finite models
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories