Notes: The Computational Universe

Chapter notes for “The Computational Universe”

Notes

¹ Liping Zhu, Song-Ju Kim, Masahiko Hara, and Masashi Aono, “Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism,” Royal Society Open Science 5 (2018): 180396. Both listed affiliations (the Faculty of Environment and Information Studies and the Graduate School of Media and Governance) are at Keio University’s Shonan Fujisawa Campus in Fujisawa, Kanagawa, roughly 50 km southwest of central Tokyo. Earlier work in the same programme: Aono et al., “Amoeba-based computing for traveling salesman problem,” BioSystems 112 (2013): 83-89.

Three details from the paper bear on how the result should be read. Solution quality is stated against the mean tour length rather than the optimum: the paper reports Lexp/Lmean ratios in the range 0.90 to 0.93, concluding that “the average length of the tour found by the plasmodium remained significantly shorter than the mean value for all n,” with no measurement of the gap to the shortest route. Problem sizes ran from four to eight cities, and the authors give the reason for the ceiling: “The reason why in this study the number of cities n was limited to eight was that we were not able to fabricate the chip with more than 64 lanes, owing to the size limit of the photolithography equipment.” The lane encoding is n x n, so hardware cost grows quadratically even as solution time grows linearly.

^1a Aono, quoted in Lisa Zyga, “Amoeba finds approximate solutions to NP-hard problem in linear time,” Phys.org, 20 December 2018. The remark is from correspondence with the reporter, not from the paper, and the terms are glossed loosely there: n is the body area needed to express a finished solution, which the paper’s encoding ties to the number of cities, and x is described only as a constant rate of gelatinous supply, with no units or measured value given in any source.

² Romain P. Boisseau, David Vogel, and Audrey Dussutour, “Habituation in non-neural organisms: evidence from slime moulds,” Proceedings of the Royal Society B 283(1829) (2016): 20160446. The transfer of that habituation between organisms by fusion is reported in the companion study: Vogel and Dussutour, “Direct transfer of learned behaviour via cell fusion in non-neural organisms,” Proceedings of the Royal Society B 283 (2016): 20162382.

³ CNRS/University of Toulouse III, “Slime mold absorbs substances to memorize them” (2019). Physarum polycephalum learns to tolerate aversive substances by absorbing them—memory as material incorporation.

⁴ Mirna Kramar and Karen Alim, “Encoding memory in tube diameter hierarchy of living flow network,” PNAS 118 (2021): e2007815118. The tubes that persist longest “directly bear the memory of the nutrient stimulus.” Note ¹⁶ below gives the mechanism from this same paper: the two notes cite one study, not two.

