A space–time tradeoff for implementing a function with master equation dynamics
A space–time tradeoff for implementing a function with master equation dynamics
复制标题
实现具有主方程动力学的函数的时空权衡
DOI：
10.1038/s41467-019-09542-x
复制
发表时间：
2019
影响因子：
16.6
通讯作者：
Owen, Jeremy A.
中科院分区：
文献类型：
--
作者：
Wolpert, David H.;Kolchinsky, Artemy;Owen, Jeremy A.
主方程通常用于对物理系统的动力学进行建模，包括实现单值函数（例如计算机的更新步骤）的系统。然而，许多这样的函数不能通过任何主方程来实现，甚至不能近似地实现，这就提出了它们如何在现实世界中出现的问题。在这里，我们展示了如何使用主方程动力学来实现某些“可见”状态上的任何函数——如果动力学在中间时间利用额外的“隐藏”状态。我们还表明，任何实现函数的主方程都可以分解为一系列“隐藏”时间步长，这些时间步长由具有非零概率的状态到状态转换的变化来划分。在许多现实世界的情况下，更多的隐藏状态和更多的隐藏时间步都会产生成本。因此，我们得出了实现任何给定函数所需的隐藏状态数量和隐藏时间步数之间的“时空”权衡。
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.
登录
查看更多内容
有限半群的中心极限定理及其在有限状态马尔可夫链嵌入问题中的应用
DOI：
10.1007/bf00532720
发表时间：
1973
期刊：
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
影响因子：
--
作者：
S. Johansen
通讯作者：
S. Johansen
有限全变换半群中幂等的乘积：一些改进的界限
DOI：
10.1017/s0308210500025531
发表时间：
1984
期刊：
Proceedings of the Royal Society of Edinburgh: Section A Mathematics
影响因子：
--
作者：
J. Howie
通讯作者：
J. Howie
影响因子：
64.8
作者：
Berut, Antoine;Arakelyan, Artak;Lutz, Eric
通讯作者：
Lutz, Eric
从经验数据到时间不均匀的连续马尔可夫过程。
影响因子：
2.4
作者：
P. Lencastre;F. Raischel;T. Rogers;P. Lind
通讯作者：
P. Lind
影响因子：
2.6
作者：
Hasegawa, H. -H.;Ishikawa, J.;Driebe, D. J.
通讯作者：
Driebe, D. J.