论文标题
使用具有平衡连续的大型人口协议计算实数
Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria
论文作者
论文摘要
如果伯内斯（Bournez），弗雷尼亚德（Fraigniaud）和科格勒（Koegler）在[0,1]中定义了一个数字，则可以通过其大型人口协议（LPP）模型来计算，如果随着人口增长到无限限，一组标记状态中的代理的比例随着时间的推移会收敛到上述数量。但是，该概念限制了与LPP相关的普通微分方程（ODE），仅具有有限的许多均衡。该限制对模型构成了内在限制。结果，当且仅当它是代数时，即在该概念下，就可以计算一个数字，而不是在代数时计算一个数字。 在本文中，我们提高了对均衡的规定要求。也就是说，我们考虑具有平衡连续的系统。我们表明，从[0,1]中的所有数字都可以通过有限的通用类模拟计算机（GPAC）或化学反应网络（CRN）计算的所有数字，也可以由LPP在此新定义下计算。这意味着一系列丰富的数字（例如，Euler常数的倒数，$π/4 $，Euler的$γ$，加泰罗尼亚的常数和Dottie编号）都是LPP的计算。我们的证明是建设性的：我们开发了一种将有限的GPAC/CRN转移到LPP中的算法。我们的算法还固定了Bournez等人的LPP构造中的差距，该LPP旨在计算[0,1]中的任何任意代数数。
Bournez, Fraigniaud, and Koegler defined a number in [0,1] as computable by their Large-Population Protocol (LPP) model, if the proportion of agents in a set of marked states converges to said number over time as the population grows to infinity. The notion, however, restricts the ordinary differential equations (ODEs) associated with an LPP to have only finitely many equilibria. This restriction places an intrinsic limitation on the model. As a result, a number is computable by an LPP if and only if it is algebraic, namely, not a single transcendental number can be computed under this notion. In this paper, we lift the finitary requirement on equilibria. That is, we consider systems with a continuum of equilibria. We show that essentially all numbers in [0,1] that are computable by bounded general-purpose analog computers (GPACs) or chemical reaction networks (CRNs) can also be computed by LPPs under this new definition. This implies a rich series of numbers (e.g., the reciprocal of Euler's constant, $π/4$, Euler's $γ$, Catalan's constant, and Dottie number) are all computable by LPPs. Our proof is constructive: We develop an algorithm that transfers bounded GPACs/CRNs into LPPs. Our algorithm also fixes a gap in Bournez et al.'s construction of LPPs designed to compute any arbitrary algebraic number in [0,1].
