Stochastic Thermodynamics of Finite Automata

The deterministic finite automaton (DFA) is a foundational model of computation. It is implemented by digital computational systems ranging from circuits to compilers, and is ubiquitous in biological systems. The state space of a DFA consists of a set of internal states, strings of input symbols, and a pointer indicating the current input symbol. The complexity of a DFA is its number of internal states. Here we investigate the stochastic thermodynamics of running a DFA, using an inclusive, Hamiltonian formulation, in which we partition the DFA's state space into a system of interest (SOI) and a separate environment. In the first partition, the SOI is the pointer and the DFA's internal state. We prove that in any set of DFAs that behave equivalently, the DFA with minimal complexity is the one with the least entropy production. This result holds for every iteration of the DFA, and for any distribution over input strings. In the second partition, the SOI is the pointer, the internal state, and the current symbol. Under this partition, the DFA is formally identical to a Markov information source. We exploit this to establish a set of results on the thermodynamics of block codes for information sources.