Skip to main content
eScholarship
Open Access Publications from the University of California

UC Davis

UC Davis Previously Published Works bannerUC Davis

Non-Markovian momentum computing: Thermodynamically efficient and computation universal

  • Author(s): Ray, KJ;
  • Boyd, AB;
  • Wimsatt, GW;
  • Crutchfield, JP
  • et al.
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View