Complex Worlds, Simple Rules

Note 1. John Conway’s Game of Life was first published in Martin Gardner’s “Mathematical Games” column in Scientific American (October 1970). Conway died in 2020; the Game of Life remains his most famous creation.

Note 1a. Paul Rendell completed his Game of Life Turing machine on 2 April 2000 and published the construction as “Turing Universality of the Game of Life,” in Collision-Based Computing, ed. Andrew Adamatzky (Springer, 2002): 513-539; the full development, including the universal machine he finished in 2010-2011, appears in Rendell, Turing Machine Universality of the Game of Life (Springer, 2016). The universality of the Game of Life was argued much earlier, by sketch rather than by working pattern, in Elwyn Berlekamp, John Conway, and Richard Guy, Winning Ways for Your Mathematical Plays, vol. 2 (Academic Press, 1982), chapter 25. Rendell’s machine runs as a pattern in a Life simulator: the grid is the hardware.

Note 2. Stephen Wolfram, A New Kind of Science (2002). Wolfram’s systematic study of cellular automata began in the 1980s and culminated in this comprehensive (and controversial) work.

Note 3. Matthew Cook, “Universality in Elementary Cellular Automata,” Complex Systems 15 (2004): 1-40. Cook’s proof that Rule 110 is Turing complete took years to reach print because of a legal dispute with Wolfram Research over its publication; the dispute concerned rights, not the mathematics.

Note 4. Chris Langton, “Computation at the Edge of Chaos: Phase Transitions and Emergent Computation,” Physica D 42 (1990): 12-37. Langton’s work connected cellular automata to theories of life and computation.

Note 5. Per Bak, Chao Tang, and Kurt Wiesenfeld, “Self-organized criticality,” Physical Review A 38 (1988): 364-374. See also Per Bak, How Nature Works: The Science of Self-Organized Criticality (1996) for an accessible introduction.

Note 6. Voss, R.F. and Clarke, J., “1/f noise in music and speech,” Nature 258 (1975): 317-318. The study reported approximately 1/f spectra in selected music and speech signals. A 1/f-like spectrum can arise through several mechanisms and does not by itself establish criticality.

Note 7. Newman, M.E.J., “Power laws, Pareto distributions and Zipf’s law,” Contemporary Physics 46 (2005): 323-351. A comprehensive review of power-law distributions across natural and social phenomena, including earthquakes, extinctions, financial markets, and war sizes.

Note 8. Nassim Nicholas Taleb, The Black Swan: The Impact of the Highly Improbable (2007). Taleb’s Mediocristan/Extremistan distinction separates domains where no single observation moves the total much from domains where one observation can swamp it. The Turkey Problem illustrates how observational data becomes systematically misleading in Extremistan — where the rare catastrophic event dominates outcomes.

Note 9. Browne, C.A. and Datta, S.S., “Elastic turbulence generates anomalous flow resistance in porous media,” Science Advances 7 (2021): eabj2619. Fluorescent microparticle tracking revealed that polymer-containing fluids develop chaotic flow (eddies forming, growing, and vanishing in individual pores) at a sharp threshold, with the influence of inertia at least a million times below the onset of inertial turbulence. The mechanism is elastic: polymer chains stretch and recoil, feeding energy back into the flow. The 2015 precursor experiment at Schlumberger Gould Research Center (Cambridge, UK) first identified the effect in a 2D analog. See also Mann, A., “An Injection of Chaos Solves Decades-Old Fluid Mystery,” Quanta Magazine (January 4, 2022).

Note 10. Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics 21 (1987): 25-34. Reynolds’ Boids algorithm is now standard in computer graphics for simulating natural group movement.

Note 11. Theraulaz, G., Gautrais, J., Camazine, S., and Deneubourg, J.-L., “The formation of spatial patterns in social insects: from simple behaviors to complex structures,” Philosophical Transactions of the Royal Society A 361 (2003): 1263–1282. The three-rule model of ant nest construction (constant pickup rate, preferential deposition near existing grains, preference for pheromone-marked grains) reproduces the multilayered architecture of real nests. See also Khuong, A. et al., “Stigmergic construction and topochemical information shape ant nest architecture,” PNAS 113(5) (2016): 1303–1308, for high-resolution tracking of individual building decisions.

Note 12. Reid, C.R., Lutz, M.J., Powell, S., Kao, A.B., Couzin, I.D., and Garnier, S., “Army ants dynamically adjust living bridges in response to a cost-benefit trade-off,” PNAS 112(49) (2015): 15113–15118. Army ant bridges form when ants sense a gap in the trail and dismantle when traffic stops. They also stop short of the shortest possible shortcut: each ant locked into a bridge is an ant not foraging, and through purely local decisions the bridge settles where that cost balances the distance saved. For fire ant rafts: Mlot, N.J., Tovey, C.A., and Hu, D.L., “Fire ants self-assemble into waterproof rafts to survive floods,” PNAS 108(19) (2011): 7669–7673.

