Notes: Chapter 5: Complex Worlds, Simple Rules

Chapter notes for “Chapter 5: Complex Worlds, Simple Rules”

Notes

¹ 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.

^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.

² 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.

³ Matthew Cook, “Universality in Elementary Cellular Automata,” Complex Systems 15 (2004): 1-40. The proof that Rule 110 is Turing complete was controversial and took years to publish due to legal disputes.

⁴ 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.

⁵ 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.

⁶ 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.

⁷ 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.

⁸ Nassim Nicholas Taleb, The Black Swan: The Impact of the Highly Improbable (2007). Taleb’s Mediocristan/Extremistan distinction captures a fundamental difference in the statistics of different domains. The Turkey Problem illustrates how observational data becomes systematically misleading in Extremistan — where the rare catastrophic event dominates outcomes.

⁹ 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).

¹⁰ 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.

¹¹ 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.

¹² 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 — maximizing colony-level foraging efficiency through purely local decisions. 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.

¹³ 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 are from Daniels, B.C., Flack, J.C., and Krakauer, D.C., analyzed in collaboration with data collected by William Newsome’s group at Stanford. 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).

¹⁴ 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 — demonstrating that a small number of stabilizers maintain collective order.

¹⁵ 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.

¹⁶ 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.

¹⁷ 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).

¹⁸ 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).

¹⁹ 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).

²⁰ 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).

²¹ Jiao, Y., et al., “Avian photoreceptor patterns represent a disordered hyperuniform solution to a multiscale packing problem,” Physical Review E 89 (2014): 022721. The study demonstrates that bird retinal photoreceptor distributions are hyperuniform — suppressing large-scale density fluctuations while maintaining small-scale disorder, representing an optimal solution to the problem of packing multiple cone types for visual acuity.

²² 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.

²³ 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.

²⁴ 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.

²⁵ 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.

²⁶ 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 — a distributed computation requiring no nervous system or central coordinator.

²⁷ 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.

²⁸ 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.

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