Title: The minimal hidden computer needed to implement a visible computation,
Abstract: Master equations are commonly used to model the dynamics of physical systems.
Surprisingly, many deterministic maps $x \rightarrow f(x)$ cannot be
implemented by any master equation, even approximately. This raises the
question of how they arise in real-world systems like digital computers. We
show that any deterministic map over some "visible" states can be implemented
with a master equation--but only if additional "hidden" states are dynamically
coupled to those visible states. We also show that any master equation
implementing a given map can be decomposed into a sequence of "hidden"
timesteps, demarcated by changes in what transitions are allowed under the rate
matrix. Often there is a real-world cost for each additional hidden state, and
for each additional hidden timestep. We derive the associated "space/time"
tradeoff between the numbers of hidden states and of hidden timesteps needed to
implement any given $f(x)$.