Abstract
Recent research into analog computing has introduced new notions of computing real numbers. Huang, Klinge, Lathrop, Li, and Lutz defined a notion of computing real numbers in real-time with chemical reaction networks (CRNs), introducing the classes \(\mathbb {R}_\text {LCRN}\) (the class of all Lyapunov CRN-computable real numbers) and \(\mathbb {R}_\text {RTCRN}\) (the class of all real-time CRN-computable numbers). In their paper, they show the inclusion of the real algebraic numbers \(ALG \subseteq \mathbb {R}_\text {LCRN}\subseteq \mathbb {R}_\text {RTCRN}\) and that \(ALG \subsetneqq \mathbb {R}_\text {RTCRN}\) but leave open where the inclusion is proper. In this paper, we resolve this open problem and show \( ALG= \mathbb {R}_\text {LCRN}\subsetneqq \mathbb {R}_\text {RTCRN}\). However, their definition of real-time computation is fragile in the sense that it is sensitive to perturbations in initial conditions. To resolve this flaw, we further require a CRN to withstand these perturbations. In doing so, we arrive at a discrete model of memory. This approach has several benefits. First, a bounded CRN may compute values approximately in finite time. Second, a CRN can tolerate small perturbations of its species’ concentrations. Third, taking a measurement of a CRN’s state only requires precision proportional to the exactness of these approximations. Lastly, if a CRN requires only finite memory, this model and Turing machines are equivalent under real-time simulations.
This research supported in part by NSF grants 1900716 and 1545028.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bournez, O., Campagnolo, M.L., Graça, D.S., Hainry, E.: The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, pp. 631–643. Springer, Heidelberg (2006). https://doi.org/10.1007/11750321_60
Bournez, O., Fraigniaud, P., Koegler, X.: Computing with large populations using interactions. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 234–246. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_23
Bournez, O., Graça, D.S., Pouly, A.: Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length. J. ACM 64(6) (2017). https://doi.org/10.1145/3127496
Cappelletti, D., Ortiz-Muñoz, A., Anderson, D.F., Winfree, E.: Stochastic chemical reaction networks for robustly approximating arbitrary probability distributions. Theoret. Comput. Sci. 801, 64–95 (2020). https://doi.org/10.1016/j.tcs.2019.08.013
Clamons, S., Qian, L., Winfree, E.: Programming and simulating chemical reaction networks on a surface. J. R. Soc. Interface 17(166), 20190790 (2020). https://doi.org/10.1098/rsif.2019.0790
Epstein, I.R., Pojman, J.A.: An Introduction to Nonlinear Chemical Dynamics: Oscillations, Patterns, and Chaos. Oxford University Press, Waves (1998)
Fages, F., Le Guludec, G., Bournez, O., Pouly, A.: Strong turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs. In: Feret, J., Koeppl, H. (eds.) CMSB 2017. LNCS, vol. 10545, pp. 108–127. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67471-1_7
Furcy, D., Summers, S.M., Wendlandt, C.: Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D. Theoret. Comput. Sci. (2021). https://doi.org/10.1016/j.tcs.2021.02.001
Hader, D., Patitz, M.J.: Geometric tiles and powers and limitations of geometric hindrance in self-assembly. Nat. Comput. 20(2), 243–258 (2021). https://doi.org/10.1007/s11047-021-09846-2
Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285–306 (1965). http://www.jstor.org/stable/1994208
Huang, X., Klinge, T.H., Lathrop, J.I.: Real-time equivalence of chemical reaction networks and analog computers. In: Thachuk, C., Liu, Y. (eds.) DNA 2019. LNCS, vol. 11648, pp. 37–53. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26807-7_3
Huang, X., Klinge, T.H., Lathrop, J.I., Li, X., Lutz, J.H.: Real-time computability of real numbers by chemical reaction networks. Nat. Comput. 18(1), 63–73 (2018). https://doi.org/10.1007/s11047-018-9706-x
Klinge, T.H., Lathrop, J.I., Lutz, J.H.: Robust biomolecular finite automata. Theoret. Comput. Sci. 816, 114–143 (2020). https://doi.org/10.1016/j.tcs.2020.01.008
Klinge, T.H., Lathrop, J.I., Moreno, S., Potter, H.D., Raman, N.K., Riley, M.R.: ALCH: an imperative language for chemical reaction network-controlled tile assembly. In: Geary, C., Patitz, M.J. (eds.) 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), vol. 174, pp. 6:1–6:22. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl (2020). https://doi.org/10.4230/LIPIcs.DNA.2020.6
Severson, E.E., Haley, D., Doty, D.: Composable computation in discrete chemical reaction networks. Distrib. Comput. (1), 1–25 (2020). https://doi.org/10.1007/s00446-020-00378-z
Turing, A.M.: On computable numbers, with an application to the Entscheidungs problem. Proc. Lond. Math. Society s2–42(1), 230–265 (1937). https://doi.org/10.1112/plms/s2-42.1.230
Acknowledgments
The authors thank anonymous reviewers for useful feedback and suggestions. This research supported in part by NSF grants 1900716 and 1545028.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Fletcher, W., Klinge, T.H., Lathrop, J.I., Nye, D.A., Rayman, M. (2021). Robust Real-Time Computing with Chemical Reaction Networks. In: Kostitsyna, I., Orponen, P. (eds) Unconventional Computation and Natural Computation. UCNC 2021. Lecture Notes in Computer Science(), vol 12984. Springer, Cham. https://doi.org/10.1007/978-3-030-87993-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-87993-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-87992-1
Online ISBN: 978-3-030-87993-8
eBook Packages: Computer ScienceComputer Science (R0)