The minimal “hidden” computer needed to implement a computation*

We consider the problem of constructing a physical process to implement some desired (single-valued) function f over a set of “visible” states X. The physical process is represented as a time-inhomogeneous continuous-time Markov chain (CTMC), for example modeling the dynamics of a driven system connected to a heat bath. A prototypical example is a physical implementation of a logical gate in a circuit.

In general, there exists functions f which are not implementable by any possible CTMC, even approximately. However, we demonstrate that for any f, an implementation is always possible if the system has access to some additional "hidden" states not in X. We then consider a natural decomposition of any such CTMC-based implementation into a countable set of discrete steps, demarcated from one another by the raising or lowering of barriers restricting probability flow between states. We demonstrate a tradeoff between the minimal number of hidden states and the minimal number of such steps needed to implement any given f. This tradeoff is analogous to space / time tradeoffs in computational circuit complexity theory - except that it arises even within each gate in such a circuit.