License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.28.7
URN: urn:nbn:de:0030-drops-167922
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16792/
Go to the corresponding LIPIcs Volume Portal

Huang, Xiang ; Huls, Rachel N.

Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria

pdf-format:
LIPIcs-DNA-28-7.pdf (0.9 MB)

Abstract

Bournez, Fraigniaud, and Koegler [Bournez et al., 2012] 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].

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs.DNA.28.7,
  author =	{Huang, Xiang and Huls, Rachel N.},
  title =	{{Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16792},
  URN =		{urn:nbn:de:0030-drops-167922},
  doi =		{10.4230/LIPIcs.DNA.28.7},
  annote =	{Keywords: Population protocols, Chemical reaction networks, Analog computation}
}

Keywords: Population protocols, Chemical reaction networks, Analog computation
Collection: 28th International Conference on DNA Computing and Molecular Programming (DNA 28)
Issue Date: 2022
Date of publication: 04.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI