Ray, Kyle J.; Alexander B. Boyd; Gregory W. Wimsatt and James P. Crutchfield
Practical, useful computations are instantiated via physical processes. Information must be stored and updated within a system’s configurations, whose energetics determine a computation’s cost. To describe thermodynamic and biological information processing, a growing body of results embraces rate equations as the underlying mechanics of computation. Strictly applying these continuous-time stochastic Markov dynamics, however, precludes a universe of natural computing. Within this framework, operations as simple as a NOT gate (flipping a bit) and swapping two bits, and swapping bits are inaccessible. We show that expanding the toolset to continuous- time hidden Markov dynamics substantially removes the constraints, by allowing information to be stored in a system’s latent states. We demonstrate this by simulating computations that are impossible to implement without hidden states. We design and analyze a thermodynamically costless bit flip, providing a counterexample to rate- equation modeling. We generalize this to a costless Fredkin gate—a key operation in reversible computing that is Turing complete (computation universal). Going beyond rate-equation dynamics is not only possible but also necessary if stochastic thermodynamics is to become part of the paradigm for physical information processing.