Note 13. Flack, J.C., “Life’s Information Hierarchy,” in From Matter to Life: Information and Causality, ed. Walker, S.I., Davies, P.C.W., and Ellis, G.F.R. (Cambridge University Press, 2017). Flack’s “collective computation” framework treats adaptive systems as noisy information processors that solve problems in two phases: distributed information gathering followed by consensus consolidation. The neural data discussed here were collected by William Newsome’s group at Stanford and analyzed by Daniels, Flack, and Krakauer. See Daniels, B.C., Flack, J.C., and Krakauer, D.C., “Dual Coding Theory Explains Biphasic Collective Computation in Neural Decision-Making,” Frontiers in Neuroscience 11 (2017): 313, DOI: 10.3389/fnins.2017.00313. See also Sokol, J., “How Nature Solves Problems Through Computation,” Quanta Magazine (July 6, 2017).

Note 14. Flack, J.C., Girvan, M., de Waal, F.B.M., and Krakauer, D.C., “Policing stabilizes construction of social niches in primates,” Nature 439 (2006): 426–429. Removal of policing individuals from a group of pigtailed macaques at the Yerkes National Primate Research Center caused the social network to fragment and aggression to increase. A handful of individuals had been holding the group’s order together.

Note 15. Daniels, B.C., Krakauer, D.C., and Flack, J.C., “Control of finite critical behavior in a small-scale social system,” Nature Communications 8 (2017): 14301. The study measured the distance to criticality in a macaque society and found that shifting the fight-joining propensity of three to five key individuals was sufficient to push the system past its critical point into large-scale conflict.

Note 16. Turing, A.M., “The chemical basis of morphogenesis,” Philosophical Transactions of the Royal Society of London B 237 (1952): 37-72. Turing’s reaction-diffusion model proposed that two interacting morphogens (an activator and a faster-diffusing inhibitor) could spontaneously generate spatial patterns. The paper preceded publication of DNA’s double-helical structure by a year. For experimental confirmation in mammalian hair, see Sick, S. et al., “WNT and DKK determine hair follicle spacing through a reaction-diffusion mechanism,” Science 314 (2006): 1447-1450.

Note 17. Cooper, R.L. et al., “An ancient Turing-like patterning mechanism regulates skin denticle development in sharks,” Science Advances 4 (2018): eaau5484. The study demonstrated that shark denticle patterning is governed by a reaction-diffusion mechanism using the same gene families (FGF, Shh, and Bmp) as avian feather patterning, with functional conservation confirmed by chemical inhibition experiments. See also Lambert, J., “Ancient Turing Pattern Builds Feathers, Hair — and Now, Shark Skin,” Quanta Magazine (January 2, 2019).

Note 18. Economou, A.D. et al., “Periodic stripe formation by a Turing mechanism operating at growth zones in the mammalian palate,” Nature Genetics 44 (2012): 348–351. First identification of the specific activator-inhibitor molecules (FGF signaling as local activation, Shh signaling as inhibition) in a Turing mechanism during mammalian development. Follow-up on digit patterning and Hox scaling: Sheth, R. et al., “Hox genes regulate digit patterning by controlling the wavelength of a Turing-type mechanism,” Science 338 (2012): 1476–1480. See also Ouellette, J., “Biologists Home In on Turing Patterns,” Quanta Magazine (25 March 2013).

Note 19. Self-generated chemotactic gradients: Insall, R., “The interaction between pseudopods and extracellular signaling during chemotaxis and directed migration,” Current Opinion in Cell Biology 73 (2021): 136–142. Maze-solving experiments: Tweedy, L., Thomason, P.A., Paschke, P.I., et al., “Seeing around corners: cells solve mazes and respond at a distance using attractant breakdown,” Science 369 (2020): 706–710. Self-generated stiffness gradients in vivo: Shellard, A.G. and Mayor, R., “Collective durotaxis along a self-generated stiffness gradient in vivo,” Nature 600 (2021): 690–694. Self-correction of irregular fronts: Bhattacharjee, T. and Datta, S.S., “Bacterial hopping and trapping in porous media,” Nature Communications 10 (2019): 2075; Datta, S.S., et al., “Self-generated chemotactic gradients smooth out bacterial spreading fronts,” preprint (2022).

Note 20. Jiao, Y., Lau, T., Hatzikirou, H., Meyer-Hermann, M., Corbo, J.C., and Torquato, S., “Avian photoreceptor patterns represent a disordered hyperuniform solution to a multiscale packing problem,” Physical Review E 89 (2014): 022721. The chicken retina contains four single-cone types and one double-cone type with different sizes and abundances. For an accessible overview, see Wolchover, N., “A Bird’s-Eye View of Nature’s Hidden Order,” Quanta Magazine (2016).

