Thermodynamics of periodic processes with unidirectional transitions and stochastic finishing times --- the case of digital computers.*

Developing a thermodynamic theory of computation is a challenging task that requires addressing 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 these difficulties by extending martingale theory of non-equilibrium thermodynamics to non-stationary Markovian dynamics with broken local detailed balance and absolute irreversibility. The starting point of this new framework is some new universal fluctuation relations and second-law-like inequalities that provide both lower and upper bounds on the mismatch cost associated with any periodic process - in particular the periodic processes underlying all current digital computation. Crucially, these bounds apply even if the underlying periodic process has stochastic stopping times, as it does in many computational machines. We illustrate our results by analyzing deterministic finite automata processing bit strings, one of the fundamental models of computation from theoretical computer science. In particular, we 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 other connections between computer science and stochastic resetting. Our results, while motivated from the computational context, are applicable far more broadly.