^4a A widely shared video (https://www.youtube.com/watch?v=N-RGFaCeru4) depicts a Physarum trained over weeks to accept an initially rejected food, then reversing a naive partner’s avoidance after fusion. It illustrates the principle vividly, yet it is a popular demonstration rather than a peer-reviewed result; the documented fusion-transfer finding is habituation to salt (Vogel and Dussutour 2016, ² above).

⁵ See Chapter 5 notes (⁹) for the Euplotes microtubule mechanical computer reference (Larson et al., Current Biology 2022).

⁶ Sharon Glotzer, interview in Quanta Magazine (2017): “Digital Alchemist Sharon Glotzer Seeks Rules of Emergence.” See Damasceno et al., “Predictive Self-Assembly of Polyhedra into Complex Structures,” Science 337 (2012): 453-457.

⁹ Susanne Still et al., “Thermodynamics of prediction,” Physical Review Letters 109 (2012): 120604.

¹⁰ Jeremy England, “Statistical physics of self-replication,” Journal of Chemical Physics 139 (2013): 121923.

¹¹ Andrew Adamatzky, “Physarum machines: computers from slime mould,” World Scientific (2010). See also Adamatzky et al., arXiv:1108.4956 for maze-solving dynamics.

¹³ Alan Turing, “The Chemical Basis of Morphogenesis,” Philosophical Transactions of the Royal Society B 237 (1952): 37-72. For the shark denticle research confirming conservation across 450 million years: Gareth Fraser et al., Science Advances (2018).

¹⁴ Bacterial biofilm intelligence and kin discrimination: Süel Lab, UC San Diego. Division of labor in biofilms: Nadell et al., Nature Reviews Microbiology 14 (2016): 589-600.

¹⁶ Slime mold tube restructuring mechanism: Mirna Kramar and Karen Alim, PNAS 118 (2021): e2007815118. A nutrient source “locally releases a softening agent that gets transported by the cytoplasmic flows within the tubular network. Tubes receiving a lot of softening agent grow in diameter at the expense of other tubes shrinking. Thereby, the tubes’ capacities for flow-based transport get permanently upgraded toward the nutrient location, redirecting future decisions and migration.” The paper does not name the agent chemically. The book previously described these diameter changes as “irreversible”; the paper’s own term is “permanently upgraded,” which supports durability but not irreversibility, since the same mechanism grows and shrinks tubes as new events arrive.

¹⁸ Leslie Valiant, Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World (Basic Books, 2013).

¹⁹ Hector Zenil et al., “Evolution of algorithmic complexity,” PLOS Computational Biology (2018).

²⁰ Electronic amoeba: Hokkaido University (2020), “Electronic amoeba finds approximate solution to traveling salesman problem in linear time.” Ising machines: Stanford/NTT implementations described in Physics World (2019).

²¹ Joseph Burchett et al., “Revealing the Dark Threads of the Cosmic Web,” Astrophysical Journal Letters 891 (2020): L35. The Monte Carlo Physarum Machine algorithm is described in detail. Validation against Bolshoi-Planck simulation achieved “almost perfect fit” to density fields.

²² Atsushi Tero, Toshiyuki Nakagaki, et al., “Rules for biologically inspired adaptive network design,” Science 327 (2010): 439–442. The Tokyo railway experiment won the 2010 Ig Nobel Prize in Transportation Planning.

²⁴ Krishna Palem et al., “Inexact computing improves answers,” Rice University/Argonne/UIUC (2016). Sacrificing intermediate precision improved final solution quality by 1000x at same energy cost.

²⁷ Sangram Bagh et al., “Distributed computing with engineered bacteria and its application in solving chemically generated 2x2 maze problems,” ACS Synthetic Biology (2021). Six types of engineered E. coli collectively solve maze problems with 100% accuracy.

²⁸ Programmable DNA gate arrays: Lv, H. et al., Nature 622 (2023): 292-300. Over 100 billion distinct circuits implementable via DNA origami architecture. Storage density: ~1 exabyte per cubic millimeter.

²⁹ Michael Levin, “Bioelectric signaling: Reprogrammable circuits underlying embryogenesis, regeneration, and cancer,” Cell 184 (2021): 1971-1989. See also Levin, “The bioelectric code,” Biosystems 164 (2018): 76-93.

³⁰ John Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” PNAS 79 (1982): 2554-2558. Nobel Prize in Physics 2024 (shared with Geoffrey Hinton). Simulated annealing was introduced separately by Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., “Optimization by simulated annealing,” Science 220 (1983): 671-680. For memristor-based annealing: Cai et al., Nature Electronics 3 (2020): 409-418.

³³ Daniel Wolpert, “The real reason for brains,” TED Talk (2011). The sea squirt example illustrates that brains evolved primarily for movement prediction.

³⁴ Andrew Adamatzky, “Slime mould logical gates: exploring ballistic approach,” arXiv:1005.2301 (2010). Source of the size-discriminated gate described in the text: “In input scenarios (0,1) and (1,0) size of propagating wave-fragment was not enough for the fragment to branch into output channel p… When two wave-fragments are initiated… they merge into a single larger-wave fragment. This new fragment propagates towards output q and also expands into output channel p.” Two caveats the prose compresses. The discriminator is fragment size and front curvature, not depletion of the medium; and the gate is a two-output device, so a lone input still leaves by the straight-ahead channel rather than vanishing. The “no strict rules on repelling and merging” observation about laboratory plasmodia is from the same paper. On Turing completeness in this substrate see also Adamatzky, “Physarum machine: implementation of a Kolmogorov-Uspensky machine on a biological substrate,” Parallel Processing Letters 17 (2007): 455-467.

³⁵ Andrew Adamatzky, Ben De Lacy Costello, and Tomohiro Shirakawa, “Universal Computation with Limited Resources: Belousov-Zhabotinsky and Physarum Computers,” International Journal of Bifurcation and Chaos 18(8) (2008): 2373-2389; preprint arXiv:0711.2711. The quoted sentence opens the abstract, which continues: “In situations of limited resources the systems studied develop travelling localizations. The localizations are elementary units of dynamical logical circuits in collision-based computing architectures.” The claim is about universal computation in an unconstrained medium, and it should not be read as saying that a well-fed slime mold computes nothing: Nakagaki’s maze-solving and network-optimization results run on nutrient-rich substrate. What abundance destroys is localization, not pattern. The nutrient-rich regime produces uniform circular growth, the organism’s analogue of the target waves seen in an excitable chemical medium.

³⁷ “Cellular supremacy”: The term emerged in 2024 biocomputing literature. See Communications of the ACM (2024): “Biocomputation: Moving Beyond Turing with Living Cellular Computers.”

³⁸ Brain organoid computing: See arXiv (2025): “Brain Organoid Computing—an Overview.”

³⁹ Slime mold as memristor: Whiting et al., Frontiers in Soft Matter (2025).

⁴⁰ Andrew Adamatzky, “We are chemical computers,” interview in npj Unconventional Computing launch (2024).

⁴¹ George Dyson, Turing’s Cathedral: The Origins of the Digital Universe (Pantheon, 2012). Primary source for the Baricelli, Bigelow, and IAS computer history in this chapter.

⁴² Nils Baricelli, “Symbiogenetic Evolution Processes Realized by Artificial Methods,” Methodos 9 (1957): 143-182.

⁴³ Julian Bigelow’s distinction between sequence and time appears in unpublished notes and interviews conducted by Dyson. See Turing’s Cathedral, chapters 11-12.

⁴⁴ The Monte Carlo method: Stanisław Ulam, “Adventures of a Mathematician” (Scribner, 1976); N. Metropolis, “The Beginning of the Monte Carlo Method,” Los Alamos Science 15 (1987): 125-130.

⁴⁵ Wolpert, D.H., “The stochastic thermodynamics of computation,” Journal of Physics A 52 (2019): 193001.

⁴⁷ Sender, R., Fuchs, S., and Milo, R., “Revised Estimates for the Number of Human and Bacteria Cells in the Body,” Cell 164 (2016): 337-340.

⁴⁸ The exabyte-per-cubic-millimeter figure is a theoretical ceiling, from Zhirnov, V., Zadegan, R.M., Sandhu, G.S., Church, G.M., and Hughes, W.L., “Nucleic acid memory,” Nature Materials 15 (2016): 366–370. DOI: 10.1038/nmat4594. It applies to data written directly into the base sequence, and the paper is explicit that densities attained in practice are far lower, since approaches relying on DNA secondary structure need on the order of a hundred base pairs per bit. For a demonstrated write-and-read at a density orders of magnitude below the ceiling, see Church, G.M., Gao, Y., and Kosuri, S., “Next-Generation Digital Information Storage in DNA,” Science 337 (2012): 1628, which encoded a digital book in DNA and recovered it. The distinction matters: the ceiling is what the chemistry permits, not what anyone has built.

⁴⁹ Campbell, John O., “Universal Darwinism as a process of Bayesian inference,” Frontiers in Systems Neuroscience 10 (2016): 49.