Excerpt

Introduction

Computation—defined as the pathway for information to be input, to be processed mechanically, and to be output in a useful way (Evans 2011)—takes place not only in the myriad of electronic devices we use daily but also in living systems. Life carries out computations mostly by using chemical support: inputs are chemical substances, the mechanical processing occurs via chemical reaction mechanisms, and the result is chemical as well. Machines carrying out computations are typically referred to as automata (Hopcroft, Motwani, and Ullman 2006); hence, to a large extent, living systems can be viewed as chemical automata (Bray 2009). Classic automata are arranged hierarchically from simplest to most powerful (Hopcroft, Motwani, and Ullman 2006): finite automata, then pushdown automata, and, at the top of the hierarchy, Turing machines (Turing 1936).

Although the subject of this contribution already has an interesting history, we give here a brief, personal, and short summary of some interesting developments in the field of chemical computation. Interest in chemical computing dates back to the early 1970s, when Conrad (1972) studied information processing in molecular systems and how it differs from electronic digital computing. A theoretical chemical diode was first suggested by Okamoto, Sakai, and Hayashi (1987), an idea that Hjelmfelt, Weinberger, and Ross (1991) further developed to suggest that neural networks and chemical automata could be constructed connecting such chemical diodes. In the 1990s, Magnasco (1997) studied the Turing completeness of chemical kinetics. The first experimental realization of chemical AND and OR logic gates using reaction diffusion was achieved in 1995 by Tóth and Showalter (1995), followed by XOR gates (Adamatzky and Lacy Costello 2002) and counters (Górecki, Yoshikawa, and Igareshi 2003), and still is an active area of research due to the difficulties associated to linking many gates to carry out more advanced computations. Computations carried out in a more native way, without requiring diffusion, have been suggested using complex biomolecules such as DNA (Adleman 1994; Benenson 2009) or chromatin (Prohaska, Stadler, and Krakauer 2010; Bryant 2012). In summary, most artificial approaches to chemical computing, inspired by living systems, focus on reaction–diffusion systems mostly representing logic gates or use complex biomolecules to solve very specific problems.

Our approach (Pérez-Mercader, Dueñas-Díez, and Case 2017) differs from the aforementioned work in that we use the power of chemistry, and the molecular recognition associated with the occurrence of chemical reactions, in a one-pot reactor, that is, a single well-mixed container where multiple rounds of reactions can take place, without using external geometrical aids or complex biomolecules and relying fully on the power of molecular recognition and the robustness associated with Avogadro’s number to carry out computations. We have recently demonstrated experimentally that this approach, without using biochemistry, can recognize a language that only automata at the Turing machine level of the hierarchy can recognize (Dueñas-Díez and Pérez-Mercader 2019).

Bibliography

Adamatzky, A., and B. de Lacy Costello. 2002. “Experimental Logical Gates in a Reaction-Diffusion Medium: The XOR Gate and Beyond.” Physical Reviews E 66 (4): 046112.

Adleman, L. M. 1994. “Molecular Computation of Solutions to Combinatorial Problems.” Science 266 (5187): 1021–1024.

Belousov, B. P. 1959. “A Periodic Reaction and Its Mechanism.” Compilation of Abstracts on Radiation Medicine 147 (145): 1.

Benenson, Y. 2009. “Biocomputers: From Test Tubes to Live Cells.” Molecular Biosystems 5:675–685.

Bennett, C. H. 1982. “The Thermodynamics of Computation—A Review.” International Journal of Theoretical Physics 21 (12): 905–940.

Bray, D. 2009. Wetware: A Computer in Every Living Cell. New Haven, CT: Yale University Press.

Bryant, B. 2012. “Chromatin Computation.” PLoS One 7 (5): e35703.

Callen, H. B. 1985. Thermodynamics and an Introduction to Thermostatistics. Hoboken, NJ: John Wiley.

Cohen, D. I. A. 1991. Introduction to Computer Theory. 2nd ed. Hoboken, NJ: John Wiley.

