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 (14)

• 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
• 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
• Quantum nonequilibrium equalities with absolute irreversibility
• Quantum Martingale Theory and Entropy Production
• Dissipation reduction and information-to-measurement conversion in DNA pulling experiments with feedback protocols
• Upper bound for quantum entropy production from entropy flux

Cited by in corpus (11)

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