39.Actually it would report even more. The final version of the Köchel catalog—there are six—does end with #626, the Requiem in D Minor, but also includes numerous entries with variations, such as the Church Sonata in C (#317a) and the Aria for Soprano in B-flat (#317b).
40.Some functions, such as the NOT and NOR functions, can be implemented with single transistors. The upper output bit shown in figure 22 corresponds to the lower significance binary digit. It is computed by the so-called exclusive or function (XOR). The lower-output bit is the higher-significance “carry” bit that is the result of an AND function.
41.Integrated circuits also contain some more complex, derived logical building blocks, such as multiplexers, demultiplexers, and registers, but all of these are based on Boolean logic functions. See also Balch (2003).
42.Such devices also come under other names, such as reconfigurable hardware or programmable logic devices. For an overview see Balch (2003). There are several classes of such devices. The research I discuss here was carried out with a specific class in mind: field-programmable gate arrays (FPGAs). Like many other integrated circuits, such arrays contain many more than just AND and OR gates. They also use more complicated units of computation, such as logic blocks, each of which may contain a full adder, several lookup tables that store truth tables in random access memory, multiplexers, and others. But the principle is still the same: They perform complex computations by networking simpler computational units.
The programming of such devices is different from more conventional software programming. A search program like the one I described earlier to search a music database is typically executed on a hardwired chip, whereas on a programmable chip a program can change the wiring of the chip itself. It amounts to creating a piece of hardware that can execute a given computation task faster than software running on a generic hardwired chip. Limitations of FPGAs include that they are slower and more expensive than application-specific integrated circuits. See also Balch (2003), 250.
43.The field of machine learning is a well-established research field whose current focus is not programmable hardware, but methods (often implemented in software) that enable computers to extract statistical information from complex data.
44.Once again, I am using the word “wires” not in a literal sense—flexible metal threads—but metaphorically. They are integral parts of an integrated circuit.
45.A difference from proteins is that amino acids form a linear string, whereas the gates in a circuit have a two-dimensional arrangement.
46.The number of functions a circuit can compute depends not only on its number of gates but also on the number of input and output bits.
47.It also allowed us to study idealized situations, such as exploring every possible wiring change in a circuit, whereas some such changes may be prohibited in a commercial FPGA architecture. We considered circuits that could harbor OR, AND, XOR, NAND, and NOR gates, because these are the five most commonly used two-input logic gates. Each input could be wired to any of the input gates in the first column of the sixteen-gate array. Each output could be wired to any of the circuit’s output bits. Gates were wired internally in a feed-forward fashion where the input of a gate could only come from a gate to the left of it in the array. Such feed-forward connectivity is important to avoid complex dynamics, such as cyclic behavior. More details on this work, including some of the numbers I discuss, can be found in Raman and Wagner (2011).
48.The circuits we studied had four input and four output bits, and there are 1.84 × 1019 possible Boolean functions with this property.
49.When I say that no two gates were identical, I mean that gates at the same position in the two circuits computed different Boolean logic functions. The maximal distance we could achieve in such a random walk depended only little on the frequency of a logic function, that is, on the number of circuits computing this logic function. There may be Boolean logic functions encoded by very few circuits that are highly similar, but those would be very hard to find in a vast circuit space. Previous work has recognized that neutral change can be important for the performance of evolutionary algorithms. See, for example, Banzhaf and Leier (2006), as well as Brameier and Banzhaf (2003), Miller and Thomson (2000), and Yu and Miller (2006). However, to my knowledge, nobody had demonstrated systematically, and in a system that can be implemented in hardware, that genotype networks and the diversity of their neighborhoods are generic features of a configuration space (not restricted to one or a few Boolean logic functions).
50.This means that these functions are not likely to be found in the neighborhood of a specific circuit different from the focal circuit in whose neighborhood they occur. (But they may occur in the neighborhood of other circuits in genotype space.)
51.A thousand wiring changes may seem like a lot, but keep in mind that programmable hardware can rewire at lightning speeds. Some useful information on the reconfiguration time of a commercial FPGA is given in Schuck, Haetzer, and Becker (2009).
52.This holds, as usual, for phenotypes (functions) sufficiently frequent that circuits encoding them can be found through a blind search. This property of the circuit library is important, because it can minimize the amount of array reconfiguration (and thus time) needed to change from one function to another.
53.A minor difference from my previous notions of phenotype and function is that any one circuit, any one wiring pattern, may be able to display more than one (computational) behavior, depending on the input to the Boolean logic function that it encodes. One can view a circuit that explores the circuit library to preserve an old, optimal computation while improving a newer, still suboptimal computation as walking along the circuit network in which both computations are unchanged, while exploring the neighborhood of this network for circuits that improve the new computation.
EPILOGUE: PLATO’S CAVE
1.See Darwin (1969), 58.
2.See proposition 168 in Wittgenstein (1983), 99.
3.See Wigner (1960).
4.See Tegmark (2008). A skeptic might argue that the correspondence between mathematics and reality is just an artifact of human history—that there is a huge space of all possible mathematics and we have “sliced” only those theorems from this space that actually describe the physical world. But that assertion raises the question of what the nature of this space is and why useful math exists at all in it.
BIBLIOGRAPHY
Abbott, E. A. Flatland: A Romance of Many Dimensions. New York: Perseus, 2002.
Akam, M. “Drosophila Development: Making Stripes Inelegantly.” Nature 341 (1989): 282–83.
Alberch, P. “From Genes to Phenotype: Dynamical Systems and Evolvability.” Genetica 84 (1991): 5–11.
Albert, R., and H. G. Othmer. “The Topology of the Regulatory Interactions Predicts the Expression Pattern of the Segment Polarity Genes in Drosophila melanogaster.” Journal of Theoretical Biology 223 (2003): 1–18.
Alfred, R. “Oct. 21, 1879: Edison Gets the Bright Light Right.” Wired, October 21, 2009.
Amores, A., et al. “Zebrafish Hox Clusters and Vertebrate Genome Evolution.” Science 282 (1998): 1711–14.
Arkin, R. C. Behavior-Based Robotics. Cambridge, MA: MIT Press, 1998.
Arthur, W. B. The Nature of Technology: What It Is and How It Evolves. New York: Free Press, 2009.
Ashery-Padan, R., et al. “Pax6 Activity in the Lens Primordium Is Required for Lens Formation and for Correct Placement of a Single Retina in the Eye.” Genes and Development 14 (2000): 2701–11.
Avery, O. T., C. M. MacLeod, and M. McCarty. “Studies on the Chemical Nature of the Substance Inducing Transformation of Pneumococcal Types: Induction of Transformation by a Desoxyribonucleic Acid Fraction Isolated from Pneumococcus Type III.” Journal of Experimental Medicine 79 (1944): 137–58.
Babu, M. M., et al. “Structure and Evolution of Transcriptional Regulatory Networks.” Current Opinion in Structural Biology 14 (2004): 283–91.
; Bada, J. L., and A. Lazcano. “Origin of Life—Some Like It Hot, but Not the First Biomolecules.” Science 296 (2002): 1982–83.
Balch, M. Complete Digital Design. New York: McGraw-Hill, 2003.
Banzhaf, W., and A. Leier, A. “Evolution on Neutral Networks in Genetic Programming.” In Genetic Programming Theory and Practice III, edited by T. Yu, R. Riolo, and B. Worzel, 207–21. New York: Springer, 2006.
Beatty, J. T., et al. “An Obligately Photosynthetic Bacterial Anaerobe from a Deep-Sea Hydrothermal Vent.” Proceedings of the National Academy of Sciences of the United States of America 102 (2005): 9306–10.
Beerling, D. J., C. P. Osborne, and W. G. Chaloner. “Evolution of Leaf-Form in Land Plants Linked to Atmospheric CO2 Decline in the Late Palaeozoic Era.” Nature 410 (2001): 352–54.
Benfey, P., and A. Protopapas. Genomics. Upper Saddle River, NJ: Prentice Hall, 2005.
Bennick, A. “Interaction of Plant Polyphenols with Salivary Proteins.” Critical Reviews in Oral Biology and Medicine 13 (2002): 184–96.
Bergthorsson, U., et al. “Widespread Horizontal Transfer of Mitochondrial Genes in Flowering Plants.” Nature 424 (2003): 197–201.
Bersaglieri, T., et al. “Genetic Signatures of Strong Recent Positive Selection at the Lactase Gene.” American Journal of Human Genetics 74 (2004): 1111–20.
Bertalanffy, L. v. General System Theory: Foundations, Development, Applications. New York: George Braziller, 1968.
Bharathan, G., et al. “Homologies in Leaf Form Inferred from KNOXI Gene Expression during Development.” Science 296 (2002): 1858–60.
Blattner, F. R., et al. “The Complete Genome Sequence of Escherichia coli K-12.” Science 277 (1997): 1453–62.
Borges, J. L. Fictions. London: Calder, 1962.
Braakman, R., and E. Smith. “The Compositional and Evolutionary Logic of Metabolism.” Physical Biology 10 (2013): 1–61.
Brakefield, P. M., et al. “Development, Plasticity and Evolution of Butterfly Eyespot Patterns.” Nature 384 (1996): 236–42.
Brameier, M., and W. Banzhaf. “Neutral Variations Cause Bloat in Linear GP.” In 6th European Conference on Genetic Programming (EuroGP 2003), edited by C. Ryan et al., 286–96. Colchester, England, 2003.
Branden, C., and J. Tooze. Introduction to Protein Structure. New York: Garland, 1999.
Brasier, M., et al. “A Fresh Look at the Fossil Evidence for Early Archaean Cellular Life.” Philosophical Transactions of the Royal Society B: Biological Sciences 361 (2006): 887–902.
Bryson, B. A Short History of Nearly Everything. London: Random House, 2003.
Budin, I., R. J. Bruckner, and J. W. Szostak. “Formation of Protocell-Like Vesicles in a Thermal Diffusion Column.” Journal of the American Chemical Society 131 (2009): 9628–29.
Budin, I., and J. W. Szostak. “Expanding Roles for Diverse Physical Phenomena during the Origin of Life.” Annual Review of Biophysics 39 (2010): 245–63.
Burchfield, J. Lord Kelvin and the Age of the Earth. Chicago: University of Chicago Press, 1990.
———. “Darwin and the Problem of Geological Time. Isis 65 (1974): 300–21.
Burr, A. B., and G. E. Andrew. The Unreasonable Effectiveness of Number Theory. Washington, DC: American Mathematical Society, 1992.
Bushman, F. Lateral DNA Transfer: Mechanisms and Consequences. Cold Spring Harbor, NY: Cold Spring Harbor Laboratory Press, 2002.
Cairns, J., J. Overbaugh, and S. Miller. “The Origin of Mutants.” Nature 335 (1988): 142–45.
Carroll, S. B., J. K. Grenier, and S. D. Weatherbee. From DNA to Diversity: Molecular Genetics and the Evolution of Animal Design. Malden, MA: Blackwell, 2001.
Caspi, R., et al. “The MetaCyc Database of Metabolic Pathways and Enzymes and the BioCyc Collection of Pathway/Genome Databases.” Nucleic Acids Research 40 (2012): D742–D753.
Cech, T. R. “Structural Biology—The Ribosome Is a Ribozyme.” Science 289 (2000): 878–79.
Chang, A., et al. “BRENDA, AMENDA and FRENDA the Enzyme Information System: New Content and Tools in 2009.” Nucleic Acids Research 37 (2009): D588–D592.
Cheng, C. C.-H. “Evolution of the Diverse Antifreeze Proteins.” Current Opinion in Genetics and Development 8 (1998): 715–20.
Cheng, L. K. L., and P. J. Unrau. “Closing the Circle: Replicating RNA with RNA.” Cold Spring Harbor Perspectives in Biology 2 (2010).
Ciliberti, S., O. C. Martin, and A. Wagner. “Circuit Topology and the Evolution of Robustness in Complex Regulatory Gene Networks.” PLoS Computational Biology 3, no. 2 (2007a): e15.
———. “Innovation and Robustness in Complex Regulatory Gene Networks.” Proceedings of the National Academy of Sciences of the United States of America 104 (2007b): 13591–96.
Cody, G. D., et al. “Primordial Carbonylated Iron-Sulfur Compounds and the Synthesis of Pyruvate.” Science 289 (2000): 1337–40.
Cohn, M. J., and C. Tickle. “Developmental Basis of Limblessness and Axial Patterning in Snakes.” Nature 399 (1999): 474–79.
Cole, S., and T. J. Phelan. “The Scientific Productivity of Nations.” Minerva 37 (1999): 1–23.
Cook, L. M., et al. “Selective Bird Predation on the Peppered Moth: The Last Experiment of Michael Majerus.” Biology Letters 8 (2012): 609–12.
Copley, S. D. “Evolution of a Metabolic Pathway for Degradation of a Toxic Xenobiotic: The Patchwork Approach.” Trends in Biochemical Sciences 25 (2000): 261–65.
Copley, S. D., et al. “The Whole Genome Sequence of Sphingobium chlorophenolicum L-1: Insights into the Evolution of the Pentachlorophenol Degradation Pathway.” Genome Biology and Evolution 4 (2012): 184–98.
Copley, S. D., E. Smith, and H. J. Morowitz. “The Origin of the RNA World: Co-evolution of Genes and Metabolism.” Bioorganic Chemistry 35 (2007): 430–43.
Corcos, A., and F. Monaghan. “Role of de Vries in the Recovery of Mendel’s Work. 1. Was de Vries Really an Independent Discoverer of Mendel?” Journal of Heredity 76 (1985): 187–90.
Corliss, J. B., et al. “Submarine Thermal Springs on the Galápagos Rift.” Science 203 (1979): 1073–83.
Cotterell, J., and J. Sharpe. “An Atlas of Gene Regulatory Networks Reveals Multiple Three-Gene Mechanisms for Interpreting Morphogen Gradients.” Molecular Systems Biology 6 (2010): 425.
Cropper, W. H. Great Physicists. New York: Oxford University Press, 2001.
Dantas, G., et al. “Bacteria Subsisting on Antibiotics.” Science 320 (2008): 100–103.
Darwin, C. On the Origin of Species by Means of Natural Selection, or the Preservation of Favored Races in the Struggle for Life. 1st ed. London: John Murray, 1859.
———. The Origin of Species by Means of Natural Selection, or the Preservation of Favored Races in the Struggle for Life. 6th ed. London: John Murray, 1872. Reprint, New York: A. L. Burt.
———. The Autobiography of Charles Darwin, 1809–1882. New York: Norton, 1969.
Davidson, A. R., and R. T. Sauer. “Folded Proteins Occur Frequently in Libraries of Random Amino Acid Sequences.” Proceedings of the National Academy of Sciences of the United States of America 91 (1994): 2146–50.
Davis, M. C., R. D. Dahn, and N. H. Shubin. “An Autopodial-Like Pattern of Hox Expression in the Fins of a Basal Actinopterygian Fish.” Nature 447 (2007): 473–76.
Dawkins, R. Climbing Mount Improbable. New York: Norton, 1997.
———. Unweaving the Rainbow: Science, Delusion, and the Appetite for Wonder. Boston: Houghton Miffin, 1998.
de Vries, H. Species and Varieties, Their Origin by Mutation. Chicago: Open Court Publishing Company, 1905.
Deamer, D. W. “Membrane Compartments in Prebiotic Evolution.” In The Molecular Origins of Life, edited by E. Brock, 189–205. Cambridge: Cambridge University Press, 1998.
Dekel, E., and U. Alon. “Optimality and Evolutionary Tuning of the Expression Level of a Protein.” Nature 436 (2005): 588–92.
Delsemme, A. H. “Cosmic Origin of the Biosphere.” In The Molecular Origins of Life, edited b
y E. Brock, 100–118. Cambridge: Cambridge University Press, 1998.
Desmond, A., and J. Moore. Darwin: The Life of a Tormented Evolutionist. New York: Norton, 1994.
Dong, J., and J. Vagners. “Parallel Evolutionary Algorithms for UAV Planning.” In AIAA First Intelligent Systems Technical Conference. Chicago, 2004.
Dong, P. D. S., J. S. Dicks, and G. Panganiban. “Distal-less and Homothorax Regulate Multiple Targets to Pattern the Drosophila Antenna.” Development 129 (2002): 1967–74.
Drake, J. W., et al. “Rates of Spontaneous Mutation.” Genetics 148 (1998): 1667–86.
Arrival of the Fittest: Solving Evolution's Greatest Puzzle Page 28