Note 21. Jiao et al. (2014); see note 20. The study shows that bird retinal photoreceptor distributions are hyperuniform: large-scale density fluctuations are suppressed while small-scale disorder remains, an optimal solution to the problem of packing multiple cone types for visual acuity.

Note 22. Salvatore Torquato et al., “Hyperuniformity and its generalizations,” Physical Review E 94 (2016): 022122. Torquato’s work has identified hyperuniformity across biological and physical systems. In a striking extension, Torquato, Ge Zhang, and Matthew de Courcy-Ireland showed that the prime numbers, when treated as a one-dimensional system of particles and subjected to computational X-ray diffraction, produce a fractal-like pattern of Bragg peaks — a new category of order they call “effective limit-periodicity,” distinct from both crystals and quasicrystals. Even the primes, the most apparently random of mathematical objects, reveal hidden structure when examined with the right lens. See Torquato et al., “Uncovering multiscale order in the prime numbers via scattering,” Journal of Statistical Mechanics: Theory and Experiment 2018(9): 093401.

Note 23. Fernando, C. and Sojakka, S., “Pattern Recognition in a Bucket,” in Advances in Artificial Life (2003). Springer. Demonstrates that a bucket of water can implement basic pattern recognition through wave interference, the water serving as a dynamic reservoir while a separately trained readout performs the classification.

Note 24. Khoram, E., Chen, A., Liu, D., Ying, L., Wang, Q., Yuan, M., and Yu, Z., “Nanophotonic media for artificial neural inference,” Photonics Research 7(8) (2019): 823–827. The authors computationally designed a thin sheet of glass, its interior patterned with subwavelength air inclusions, that in simulation classifies images of handwritten digits passively as light passes through it, performing the weighted summation of a neural network with no power source and no electronic circuitry.

Note 25. For reservoir computing in physical substrates, see Tanaka, G., et al., “Recent advances in physical reservoir computing,” Neural Networks 115 (2019): 100-123. Reviews computational capabilities demonstrated in glass, ice, mechanical systems, and biological substrates, showing that a wide range of physical systems can perform useful computation through their natural dynamics.

Note 26. Nakagaki, T., Yamada, H., and Tóth, Á., “Maze-solving by an amoeboid organism,” Nature 407 (2000): 470. The slime mold Physarum polycephalum, first spread throughout a maze and then offered food at two points, retracted from every tube except the shortest channel connecting the food sources. The computation was distributed and needed no nervous system or central coordinator.

Note 27. Berg, H.C. and Brown, D.A., “Chemotaxis in Escherichia coli analysed by three-dimensional tracking,” Nature 239 (1972): 500–504. By tracking individual bacteria in three dimensions, Berg and Brown established the run-and-tumble mechanism: cells alternate smooth forward runs with random reorienting tumbles, and climb a chemical gradient by suppressing tumbles for as long as conditions keep improving.

Note 28. Salek, M.M., Carrara, F., Fernandez, V., Guasto, J.S., and Stocker, R., “Bacterial chemotaxis in a microfluidic T-maze reveals strong phenotypic heterogeneity in chemotactic sensitivity,” Nature Communications 10 (2019): 1877. Clonal E. coli navigating a sequence of four T-junctions, each overlaid on a background gradient of the chemoattractant α-methylaspartate, showed substantial individual variation in chemotactic performance. The measured quantity is which branch a cell takes at each junction, not how quickly it traverses the device, and the authors localize the variation to the chemotactic sensitivity coefficient, arising from a distribution of pathway gains rather than from differences in swimming speed or receptor number alone. Elowitz’s foundational work on stochastic gene expression: Elowitz, M.B. et al., “Stochastic gene expression in a single cell,” Science 297 (2002): 1183–1186. Methylobacterium extorquens formaldehyde tolerance: Lee, J.A. et al., “Microbial phenotypic heterogeneity in response to a metabolic toxin: Continuous, dynamically shifting distribution of formaldehyde tolerance in Methylobacterium extorquens populations,” PLOS Genetics 15(11) (2019): e1008458. Arnold, C., “Bacterial Clones Show Surprising Individuality,” Quanta Magazine (4 September 2019). The same genus has since been observed thriving within radiation fog itself, where cells enlarge and divide in the droplets and degrade atmospheric formaldehyde roughly 200 times faster than rates measured in cloud water; the degradation is protective rather than nutritive, so any air-cleaning effect is a byproduct of the cells’ self-maintenance. Methylobacterium growth in radiation fog: Cao, T.T.T., Herckes, P., Straub, D., Sarkar, S., and Garcia-Pichel, F., “Growth and formaldehyde degradation of photoheterotrophic Methylobacterium within radiation fogs,” mBio (2026), doi:10.1128/mbio.00463-26.

Note 29. Hofstadter, Douglas R., Gödel, Escher, Bach: An Eternal Golden Braid (Basic Books, 1979), p. 537.