  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.