Conrad, M. 1972. “Information Processing in Molecular Systems.” Biosystems 5 (1): 1–14.

Donder, T. de. 1927. Affinité. Paris: Gauthier-Villars.

Dueñas-Díez, M., and J. Pérez-Mercader. 2019. “How Chemistry Computes: Language Recognition by Non-Biochemical Chemical Automata.” ChemRxiv.

Evans, D. 2011. “Introduction to Computing: Explorations in Language, Logic, and Machines.” http://computingbook.org.

Górecki, J., K. Yoshikawa, and Y. Igareshi. 2003. “On Chemical Reactors That Can Count.” Journal of Physical Chemistry A 107 (10): 1664–1669.

Haynes, W. M., ed. 2014. CRC Handbook of Chemistry and Physics. 95th ed. Boca Raton, FL: CRC Press.

Hjelmfelt, A., E. D. Weinberger, and John Ross. 1991. “Chemical Implementation of Neural Networks and Turing Machines.” Proceedings of the National Academy of Sciences of the United States of America 88 (24): 10983–10987.

Hopcroft, J. E., R. Motwani, and J. D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Boston, MA: Addison-Wesley Longman.

Kondepudi, D., and I. Prigogine. 2014. Modern Thermodynamics: From Heat Engines to Dissipative Structures. Hoboken, NJ: John Wiley.

Kuhn, H., and H. D. Försterling. 2000. Principles of Physical Chemistry. Hoboken, NJ: John Wiley.

Landauer, R. 1961. “Irreversibility and Heat Generation in the Computing Process.” IBM Journal of Research and Development 5 (3): 183–191.

Linz, P. 2012. An Introduction to Formal Languages and Automata. 5th ed. Burlington, MA: Jones / Bartlett Learning.

Magnasco, M. O. 1997. “Chemical Kinetics Is Turing Universal.” Physical Review Letters 78 (6): 1190.

Minsky, M. L. 1961. “Recursive Unsolvability of Post's Problem of Tag and Other Topics in Theory of Turing Machines.” Annals of Mathematics 74 (3): 437–455.

Novák, B., and J. J. Tyson. 2008. “Design Principles of Biochemical Oscillators.” Nature Reviews Molecular Cell Biology 9:981–991.

Okamoto, M., T. Sakai, and K. Hayashi. 1987. “Switching Mechanism of a Cyclic Enzyme System: Role as a ‘Chemical Diode’.” Biosystems 21 (1): 1–11.

Pérez-Mercader, J., M. Dueñas-Díez, and Daniel Case. 2017. Chemically-Operated Turing Machine. US Patent 9582771B2.

Petrucci, R. H., F. G. Herring, J. D. Madura, and C. Bissonette. 2011. General Chemistry: Principles and Modern Applications. 10th ed. Pearson Prentice Hall.

Prohaska, S. J., P. F. Stadler, and D. C. Krakauer. 2010. “Innovation in Gene Regulation: The Case of Chromatic Computation.” Journal of Theoretical Biology 265 (1): 27–44.

Rao, R., and M. Esposito. 2016. “Nonequilibrium Thermodynamics of Chemical Reaction Networks: Wisdom from Stochastic Thermodynamics.” Physical Reviews X 6:041064.

Srinivas, N., J. Parkin, G. Seelig, E. Winfree, and D. Soloveichik. 2017. “Enzyme-Free Nucleic Acid Dynamical Systems.” Science 358 (6369): eaal2052.

Tóth, Á., and K. Showalter. 1995. “Logic Gates in Excitable Media.” Journal of Chemical Physics 103 (6): 2058–2066.

Turing, A. M. 1936. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society 2:230–265.

Weisstein, E. W. 2009. CRC Encyclopedia of Mathematics. 3rd ed. Boca Raton, FL: CRC Press.

Zhabotinsky, A. M. 1964. “Periodic Oxidation of Malonic Acid in Solution (Investigation of the Kinetics of the Reaction of Belousov).” Biofizika 9:306–311.

BACK TO The Energetics of Computing in Life & Machines