“Non-Markovian Momentum Computing: Thermodynamically Efficient and Computation Universal”

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 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 (computational universal). Going beyond rate-equation dynamics is not only possible, but necessary if stochastic thermodynamics is to become part of the paradigm for physical information processing. The increased analytical challenges are readily addressed with recently-introduced spectral decomposition methods for nondiagnonalizable dynamics.

K. J. Ray, G. W. Wimsatt, A. B. Boyd, and J. P. Crutchfield,

Selected animations of continuous-time thermodynamically-free Fredkin gate: