Document Open Access Logo

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

Authors Xiang Huang , Rachel N. Huls

PDF
Thumbnail PDF

File

LIPIcs.DNA.28.7.pdf
  • Filesize: 0.85 MB
  • 22 pages

Document Identifiers

Author Details

Xiang Huang
  • Department of Computer Science, University of Illinois Springfield, USA
Rachel N. Huls
  • Department of Mathematics, University of Illinois Springfield, USA

Funding

  • Huang, Xiang: This research was supported in part by NSF grants 1545028 and 1900716.
  • Huls, Rachel N.: This research was supported in part by the University of Illinois Springfield Leadership Lived Experience (LLE) initiative.

Acknowledgements

We thank Titus Klinge for providing the motivating example in Section 1.

Cite As Get BibTex

Xiang Huang and Rachel N. Huls. Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DNA.28.7

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].

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
  • Theory of computation → Probabilistic computation
  • Theory of computation → Abstract machines
Keywords
  • Population protocols
  • Chemical reaction networks
  • Analog computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, and Przemysław Uznański. Robust detection in leak-prone population protocols. In International Conference on DNA-Based Computers, pages 155-171. Springer, 2017. Google Scholar
  2. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  3. Guillaume Aupy and Olivier Bournez. On the number of binary-minded individuals required to compute. Theoretical Computer Science, 412(22):2262, 2011. Google Scholar
  4. Sanjay P. Bhat and Dennis S. Bernstein. Nontangency-based lyapunov tests for convergence and stability in systems having a continuum of equilibria. SIAM Journal on Control and Optimization, 42(5):1745-1775, 2003. Google Scholar
  5. Olivier Bournez, Philippe Chassaing, Johanne Cohen, Lucas Gerin, and Xavier Koegler. On the convergence of population protocols when population goes to infinity. Applied Mathematics and Computation, 215(4):1340-1350, 2009. Google Scholar
  6. Olivier Bournez, Pierre Fraigniaud, and Xavier Koegler. Computing with large populations using interactions. In Proceedings of the 37th International Conference on Mathematical Foundations of Computer Science, pages 234-246. Springer, 2012. Google Scholar
  7. Olivier Bournez, Daniel S. Graça, and Amaury Pouly. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length. Journal of the ACM, 64(6):38, 2017. Google Scholar
  8. Vannevar Bush. The differential analyzer. A new machine for solving differential equations. Journal of the Franklin Institute, 212(4):447-488, 1931. Google Scholar
  9. David C. Carothers, G. Edgar Parker, James S. Sochacki, and Paul G. Warne. Some properties of solutions to polynomial systems of differential equations. Electronic Journal of Differential Equations (EJDE)[electronic only], 2005:Paper-No, 2005. Google Scholar
  10. David Cox, John Little, and Donal OShea. Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media, 2013. Google Scholar
  11. David Doty and Eric Severson. Ppsim: A software package for efficiently simulating and visualizing population protocols. In International Conference on Computational Methods in Systems Biology, pages 245-253. Springer, 2021. Google Scholar
  12. Bartłomiej Dudek and Adrian Kosowski. Universal protocols for information dissemination using emergent signals. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 87-99, 2018. Google Scholar
  13. François Fages, Guillaume Le Guludec, Olivier Bournez, and Amaury Pouly. Strong Turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs. In Proceedings of the 15th International Conference on Computational Methods in Systems Biology, pages 108-127. Springer International Publishing, 2017. Google Scholar
  14. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  15. Willem Fletcher, Titus H. Klinge, James I. Lathrop, Dawn A. Nye, and Matthew Rayman. Robust real-time computing with chemical reaction networks. In International Conference on Unconventional Computation and Natural Computation, pages 35-50. Springer, 2021. Google Scholar
  16. Lucas Gerin and Marie Albenque. On the algebraic numbers computable by some generalized ehrenfest urns. Discrete Mathematics & Theoretical Computer Science, 14, 2012. Google Scholar
  17. Daniel S. Graça. Some recent developments on shannon’s general purpose analog computer. Mathematical Logic Quarterly: Mathematical Logic Quarterly, 50(4-5):473-485, 2004. Google Scholar
  18. Daniel Silva Graça and José Félix Costa. Analog computers and recursive functions over the reals. Journal of Complexity, 19(5):644-664, 2003. Google Scholar
  19. Daniel S. Graça, Manuel L. Campagnolo, and Jorge Buescu. Computability with polynomial differential equations. Advances in Applied Mathematics, 40(3):330-349, 2008. Google Scholar
  20. Indranil Gupta, Mahvesh Nagda, and Christo Frank Devaraj. The design of novel distributed protocols from differential equations. Distributed Computing, 20(2):95-114, 2007. Google Scholar
  21. Vera Hárs and János Tóth. On the inverse problem of reaction kinetics. In Colloquia Mathematica Societatis János Bolyai, 30: Qualitative Theory of Differential Equations, pages 363-379, 1981. Google Scholar
  22. Xiang Huang. Chemical Reaction Networks: Computability, Complexity, and Randomness. PhD thesis, Iowa State University, 2020. Google Scholar
  23. Xiang Huang, Titus H. Klinge, and James I. Lathrop. Real-time equivalence of chemical reaction networks and analog computers. In International Conference on DNA Computing and Molecular Programming, pages 37-53. Springer, 2019. Google Scholar
  24. Xiang Huang, Titus H. Klinge, James I. Lathrop, Xiaoyuan Li, and Jack H. Lutz. Real-time computability of real numbers by chemical reaction networks. Natural Computing, 18(1):63-73, 2019. Google Scholar
  25. Titus H. Klinge. Modular and Robust Computation with Deterministic Chemical Reaction Networks. PhD thesis, Iowa State University, 2016. Google Scholar
  26. Thomas G. Kurtz. The relationship between stochastic and deterministic models for chemical reactions. The Journal of Chemical Physics, 57(7):2976-2978, 1972. Google Scholar
  27. Leonard Lipshitz and Lee A Rubel. A differentially algebraic replacement theorem, and analog computability. Proceedings of the American Mathematical Society, 99(2):367-372, 1987. Google Scholar
  28. G. Edgar Parker and James S. Sochacki. Implementing the picard iteration. Neural, Parallel & Scientific Computations, 4(1):97-112, 1996. Google Scholar
  29. Marion B Pour-El and Jonathan I Richards. Abstract computability and its relations to the general purpose analog computer. Transactions of the American Mathematical Society, 199:1-28, 1974. Google Scholar
  30. Claude E Shannon. Mathematical theory of the differential analyzer. Studies in Applied Mathematics, 20(1-4):337-354, 1941. Google Scholar
  31. Justin R. Smith. Introduction to Algebraic Geometry. Justin Smith, 2014. Google Scholar
  32. Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(1):230-265, 1936. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact