arXiv:2608.11362cs.CCcs.CL2026-08

用可逆化学反应网络计算实数,揭示其与经典计算模型的联系

RevCRN: Reversible Analog Computation using Chemical Reaction Networks

论文配图:RevCRN: Reversible Analog Computation using Chemical Reaction Networks
图 1 · 摘自论文原文
  • 提出可逆化学反应网络(RevCRN)计算实数的新框架
  • 证明有理数是可逆网络可计算实数的真子集,1物种情形等于代数数
  • 为低能耗生物计算提供理论基础,适合计算生物学与理论计算机研究者

图灵机对实数与函数的可计算性研究是20世纪中叶以来理论计算机科学的核心议题。20世纪后期发现,化学反应可作为计算基础,基于化学反应网络(CRN)模型。近年来,确定性化学反应网络(DCRN)在实数计算方面取得进展,识别出多个可计算实数类。与此同时,兰道尔与本内特的工作表明,可逆计算在能量效率上显著优于不可逆方法,推动了该领域的深入研究。本文研究可逆化学反应网络(RevCRN)对实数的可计算性。主要贡献:(1) 建立了各类CRN可计算实数之间的关系,关键结果包括:(i) 有理数ℚ是可逆网络可计算实数ℝ_{RevCRN}的严格子集;(ii) 正代数数ALG、李雅普诺夫CRN可计算实数ℝ_{LCRN}、1物种可逆网络可计算实数ℝ_{RevCRN}^{1s}三者相等;(iii) 实时CRN ℝ_{RTCRN}与可逆网络ℝ_{RevCRN}存在非空交集;(iv) 满足详细平衡的可逆网络可计算实数ℝ^{DetBal}_{RevCRN}是代数数的子集;(2) 探索了ℝ_{RevCRN}内部是否存在层级结构。最后,开放了ℝ_{RevCRN}与ℝ_{RTCRN}的确切关系问题,并推测可逆网络可计算实数存在一般层级。

原文摘要 · Abstract (English)

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

可逆计算化学计算实数计算理论生物

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。