Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times

Abstract

Developing a thermodynamic theory of computation is a challenging task at the interface of non-equilibrium thermodynamics and computer science. In particular, this task requires dealing with difficulties such as stochastic halting times, unidirectional (possibly deterministic) transitions, and restricted initial conditions, features common in real-world computers. Here, we present a framework which tackles all such difficulties by extending the martingale theory of non-equilibrium thermodynamics to generic non-stationary Markovian processes, including those with broken detailed balance and/or absolute irreversibility. We derive several universal fluctuation relations and second-law-like inequalities that provide both lower and upper bounds on the intrinsic dissipation (mismatch cost) associated with any periodic process -- in particular the periodic processes underlying all current digital computation. Crucially, these bounds apply even if the process has stochastic stopping times, as it does in many computational machines. We illustrate our results with exhaustive numerical simulations of deterministic finite automata (DFA) processing bit strings, one of the fundamental models of computation from theoretical computer science. We also provide universal equalities and inequalities for the acceptance probability of words of a given length by a deterministic finite automaton in terms of thermodynamic quantities, and outline connections between computer science and stochastic resetting. Our results, while motivated from the computational context, are applicable far more broadly.

24 + 8 pages, 10 figures; v2: minor changes, references added; v3: presentation improved, extra appendix added, footnotes and references added

References in corpus (25)

• Thermodynamic uncertainty relation for biomolecular processes
• Dissipation: The phase-space perspective
• High-precision test of Landauer's principle in a feedback trap
• Path-integral analysis of fluctuation theorems for general Langevin processes
• Thermodynamic Unification of Optimal Transport: Thermodynamic Uncertainty Relation, Minimum Dissipation, and Thermodynamic Speed Limits
• Stochastic resetting: A (very) brief review
• Finite-time Landauer principle
• Lower bounds on dissipation upon coarse graining
• Large work extraction and the Landauer limit in a continuous Maxwell demon
• Integral Fluctuation Theorems for Stochastic Resetting Systems
• Stochastic thermodynamics with information reservoirs
• Minimal Model of Stochastic Athermal Systems: Origin of Non-Gaussian Noise
• Variance Sum Rule for Entropy Production
• Quantum nonequilibrium equalities with absolute irreversibility
• Dynamics of information erasure and extension of Landauer's bound to fast processes
• Kinetic uncertainty relation on first passage time for accumulated current
• Quantum Martingale Theory and Entropy Production
• A Nernst heat theorem for nonequilibrium jump processes
• Calorimetry for active systems
• State retrieval beyond Bayes' retrodiction
• Extreme value statistics of edge currents in Markov jump processes and their use for entropy production estimation
• Dissipation reduction and information-to-measurement conversion in DNA pulling experiments with feedback protocols
• Martingale-induced local invariance in Progressive Quenching
• Survival and extreme statistics of work, heat, and entropy production in steady-state heat engines
• Upper bound for quantum entropy production from entropy flux

Cited by in corpus (13)

• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• Martingales for physicists: A treatise on stochastic thermodynamics and beyond
• Thermodynamic Bounds on Symmetry Breaking in Linear and Catalytic Biochemical Systems
• Broken detailed balance and entropy production in directed networks
• Landauer Principle and Thermodynamics of Computation
• Gambling Carnot Engine
• Thermodynamic bounds and symmetries in first-passage problems of fluctuating currents
• Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations
• Thermodynamic inference in molecular motors: a Martingale approach
• Improving the efficiency of finite-time memory erasure with potential barrier shaping
• Join gate with memory in token-conserving Brownian circuits and the thermodynamic cost
• Thermodynamic Cost of Random-Time Protocols
• Coarse-grained quantum thermodynamics: Observation-dependent quantities, observation-independent laws