We survey a few aspects of the thermodynamics of computation, connecting information, thermodynamics, computability and physics. We suggest some lines of research into how information theory and computational thermodynamics can help us arrive at a better understanding of biological processes. We argue that while a similar connection between information theory and evolutionary biology seems to be growing stronger and stronger, biologists tend to use information simply as a metaphor. While biologists have for the most part been influenced and inspired by information theory as developed by Claude Shannon, we think the introduction of algorithmic complexity into biology will turn out to be a much deeper and more fruitful cross-pollination.
References
[1]
Cooper, S.B. “The Mathematician’s Bias”, and the Return to Embodied Computation. In A Computable Universe: Understanding Computation & Exploring Nature as Computation; Zenil, H., Ed.; World Scientific Publishing Company: Singapore, 2012.
[2]
Szilárd, L. über die Entropieverminderung in einem thermodynamischen System bei Eingriffenin telligenter Wesen (On the reduction of entropy in a thermodynamic system by the interference of intelligent beings). Z. Physik 1929, 53, 840–856, doi:10.1007/BF01341281.
[3]
Landauer, R. Irreversibility and heat generation in the computing process. IBM J. Res. Dev 1961, 5, 183–191, doi:10.1147/rd.53.0183.
[4]
Bennett, C.H. The thermodynamics of computation—A review. Int. J. Theor. Phys. 1982, 21, 905–940, doi:10.1007/BF02084158.
[5]
Bennett, C.H. Demons, Engines and the Second Law. Sci. Am. 1987, 257, 108–116, doi:10.1038/scientificamerican1187-108.
[6]
Fredkin, E.; Toffoli, T. Conservative logic. Int. J. Theor. Phys. 1982, 21, 219–253, doi:10.1007/BF01857727.
[7]
Maxwell, J.C. Theory of Heat, 9th; Pesic, P., Ed.; Dover: Mineola, NY, USA, 2001.
[8]
Feynman, R.P. Feynman Lectures on Computation; Hey, J.G., Allen, W., Eds.; Addison-Wesley: Boston, MA, USA, 1996; p. 147.
[9]
Sethna, J. Statistical Mechanics: Entropy, Order Parameters and Complexity; Oxford University Press: Oxford, UK, 2006.
[10]
Toffoli, T. Reversible Computing; Technical memo MIT/LCS/TM-151; MIT Lab for Computer Science: Cambridge, MA, USA, 1980.
[11]
Bennett, C.H. Logical reversibility of computation. IBM J. Res. Dev. 1973, 17, 525, doi:10.1147/rd.176.0525.
[12]
Cerny, V. Energy, Entropy, Information, and Intelligence. Available online: http://arxiv.org/pdf/1210.7065.pdf (accessed on 19 November 2012).
[13]
Kolmogorov, A.N. Three approaches to the quantitative definition of information. Probl. Inform. Transm. 1965, 1, 1–7.
[14]
Chaitin, G.J. A Theory of Program Size Formally Identical to Information Theory. J. Assoc. Comput. Mach. 1975, 22, 329–340, doi:10.1145/321892.321894.
[15]
Solomonoff, R.J. A formal theory of inductive inference: Parts 1 and 2. Inform. Control 1964, 7, 1–22, 224–254.
[16]
Levin, L. Laws of information conservation (non-growth) and aspects of the foundation of probability theory. Probl. Inform. Transm. 1974, 10, 206–210.
[17]
Preskill, J. Do Black Holes Destroy Information? Available online: http://arxiv.org/abs/hep-th/9209058 (accessed on 19 November 2012).
[18]
Giddings, S.B. Comments on information loss and remnants. Phys. Rev. D. 1994, 49, 4078–4088, doi:10.1103/PhysRevD.49.4078.
[19]
Read in a presentation at the Philosophical Society of Zurich on April 24, 1865.
[20]
Bekenstein, J.D. Information in the Holographic Universe. Sci. Am. 2003, 289, 61.
[21]
Susskind, L. The World as a Hologram. J. Math. Phys. 1995, 36, 6377–6396, doi:10.1063/1.531249.
[22]
Bousso, R. The holographic principle. Rev. Mod. Phys. 2002, 74, 825–874, doi:10.1103/RevModPhys.74.825.
[23]
t Hooft, G. Dimensional Reduction in Quantum Gravity. Available online: http://arxiv.org/abs/gr-qc/9310026 (accessed on 19 November 2012).
[24]
Wheeler, J.A. Information, physics, quantum: The search for links. In Complexity, Entropy, and the Physics of Information; Zurek, E., Ed.; Addison-Wesley: Boston, MA, USA, 1990.
[25]
Misner, C.W.; Thorne, K.S.; Zurek, W.H. John Wheeler, relativity, and quantum information. Phys. Today 2009, 62, 40.
[26]
Deutsch, D. Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer. Proc. R. Soc. Lond. 1985, A400, 97–117.
[27]
Wolfram, S. A New Kind of Science; Wolfram Media: Champaign, IL, USA, 2002.
[28]
Dennett, D.C. Darwin’s Dangerous Idea: Evolution and the Meanings of Life; Simon & Schuster: New York, NY, USA, 1996.
[29]
Zenil, H.; Delahaye, J.P. On the Algorithmic Nature of the World. In Information and Computation; Dodig-Crnkovic, G., Burgin, M., Eds.; World Scientific: Singapore, 2010.
[30]
Grafen, A. The simplest formal argument for fitness optimization. J. Genet. 2008, 87, 1243–1254.
[31]
Grafen, A. The formal Darwinism project: A mid-term report. J. Evolution. Biol. 2007, 20, 1243–1254.
[32]
Hunt, P. The Function of Hox Genes. In Developmental Biology; Bittar, E.E., Ed.; Elsevier: Amsterdam, The Netherlands, 1998.
[33]
Shetty, R.P; Endy, D.; Knight, T.F., Jr. Engineering BioBrick vectors from BioBrick parts. J. Biol. Eng. 2008, 2, doi:10.1186/1754-1611-2-5.
[34]
Adleman, L.M. Toward a Mathematical Theory of Self-Assembly; USC Technical Report: Los Angeles, CA, USA, 2000.
[35]
Rothemund, P.W.K.; Papadakis, N.; Winfree, E. Algorithmic Self-Assembly of DNA Sierpinski Triangles. PLoS Biol. 2004, 2, doi:10.1371/journal.pbio.0020424.
[36]
Adleman, L.M.; Cheng, Q.; Goel, A.; Huang, M.-D.A. Running time and program size for self-assembled squares. In ACM Symposium on Theory of Computing, Crete, Greece; 2001; pp. 740–748.
[37]
Rothemund, P.W.K.;Winfree, E. The program-size complexity of self-assembled squares (extended abstract). In ACM Symposium on Theory of Computing, Portland, OR, USA; 2000; pp. 459–468.
[38]
Aggarwal, G.; Goldwasser, M.; Kao, M.; Schweller, R.T. Complexities for generalized models of self-assembly. In Symposium on Discrete Algorithms, New Orleans, LA, USA; 2004.
[39]
Winfree, E. Algorithmic Self-Assembly of DNA Thesis. Ph.D Thesis, 1998.
[40]
von Neumann, J. The Theory of Self-reproducing Automata; Burks, A., Ed.; University of Illinois Press: Urbana, IL, USA, 1966.
[41]
Gardner, M. Mathematical Games—The fantastic combinations of John Conway’s new solitaire game “life”. Sci. Am. 1970, 223, 120–123, doi:10.1038/scientificamerican1070-120.
[42]
Langton, C.G. Studying artificial life with cellular automata. Physica D 1986, 22, 120–149, doi:10.1016/0167-2789(86)90237-X.
[43]
Winfree, E. Simulations of Computing by Self-Assembly; Technical Report CS-TR:1998.22; Caltech: Pasadena, CA, USA, 1998.
[44]
Barricelli, N.A. Numerical testing of evolution theories Part I Theoretical introduction and basic tests. Acta Biotheor. 1961, 16, 69–98, doi:10.1007/BF01556771.
[45]
Reed, J.; Toombs, R.; Barricelli, N.A. Simulation of biological evolution and machine learning. I. Selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing. J. Theor. Biol. 1967, 17, 319–342.
[46]
Dyson, G. Darwin Among the Machines; Penguin Books Ltd.: London, UK, 1999.
[47]
Cook, M. Universality in Elementary Cellular Automata. Complex Syst. 2004, 15, 1–40.
[48]
Neary, T.; Woods, D. Small weakly universal Turing machines. In 17th International Symposium on Fundamentals of Computation Theory (FCT 2009); Springer: Warsaw, Poland, 2009; Volume 5699 of LNCS, pp. 262–273.
[49]
Holland, J.H. Adaptation in Natural and Artificial Systems; University of Michigan Press: Ann Arbor, MI, USA, 1975.
[50]
Koza, J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection; MIT Press: Cambridge, MA, USA, 1992.
[51]
Martínez, G.J.; Adamatzky, A.; Stephens, C.R. Cellular automaton supercolliders. Int. J. Mod. Phys. C 2011, 22, 419–439, doi:10.1142/S0129183111016348.
[52]
Livnat, A.; Pippenger, N. An optimal brain can be composed of conflicting agents. PNAS 2006, 103, 9.
[53]
Chaitin, G.J. Metaphysics, Metamathematics and Metabiology. In Randomness Through Computation; Zenil, H., Ed.; World Scientific: Singapore, 2011; pp. 93–103.
[54]
McNamara, J.M.; Dall, S.R.X. Information is a fitness enhancing resource. Oikos 2010, 119, 231–236, doi:10.1111/j.1600-0706.2009.17509.x.
[55]
Zenil, H.; Marshall, J.A.R. Some Computational Aspects of Essential Properties of Evolution and Life. ACM Ubiquity 2012, 12, 11.
[56]
Zenil, H.; Gershenson, C.; Marshall, J.A.R.; Rosenblueth, D. Life as Thermodynamic Evidence of Algorithmic Structure in Natural Environments. Entropy 2012, 14, 2173–2191, doi:10.3390/e14112173.
[57]
Zenil, H.; Hernandez-Quiroz, F. On the Possible Computational Power of the Human Mind. In Worldviews, Science and Us: Philosophy and Complexity; Gershenson, C., Aerts, D., Edmonds, B., Eds.; World Scientfic: Singapore, 2007.
[58]
Paz Flanagan, T.; Letendre, K.; Burnside, W.; Fricke, G.M.; Moses, M. How ants turn information into food. IEEE Artificial Life (ALIFE) 2011. Paris, France.
[59]
Catalania, K.C. Born knowing: Tentacled snakes innately predict future prey behaviour. PLoS ONE 2010, 5, 6.
[60]
de Vladar, H.P.; Barton, N.H. The contribution of statistical physics to evolutionary biology. Trends Ecol. Evol. 2011, 26, 424–432, doi:10.1016/j.tree.2011.04.002.
[61]
Shannon, C. A Mathematical Theory of Communication. Bell Syst. Tech. J. 1948, 27, 279–423, 623–656.
