The Energetics of Computing in Life & Machines pp 191-213
DOI: 10.37911/9781947864078.08
8. Toward Space- and Energy-Efficient Computations
Authors: Anne Condon, University of British Columbia, and Chris Thachuk, California Institute of Technology
Excerpt
Introduction
How might a simulation of computation that is both space and energy efficient be possible? If a Turing machine, on a problem instance of size n, requires t(n)time and s(n)space to complete, then a simulation of the computation is space efficient if it requires at most poly(s(n))space, and energy efficient if it dissipates at most ϵ t(n) energy over the course of the computation, for sufficiently small ϵ 0. Lecerf (1963) and Bennett (1973) made significant progress on this question by introducing the notion of logically reversible computation— previously thought to be a prerequisite for energy-efficient computation1—and devising simulations of irreversible Turing machine computations by logically reversible Turing machines with a constant factor increase in time. Bennett (1989), Lange, McKenzie, and Tapp (2000), and others subsequently made progress on space-efficient simulations.
Recent work by Qian, Soloveichik, and Winfree (2011) and others made further significant progress by bridging the gap between logically reversible and physically realizable computations using DNA strand displacement systems. Their strand displacement simulations of Turing machines use arbitrarily little energy per step while incurring a quadratic slowdown in time. However, to complete, their simulations may require exponentially more molecules (physical space) than the space used by the Turing machine.
Building on these two earlier threads, we showed how computations that are logically reversible, with balanced, symmetric transitions, have energy-efficient implementations as DNA strand displacement systems and only require a quadratic increase in the number of molecules over the theoretical space required of the computation (Thachuk and Condon 2012).
Bibliography
Adleman, L. M. 1994. “Molecular Computation of Solutions to Combinatorial Problems.” Science 266 (5187): 1021–1024.
Bennett, C. H. 1973. “Logical Reversibility of Computation.” IBM Journal of Research and Development 17 (6): 525–532.
————. 1981. “The Thermodynamics of Computation—A Review.” International Journal of Theoretical Physics 21 (12): 905–940.
————. 1989. “Time/Space Trade-Offs for Reversible Computation.” SIAM Journal on Computing 18 (4): 766–776.
Cardelli, L. 2013. “Two-Domain DNA Strand Displacement.” Mathematical Structures in Computer Science 23 (2): 247–271.
Condon, A., A. J. Hu, J. Maňuch, and C. Thachuk. 2012. “Less Haste, Less Waste: On Recycling and Its Limits in Strand Displacement Systems.” Journal of the Royal Society: Interface Focus 2 (4): 512–521.
Cook, M., D. Soloveichik, E. Winfree, and J. Bruck. 2009. “Programmability of Chemical Reaction Networks.” In Algorithmic Bioprocesses, 543–584. New York: Springer.
Esposito, M., and C. Van den Broeck. 2011. “Second Law and Landauer Principle Far from Equilibrium.” Europhysics Letters 95 (4): 40004.
Grochow, J. A., and D. H. Wolpert. 2018. “Beyond Number of Bit Erasures: New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation.” SIGACT News 49, no. 2 (June): 33–56.
Landauer, R. 1961. “Irreversibility and Heat Generation in the Computing Process.” IBM Journal of Research and Development 5 (3): 183–191.
Lange, K. J., P. McKenzie, and A. Tapp. 2000. “Reversible Space Equals Deterministic Space.” Journal of Computer Systems Science 60 (2): 354–367.
Lecerf, Y. 1963. “Logique Mathématique: Machines de Turing réversibles.” Comptes rendus des séances de l'académie des sciences 257:2597–2600.
Lewis, H. R., and C. H. Papadimitriou. 1982. “Symmetric Space-Bounded Computation.” Theoretical Computer Science XX:161–187.
Parrondo, J. M. R., J. M. Horowitz, and T. Sagawa. 2015. “Thermodynamics of Information.” Nature Physics 11 (2): 131–139.
Qian, L., D. Soloveichik, and E. Winfree. 2011. “Efficient Turing-Universal Computation with DNA Polymers [extended abstract].” In Proceedings of the 16th Annual Conference on DNA Computing, 123–140. Berlin, Heidelberg: Springer-Verlag.
Sagawa, T. 2014. “Thermodynamic and Logical Reversibilities Revisited.” Journal of Statistical Mechanics: Theory and Experiment 2014 (3): P03025.
Savage, C. 1997. “A Survey of Combinatorial Gray Codes.” SIAM Review 39 (4): 605–629.
Soloveichik, D., M. Cook, E. Winfree, and J. Bruck. 2008. “Computation with Finite Stochastic Chemical Reaction Networks.” Natural Computing 7 (4): 615–633.
Soloveichik, D., G. Seelig, and E. Winfree. 2010. “DNA as a Universal Substrate for Chemical Kinetics.” Proceedings of the National Academy of Sciences of the United States of America 107 (12): 5393–5398.
Thachuk, C. 2013. “Space and Energy Efficient Molecular Programming and Space Efficient Text Indexing Methods for Sequence Alignment.” PhD diss., University of British Columbia.
Thachuk, C., and A. Condon. 2012. “Space and Energy Efficient Computation with DNA Strand Displacement Systems.” Lecture Notes in Computer Science 7433:135–149.