In this paper, we develop the elements of the theory of algorithmic randomness in continuous-time Markov chains (CTMCs). Our main contribution is a rigorous, useful notion of what it means for an $\textit{ individual trajectory }$ of a CTMC to be ${ \textit random }$. CTMCs have discrete state spaces and operate in continuous time. This, together with the fact that trajectories may or may not halt, presents challenges not encountered in more conventional developments of algorithmic randomness. Although we formulate algorithmic randomness in the general context of CTMCs, we are primarily interested in the $\textit{ computational }$ power of stochastic chemical reaction networks, which are special cases of CTMCs. This leads us to embrace situations in which the long-term behavior of a network depends essentially on its initial state and hence to eschew assumptions that are frequently made in Markov chain theory to avoid such dependencies. After defining the randomness of trajectories in terms of a new kind of martingale (algorithmic betting strategy), we prove equivalent characterizations in terms of constructive measure theory and Kolmogorov complexity. As a preliminary application, we prove that, in any stochastic chemical reaction network, $\textit{ every }$ random trajectory with bounded molecular counts has the $\textit{ non-Zeno property }$ that infinitely many reactions do not occur in any finite interval of time.
翻译:在本文中, 我们开发了连续时间 Markov 链( CTMCs) 的算法随机性理论要素 。 我们的主要贡献是一个严格、 有用的概念, 即对于 $\ textit{ 个人轨迹 美元来说, CTMC 的值是${\ textit 随机 $。 CTMC 有离散的状态空间, 并连续运行。 这加上轨迹可能停止, 也带来了在更传统的算法随机性发展中没有遇到的挑战 。 尽管我们在 CTMCs 的总体背景下制定了算法随机性, 我们主要感兴趣的是 $\ textit{ 计算} 个人轨迹 美元 的化学反应网络的力量, 这是 CTMC 的特殊案例。 这导致我们面对的情况是, 一个网络的长期行为基本上取决于其初始状态, 从而可以避免在 Markov 链理论中经常作出的假设, 以避免这种依赖性。 在定义新的 marting $ 值( legaltial) 的算性轨迹的随机性反应的随机性( ), 和 ASorticalticalticalticalal- trevationaltical) 战略中, 我们可以证明任何的 exticalticalalaltiew extitudealalalalalalal- acational- cal- cal- cal- acaltiewal- cal- caltiewal- strational- extractional- exaltial- extradestrationaltitionaltraction 。