Fluctuation theorems for halting times of computers

Computer science theory considers abstract systems not involving thermodynamic variables. However, real world computation is subject to fluctuations and energetic constraints. Developing a physical theory of computation is thus an open challenging task at the interface of non-equilibrium thermodynamics and computer science. An important part of this task requires deriving second laws of thermodynamics for physical processes which can be modeled as implementations of abstract models of computation, such as finite automata or Turing machines. Here we extend the martingale theory of stochastic thermodynamics to derive universal second-law-like inequalities for computational machines whose halting time is a stochastic variable. We explicitly introduce new fluctuation relations for finite automata at halting times. Furthermore, we consider the thermodynamic costs of computers observing a physical system that stop the system when it achieves a pre-defined condition. We show that executing some stopping conditions require higher computational power than others.