Wolpert David H, Kolchinsky Artemy, Owen Jeremy A
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM, 87501, USA.
Arizona State University, Tempe, 85281, AZ, USA.
Nat Commun. 2019 Apr 15;10(1):1727. doi: 10.1038/s41467-019-09542-x.
Master equations are commonly used to model the dynamics of physical systems, including systems that implement single-valued functions like a computer's update step. However, many such functions cannot be implemented by any master equation, even approximately, which raises the question of how they can occur in the real world. Here we show how any function over some "visible" states can be implemented with master equation dynamics-if the dynamics exploits additional, "hidden" states at intermediate times. We also show that any master equation implementing a function can be decomposed into a sequence of "hidden" timesteps, demarcated by changes in what state-to-state transitions have nonzero probability. In many real-world situations there is a cost both for more hidden states and for more hidden timesteps. Accordingly, we derive a "space-time" tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given function.
主方程通常用于对物理系统的动力学进行建模，包括那些实现单值函数的系统，比如计算机的更新步骤。然而，许多这样的函数无法由任何主方程实现，哪怕是近似实现，这就引发了它们如何能在现实世界中出现的问题。在这里我们展示了，任何关于某些“可见”状态的函数如何能用主方程动力学来实现——前提是动力学在中间时刻利用额外的“隐藏”状态。我们还表明，任何实现一个函数的主方程都可以分解为一系列“隐藏”时间步，这些时间步由具有非零概率的状态到状态的转变的变化来划分。在许多现实世界的情况中，更多的隐藏状态和更多的隐藏时间步都会带来成本。因此，我们推导出了实现任何给定函数所需的隐藏状态数量和隐藏时间步数量之间的“时空”权衡。
