Skip to main content

cellular automata directory

See Also


“Variational Neural Cellular Automata”, Palm et al 2022

“Variational Neural Cellular Automata”⁠, Rasmus Berg Palm, Miguel González-Duque, Shyam Sudhakaran, Sebastian Risi (2022-01-28; backlinks; similar):

In nature, the process of cellular growth and differentiation has lead to an amazing diversity of organisms—algae, starfish, giant sequoia, tardigrades, and orcas are all created by the same generative process. Inspired by the incredible diversity of this biological generative process, we propose a generative model, the Variational Neural Cellular Automata (VNCA), which is loosely inspired by the biological processes of cellular growth and differentiation. Unlike previous related works, the VNCA is a proper probabilistic generative model, and we evaluate it according to best practices. We find that the VNCA learns to reconstruct samples well and that despite its relatively few parameters and simple local-only communication, the VNCA can learn to generate a large variety of output from information encoded in a common vector format. While there is a significant gap to the current state-of-the-art in terms of generative modeling performance, we show that the VNCA can learn a purely self-organizing generative process of data. Additionally, we show that the VNCA can learn a distribution of stable attractors that can recover from significant damage.

“Fundamental Behaviors Emerge from Simulations of a Living Minimal Cell”, Thornburg et al 2022

“Fundamental behaviors emerge from simulations of a living minimal cell”⁠, Zane R. Thornburg, David M. Bianchi, Troy A. Brier, Benjamin R. Gilbert, Tyler M. Earnest, Marcelo C.R. Melo et al (2022-01-20; ; backlinks; similar):

  • 3D spatial resolution of a fully dynamical whole-cell kinetic model
  • Detailed single-reaction, single-cell accounting of time-dependent ATP costs
  • Genome-wide mRNA half-lives emerge from length-dependent kinetics and diffusion
  • Connections among metabolism, genetic information, and cell growth are revealed

[media] We present a whole-cell fully dynamical kinetic model (WCM) of JCVI-syn3A⁠, a minimal cell with a reduced genome of 493 genes that has retained few regulatory proteins or small RNAs⁠. Cryo-electron tomograms provide the cell geometry and ribosome distributions.

Time-dependent behaviors of concentrations and reaction fluxes from stochastic-deterministic simulations over a cell cycle reveal how the cell balances demands of its metabolism, genetic information processes, and growth, and offer insight into the principles of life for this minimal cell. The energy economy of each process including active transport of amino acids⁠, nucleosides⁠, and ions is analyzed. WCM reveals how emergent imbalances lead to slowdowns in the rates of transcription and translation⁠.

Integration of experimental data is critical in building a kinetic model from which emerges a genome-wide distribution of mRNA half-lives, multiple DNA replication events that can be compared to qPCR results, and the experimentally observed doubling behavior.

[Keywords: minimal cell, JCVI-syn3A, whole-cell kinetic model, metabolism, genetic information processing, time-dependent ATP costs, mRNA half-lives, qPCR, hybrid stochastic-deterministic simulations]

“Collective Intelligence for Deep Learning: A Survey of Recent Developments”, Ha & Tang 2021

“Collective Intelligence for Deep Learning: A Survey of Recent Developments”⁠, David Ha, Yujin Tang (2021-11-29; ; similar):

In the past decade, we have witnessed the rise of deep learning to dominate the field of artificial intelligence. Advances in artificial neural networks alongside corresponding advances in hardware accelerators with large memory capacity, together with the availability of large datasets enabled practitioners to train and deploy sophisticated neural network models that achieve state-of-the-art performance on tasks across several fields spanning computer vision, natural language processing, and reinforcement learning. However, as these neural networks become bigger, more complex, and more widely used, fundamental problems with current deep learning models become more apparent. State-of-the-art deep learning models are known to suffer from issues that range from poor robustness, inability to adapt to novel task settings, to requiring rigid and inflexible configuration assumptions. Collective behavior, commonly observed in nature, tends to produce systems that are robust, adaptable, and have less rigid assumptions about the environment configuration. Collective intelligence, as a field, studies the group intelligence that emerges from the interactions of many individuals. Within this field, ideas such as self-organization, emergent behavior, swarm optimization, and cellular automata were developed to model and explain complex systems. It is therefore natural to see these ideas incorporated into newer deep learning methods. In this review, we will provide a historical context of neural network research’s involvement with complex systems, and highlight several active areas in modern deep learning research that incorporate the principles of collective intelligence to advance its current capabilities. We hope this review can serve as a bridge between the complex systems and deep learning communities.

“𝜇NCA: Texture Generation With Ultra-Compact Neural Cellular Automata”, Mordvintsev & Niklasson 2021

“𝜇NCA: Texture Generation with Ultra-Compact Neural Cellular Automata”⁠, Alexander Mordvintsev, Eyvind Niklasson (2021-11-26; ⁠, ; backlinks; similar):

We study the problem of example-based procedural texture synthesis using highly compact models. Given a sample image, we use differentiable programming to train a generative process, parameterised by a recurrent Neural Cellular Automata (NCA) rule.

Contrary to the common belief that neural networks should be highly over-parameterised, we demonstrate that our model architecture and training procedure allows for representing complex texture patterns using just a few hundred learned parameters, making their expressivity comparable to hand-engineered procedural texture generating programs. The smallest models from the proposed 𝜇NCA family scale down to 68 parameters. When using quantisation to one byte per parameter, proposed models can be shrunk to a size range between 588 and 68 bytes.

Implementation of a texture generator that uses these parameters to produce images is possible with just a few lines of GLSL or C code.

“Texture Generation With Neural Cellular Automata”, Mordvintsev et al 2021

“Texture Generation with Neural Cellular Automata”⁠, Alexander Mordvintsev, Eyvind Niklasson, Ettore Randazzo (2021-05-15; backlinks; similar):

Neural Cellular Automata (NCA) have shown a remarkable ability to learn the required rules to “grow” images, classify morphologies, segment images, as well as to do general computation such as path-finding. We believe the inductive prior they introduce lends itself to the generation of textures. Textures in the natural world are often generated by variants of locally interacting reaction-diffusion systems. Human-made textures are likewise often generated in a local manner (textile weaving, for instance) or using rules with local dependencies (regular grids or geometric patterns). We demonstrate learning a texture generator from a single template image, with the generation method being embarrassingly parallel, exhibiting quick convergence and high fidelity of output, and requiring only some minimal assumptions around the underlying state manifold. Furthermore, we investigate properties of the learned models that are both useful and interesting, such as non-stationary dynamics and an inherent robustness to damage. Finally, we make qualitative claims that the behaviour exhibited by the NCA model is a learned, distributed, local algorithm to generate a texture, setting our method apart from existing work on texture generation. We discuss the advantages of such a paradigm.

“Synthetic Living Machines: A New Window on Life”, Ebrahimkhani & Levin 2021

“Synthetic living machines: A new window on life”⁠, Mo R. Ebrahimkhani, Michael Levin (2021-05-03; backlinks; similar):

Increased control of biological growth and form is an essential gateway to transformative medical advances. Repairing of birth defects, restoring lost or damaged organs, normalizing tumors, all depend on understanding how cells cooperate to make specific, functional large-scale structures. Despite advances in molecular genetics, substantial gaps remain in our understanding of the meso-scale rules of morphogenesis.

An engineering approach to this problem is the creation of novel synthetic living forms, greatly extending available model systems beyond evolved plant and animal lineages. Here, we review recent advances in the emerging field of synthetic morphogenesis, the bioengineering of novel multicellular living bodies. Emphasizing emergent self-organization, tissue-level guided self-assembly, and active functionality, this work is the essential next generation of synthetic biology⁠.

Aside from useful living machines for specific functions, the rational design and analysis of new, coherent anatomies will greatly increase our understanding of foundational questions in evolutionary developmental and cell biology.

[Keywords: developmental biology, bioengineering, synthetic biology]

“Cells Form Into ‘Xenobots’ on Their Own: Embryonic Cells Can Self-assemble into New Living Forms That Don’t Resemble the Bodies They Usually Generate, Challenging Old Ideas of What Defines an Organism”, Ball 2021

“Cells Form Into ‘Xenobots’ on Their Own: Embryonic cells can self-assemble into new living forms that don’t resemble the bodies they usually generate, challenging old ideas of what defines an organism”⁠, Philip Ball (2021-03-31; ; backlinks; similar):

Early last year, the biologist Michael Levin and his colleagues offered a glimpse of how versatile living matter can be. Levin and Douglas Blackiston, a member of his laboratory at the Allen Discovery Center of Tufts University, brought together nascent skin and muscle cells from a frog embryo and shaped the multicelled assemblies by hand. This sculpting process was guided by an algorithm developed by the computer scientists Josh Bongard and Sam Kriegman of the University of Vermont, which searched for simulated arrangements of the 2 cell types capable of organized movement. One design, for example, had 2 twitching leglike stumps on the bottom for pushing itself along.

The researchers let the cell clusters assemble in the right proportions and then used micro-manipulation tools to move or eliminate cells—essentially poking and carving them into shapes like those recommended by the algorithm. The resulting cell clusters showed the predicted ability to move over a surface in a nonrandom way.

The team dubbed these structures xenobots (Kriegman et al 2020). While the prefix was derived from the Latin name of the African clawed frogs (Xenopus laevis) that supplied the cells, it also seemed fitting because of its relation to xenos, the ancient Greek for “strange.” These were indeed strange living robots: tiny masterpieces of cell craft fashioned by human design. And they hinted at how cells might be persuaded to develop new collective goals and assume shapes totally unlike those that normally develop from an embryo.

…Some of those answers are now being unveiled in work appearing today in Science Robotics⁠. It describes a new generation of xenobots—ones that took shape on their own, entirely without human guidance or assistance.

…The experiments described in the paper published today were remarkably simple. The same team of researchers, along with Emma Lederer of Levin’s lab, removed cells from developing frog embryos that had already specialized into epithelial cells and left them to develop in clusters on their own without the rest of the embryo, which normally provides the signals that guide cells to become the “right” type in the “right” place.

What the cells did first was unremarkable: They gathered into a ball, composed of dozens of cells or a few hundred. That kind of behavior was already well known and reflects the tendency of skin cells to make their surface area as small as possible after tissue damage, which helps wounds to heal.

Then things got weird. Frog skin is generally covered with a protective layer of mucus that keeps it moist; to ensure that the mucus covers the skin evenly, the skin cells have little hairlike protrusions called cilia, which can move and beat. We have them, too, on the lining of our lungs and respiratory tract, where their beating motion helps sweep away dirt in the mucus. But the frog skin cell clusters quickly began to use their cilia for a different purpose: to swim around by beating in coordinated waves. A midline formed on the cluster, “and the cells on one side row to the left and those on the other side row to the right, and this thing takes off. It starts zooming around”, Levin said

…Levin thinks that cells also commonly communicate electrically—that this isn’t just a property of nerve cells, although they may have specialized to make good use of it. In a xenobot, “there’s a network of calcium signaling”, Levin said—an exchange of calcium ions like that seen between neurons. “These skin cells are using the same electrical properties that you would find in the neural network of a brain.”

For example, if 3 xenobots are set spaced apart in a row, and one of them is activated by being pinched, it will emit a pulse of calcium that, within seconds, shows up in the other 2—“a chemical signal that goes through the water saying that someone just got attacked”, Levin said. He thinks that intercellular communications create a sort of code that imprints a form, and that cells can sometimes decide how to arrange themselves more or less independently of their genes. In other words, the genes provide the hardware, in the form of enzymes and regulatory circuits for controlling their production. But the genetic input doesn’t in itself specify the collective behavior of cell communities.

Instead, Levin thinks that it programs cells with an ensemble of tendencies that produce a repertoire of behaviors. Under the normal conditions of embryogenesis, those behaviors follow a certain path toward forming the organisms we know. But give the cells a very different set of circumstances, and other behaviors and new emergent shapes will appear. “What the genome provides for the cells is some mechanism that allows them to undertake goal-directed activities”, Levin said—in effect, a drive to adapt and survive.

…Jablonka guesses that the behaviors on display in the xenobots are probably “something like the most basic self-organization of a multicellular animal-cell aggregate.” That is, they are what happens when both the constraints on form and the resources and opportunities provided by the environment are minimal. “It tells you something about the physics of biological, developing multicellular systems”, she said: “how sticky animal cells interact.” For that reason, she thinks the work might hold clues to the emergence of multicellularity in evolutionary history.

“A Cellular Platform for the Development of Synthetic Living Machines”, Blackiston et al 2021

2021-blackiston.pdf: “A cellular platform for the development of synthetic living machines”⁠, Douglas Blackiston, Emma Lederer, Sam Kriegman, Simon Garnier, Joshua Bongard, Michael Levin (2021-03-31; ; backlinks; similar):

Robot swarms have, to date, been constructed from artificial materials. Motile biological constructs have been created from muscle cells grown on precisely shaped scaffolds. However, the exploitation of emergent self-organization and functional plasticity into a self-directed living machine has remained a major challenge.

We report here a method for generation of in vitro biological robots from frog (Xenopus laevis) cells. These xenobots exhibit coordinated locomotion via cilia present on their surface. These cilia arise through normal tissue patterning and do not require complicated construction methods or genomic editing, making production amenable to high-throughput projects. The biological robots arise by cellular self-organization and do not require scaffolds or microprinting; the amphibian cells are highly amenable to surgical, genetic, chemical, and optical stimulation during the self-assembly process.

We show that the xenobots can navigate aqueous environments in diverse ways, heal after damage, and show emergent group behaviors. We constructed a computational model to predict useful collective behaviors that can be elicited from a xenobot swarm. In addition, we provide proof of principle for a writable molecular memory using a photoconvertible protein that can record exposure to a specific wavelength of light.

Together, these results introduce a platform that can be used to study many aspects of self-assembly, swarm behavior, and synthetic bioengineering, as well as provide versatile, soft-body living machines for numerous practical applications in biomedicine and the environment.

“Growing 3D Artefacts and Functional Machines With Neural Cellular Automata”, Sudhakaran et al 2021

“Growing 3D Artefacts and Functional Machines with Neural Cellular Automata”⁠, Shyam Sudhakaran, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, Sebastian Risi et al (2021-03-15; backlinks; similar):

Neural Cellular Automata (NCAs) have been proven effective in simulating morphogenetic processes, the continuous construction of complex structures from very few starting cells. Recent developments in NCAs lie in the 2D domain, namely reconstructing target images from a single pixel or infinitely growing 2D textures. In this work, we propose an extension of NCAs to 3D, utilizing 3D convolutions in the proposed neural network architecture.

Minecraft is selected as the environment for our automaton since it allows the generation of both static structures and moving machines. We show that despite their simplicity, NCAs are capable of growing complex entities such as castles, apartment blocks, and trees, some of which are composed of over 3,000 blocks. Additionally, when trained for regeneration, the system is able to regrow parts of simple functional machines, significantly expanding the capabilities of simulated morphogenetic systems.

The code for the experiment in this paper can be found at: Github⁠.

“Nothing in Evolution Makes Sense except in the Light of Parasites”, Hickinbotham et al 2021

“Nothing in evolution makes sense except in the light of parasites”⁠, Simon John Hickinbotham, Susan Stepney, Paulien Hogeweg (2021-02-25; ; similar):

The emergence of parasites in evolving replicating systems appears to be inevitable. Parasites emerge readily in models and laboratory experiments of the hypothesised earliest replicating systems: the RNA world. Phylogenetic reconstructions also suggest very early evolution of viruses and other parasitic mobile genetic elements in our biosphere. The evolution of such parasites would lead to extinction unless prevented by compartmentalization or spatial pattern formation, and the emergence of multilevel selection. Today and apparently since the earliest times, many intricate defence and counter-defence strategies have evolved.

Here we bring together for the first time automata chemistry models and spatial RNA world models, to study the emergence of parasites and the evolving complexity to cope with the parasites. Our system is initialized with a hand-designed program string that copies other program strings one character at a time, with a small chance of point mutation. Almost immediately, short parasites arise; these are copied more quickly, and so have an evolutionary advantage. Spatial pattern formation, in the form of chaotic waves of replicators followed by parasites, can prevent extinction. The replicators also become shorter, and so are replicated faster. They evolve a mechanism to slow down replication, which reduces the difference of replication rate of replicators and parasites. They also evolve explicit mechanisms to discriminate copies of self from parasites; these mechanisms become increasingly complex. Replicators speciate into lineages and can become longer, despite the fitness cost that entails.

We do not see a classical co-evolutionary arms-race of a replicator and a parasite lineage: instead new parasite species continually arise from mutated replicators, rather than from evolving parasite lineages. Finally we note that evolution itself evolves, for example by effectively increasing point mutation rates, and by generating novel emergent mutational operators. The inevitable emergence of parasites in replicator systems drives the evolution of complex replicators and complex ecosystems with high population density. Even in the absence of parasites, the evolved replicators outperform the initial replicator and the early short replicators.

Modelling replication as an active computational process opens up many degrees of freedom that are exploited not only to meet environmental challenges, but also to modify the evolutionary process itself.

“Regenerating Soft Robots through Neural Cellular Automata”, Horibe et al 2021

“Regenerating Soft Robots through Neural Cellular Automata”⁠, Kazuya Horibe, Kathryn Walker, Sebastian Risi (2021-02-04; backlinks; similar):

Morphological regeneration is an important feature that highlights the environmental adaptive capacity of biological systems. Lack of this regenerative capacity significantly limits the resilience of machines and the environments they can operate in. To aid in addressing this gap, we develop an approach for simulated soft robots to regrow parts of their morphology when being damaged. Although numerical simulations using soft robots have played an important role in their design, evolving soft robots with regenerative capabilities have so far received comparable little attention. Here we propose a model for soft robots that regenerate through a neural cellular automata. Importantly, this approach only relies on local cell information to regrow damaged components, opening interesting possibilities for physical regenerable soft robots in the future. Our approach allows simulated soft robots that are damaged to partially regenerate their original morphology through local cell interactions alone and regain some of their ability to locomote. These results take a step towards equipping artificial systems with regenerative capacities and could potentially allow for more robust operations in a variety of situations and environments. The code for the experiments in this paper is available at: /  ​KazuyaHoribe /  ​RegeneratingSoftRobots⁠.

“An Antiviral Self-replicating Molecular Heterotroph”, Shapiro et al 2020

“An antiviral self-replicating molecular heterotroph”⁠, Anastasia Shapiro, Alexander Rosenberg, Adva Levy-Zamir, Liron Bassali, Shmulik Ittah, Almogit Abu-Horowitz et al (2020-08-14; ; similar):

We report the synthesis of a molecular machine, fabricated from nucleic acids, which is capable of digesting viral RNA and utilizing it to assemble additional copies of itself inside living cells. The machine’s body plan combines several parts that build upon the target RNA, assembling an immobile, DNA:RNA 4-way junction, which contains a single gene encoding a hammerhead ribozyme (HHR). Full assembly of the machine’s body from its parts enables the subsequent elongation of the gene and transcription of HHR molecules, followed by HHR-mediated digestion of the target molecule. This digestion converts the target to a building block suitable for participation in the assembly of more copies of the machine, mimicking biological heterotrophy. In this work we describe the general design of a prototypical machine, characterize its activity cycle and kinetics, and show that it can be efficiently and safely delivered into live cells. As a proof of principle, we constructed a machine that targets the Autographa californica multicapsid nucleopolyhedrovirus (AcMNPV) GP64 gene, and show that it effectively suppresses viral propagation in a cell population, exhibiting predator/​prey-like dynamics with the infecting virus. In addition, the machine significantly reduced viral infection, stress signaling, and innate immune activation inside virus-infected animals. This preliminary design could control the behavior of antisense therapies for a range of applications, particularly against dynamic targets such as viruses and cancer.

“The Recursive Universe”, Ghassaei 2020

“The Recursive Universe”⁠, Amanda Ghassaei (2020-05-01; similar):

A few years ago I came across this video⁠, showing a complex machine built entirely in Conway’s Game of Life:

[Zoom-out video of the OTCA Metapixel, showing the metapixels being used to emulate Conway’s Game of Life inside Conway’s Game of Life, as simulated in Golly by Phillip Bradbury in 2012.]

The purpose of the machine is to emulate a single Life pixel. With a big enough matrix of these “metapixels”, you can simulate a meta-version of Life on a massive scale. From there you could create a meta-metapixel out of metapixels and so on… This post is (mostly) some notes I took back in 2015 while trying to understand how this metapixel was designed.

  1. OTCA Metapixel
  2. Clock
  3. Encoding the Rules
  4. Counting Neighbors
  5. Comparing Neighbor Count with Rules
  6. Accessing Neighbor State
  7. Determining the Next State
  8. Output Display
  9. Further Reading

“Growing Neural Cellular Automata: Differentiable Model of Morphogenesis”, Mordvintsev et al 2020

“Growing Neural Cellular Automata: Differentiable Model of Morphogenesis”⁠, Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, Michael Levin (2020-02-11; ; backlinks; similar):

[ interactive explainer: you can train small CNNs to coordinate as cellular automata to create complex damage-resilient global patterns using standard deep learning techniques like backpropagation, since CNNs are differentiable⁠; the CNN updates such that when it is executed simultaneously in hundreds of ‘cells’, each cell can coordinate appropriately to emit a particular color and eg. form a complex lizard shape. Because it’s decentralized, any individual cell can be deleted and the damage healed.]

What is clear is that evolution has learned to exploit the laws of physics and computation to implement the highly robust morphogenetic software that runs on genome-encoded cellular hardware. This process is extremely robust to perturbations. Even when the organism is fully developed, some species still have the capability to repair damage—a process known as regeneration. Some creatures, such as salamanders, can fully regenerate vital organs, limbs, eyes, or even parts of the brain! Morphogenesis is a surprisingly adaptive process. Sometimes even a very atypical development process can result in a viable organism—for example, when an early mammalian embryo is cut in two, each half will form a complete individual—monozygotic twins!

The biggest puzzle in this field is the question of how the cell collective knows what to build and when to stop. The sciences of genomics and stem cell biology are only part of the puzzle, as they explain the distribution of specific components in each cell, and the establishment of different types of cells. While we know of many genes that are required for the process of regeneration, we still do not know the algorithm that is sufficient for cells to know how to build or remodel complex organs to a very specific anatomical end-goal. Thus, one major lynch-pin of future work in biomedicine is the discovery of the process by which large-scale anatomy is specified within cell collectives, and how we can rewrite this information to have rational control of growth and form.

…Let’s try to develop a cellular automata update rule that, starting from a single cell, will produce a predefined multicellular pattern on a 2D grid. This is our analogous toy model of organism development. To design the CA, we must specify the possible cell states, and their update function. Typical CA models represent cell states with a set of discrete values, although variants using vectors of continuous values exist. The use of continuous values has the virtue of allowing the update rule to be a differentiable function of the cell’s neighbourhood’s states. The rules that guide individual cell behavior based on the local environment are analogous to the low-level hardware specification encoded by the genome of an organism. Running our model for a set amount of steps from a starting configuration will reveal the patterning behavior that is enabled by such hardware.

…This article describes a toy embryogenesis and regeneration model. This is a major direction for future work, with many applications in biology and beyond. In addition to the implications for understanding the evolution and control of regeneration, and harnessing this understanding for biomedical repair, there is the field of bioengineering. As the field transitions from synthetic biology of single cell collectives to a true synthetic morphology of novel living machines, it will be essential to develop strategies for programming system-level capabilities, such as anatomical homeostasis (regenerative repair)…let’s speculate about what a “more physical” implementation of such a system could look like. We can imagine it as a grid of tiny independent computers, simulating individual cells. Each of those computers would require ~10Kb of ROM to store the “cell genome”: neural network weights and the control code, and about 256 bytes of RAM for the cell state and intermediate activations. The cells must be able to communicate their 16-value state vectors to neighbors. Each cell would also require an RGB-diode to display the color of the pixel it represents. A single cell update would require about 10k multiply-add operations and does not have to be synchronised across the grid. We propose that cells might wait for random time intervals between updates. The system described above is uniform and decentralised. Yet, our method provides a way to program it to reach the predefined global state, and recover this state in case of multi-element failures and restarts. We therefore conjecture this kind of modeling may be used for designing reliable, self-organising agents. On the more theoretical machine learning front, we show an instance of a decentralized model able to accomplish remarkably complex tasks. We believe this direction to be opposite to the more traditional global modeling used in the majority of contemporary work in the deep learning field, and we hope this work to be an inspiration to explore more decentralized learning modeling.

“Intrinsically Motivated Discovery of Diverse Patterns in Self-Organizing Systems”, Reinke et al 2019

“Intrinsically Motivated Discovery of Diverse Patterns in Self-Organizing Systems”⁠, Chris Reinke, Mayalen Etcheverry, Pierre-Yves Oudeyer (2019-08-19; similar):

In many complex dynamical systems, artificial or natural, one can observe self-organization of patterns emerging from local rules. Cellular automata, like the Game of Life (GOL), have been widely used as abstract models enabling the study of various aspects of self-organization and morphogenesis, such as the emergence of spatially localized patterns. However, findings of self-organized patterns in such models have so far relied on manual tuning of parameters and initial states, and on the human eye to identify interesting patterns.

In this paper, we formulate the problem of automated discovery of diverse self-organized patterns in such high-dimensional complex dynamical systems, as well as a framework for experimentation and evaluation. Using a continuous GOL as a testbed, we show that recent intrinsically-motivated machine learning algorithms (POP-IMGEPs), initially developed for learning of inverse models in robotics, can be transposed and used in this novel application area. These algorithms combine intrinsically-motivated goal exploration and unsupervised learning of goal space representations. Goal space representations describe the interesting features of patterns for which diverse variations should be discovered. In particular, we compare various approaches to define and learn goal space representations from the perspective of discovering diverse spatially localized patterns. Moreover, we introduce an extension of a state-of-the-art POP-IMGEP algorithm which incrementally learns a goal representation using a deep auto-encoder, and the use of CPPN primitives for generating initialization parameters. We show that it is more efficient than several baselines and equally efficient as a system pre-trained on a hand-made database of patterns identified by human experts.

“Lenia—Biology of Artificial Life”, Chan 2018

“Lenia—Biology of Artificial Life”⁠, Bert Wang-Chak Chan (2018-12-13; similar):

We report a new system of artificial life called Lenia (from Latin lenis “smooth”), a two-dimensional cellular automaton with continuous space-time-state and generalized local rule.

Computer simulations show that Lenia supports a great diversity of complex autonomous patterns or “lifeforms” bearing resemblance to real-world microscopic organisms. More than 400 species in 18 families have been identified, many discovered via interactive evolutionary computation. They differ from other cellular automata patterns in being geometric, metameric, fuzzy, resilient, adaptive, and rule-generic.

We present basic observations of the system regarding the properties of space-time and basic settings. We provide a broad survey of the lifeforms, categorize them into a hierarchical taxonomy, and map their distribution in the parameter hyperspace. We describe their morphological structures and behavioral dynamics, propose possible mechanisms of their self-propulsion, self-organization and plasticity.

Finally, we discuss how the study of Lenia would be related to biology, artificial life, and artificial intelligence.

“Cellular Automata As Convolutional Neural Networks”, Gilpin 2018

“Cellular automata as convolutional neural networks”⁠, William Gilpin (2018-09-09; backlinks; similar):

Deep learning techniques have recently demonstrated broad success in predicting complex dynamical systems ranging from turbulence to human speech, motivating broader questions about how neural networks encode and represent dynamical rules. We explore this problem in the context of cellular automata (CA), simple dynamical systems that are intrinsically discrete and thus difficult to analyze using standard tools from dynamical systems theory.

We show that any CA may readily be represented using a convolutional neural network with a network-in-network architecture. This motivates our development of a general convolutional multilayer perceptron architecture, which we find can learn the dynamical rules for arbitrary CA when given videos of the CA as training data. In the limit of large network widths, we find that training dynamics are nearly identical across replicates, and that common patterns emerge in the structure of networks trained on different CA rulesets.

We train ensembles of networks on randomly-sampled CA, and we probe how the trained networks internally represent the CA rules using an information-theoretic technique based on distributions of layer activation patterns. We find that CA with simpler rule tables produce trained networks with hierarchical structure and layer specialization, while more complex CA produce shallower representations—illustrating how the underlying complexity of the CA’s rules influences the specificity of these internal representations.

Our results suggest how the entropy of a physical process can affect its representation when learned by neural networks.

“Now What?”, Hopfield 2018 “Now What?”⁠, Hopfield (2018; ; backlinks)

“Is Spearman’s Law of Diminishing Returns (SLODR) Meaningful for Artificial Agents?”, Hernandez-Orallo 2016

2016-hernandezorallo.pdf: “Is Spearman’s law of diminishing returns (SLODR) meaningful for artificial agents?”⁠, Hernandez-Orallo (2016-01-01; ⁠, )

“Surprisingly Turing-Complete”, Branwen 2012

Turing-complete: “Surprisingly Turing-Complete”⁠, Gwern Branwen (2012-12-09; ⁠, ⁠, ⁠, ; backlinks; similar):

A catalogue of software constructs, languages, or APIs which are unexpectedly Turing-complete; implications for security and reliability

‘Computers’, in the sense of being Turing-complete, are extremely common. Almost any system of sufficient complexity—unless carefully engineered otherwise—may be found to ‘accidentally’ support Turing-complete somewhere inside it through ‘weird machines’ which can be rebuilt out of the original system’s parts, even systems which would appear to have not the slightest thing to do with computation. Software systems are especially susceptible to this, which often leads to serious security problems as the Turing-complete components can be used to run attacks on the rest of the system.

I provide a running catalogue of systems which have been, surprisingly, demonstrated to be Turing-complete. These examples may help unsee surface systems to see the weird machines and Turing-completeness lurking within.

“The Complexity of Small Universal Turing Machines: a Survey”, Neary & Woods 2011

“The complexity of small universal Turing machines: a survey”⁠, Turlough Neary, Damien Woods (2011-10-10):

We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing machines. We finish the survey with results on generalised and restricted Turing machine models including machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and machines that never write to their tape. We then discuss some ideas for future work.

“Implications of the Turing Completeness of Reaction-diffusion Models, Informed by GPGPU Simulations on an XBox 360: Cardiac Arrhythmias, Re-entry and the Halting Problem”, Scarle 2009

“Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: Cardiac arrhythmias, re-entry and the halting problem”⁠, Simon Scarle (2009-08-01; backlinks; similar):

In the arsenal of tools that a computational modeler can bring to bear on the study of cardiac arrhythmias the most widely used and arguably the most successful is that of an excitable medium, a special case of a reaction-diffusion model. These are used to simulate the internal chemical reactions of a cardiac cell and the diffusion of their membrane voltages. Via a number of different methodologies it has previously been shown that reaction-diffusion systems are at multiple levels Turing complete. That is, they are capable of computation in the same manner as an universal Turing machine. However, all such computational systems are subject to a limitation known as the Halting problem.

By constructing an universal logic gate using a cardiac cell model, we highlight how the Halting problem therefore could limit what it is possible to predict about cardiac tissue, arrhythmias and re-entry. All simulations for this work were carried out on the GPU of an XBox 360 development console, and we also highlight the great gains in computational power and efficiency produced by such general purpose processing on a GPU for cardiac simulations.

[Keywords: heart, re-entry, cardiac arrhythmias, excitable media, halting problem, GPGPU]

“The Determination of the Value of Rado's Noncomputable Function Σ(𝑘) for Four-state Turing Machines”, Brady 1983

1983-brady.pdf: “The determination of the value of Rado's noncomputable function Σ(𝑘) for four-state Turing machines”⁠, Allen H. Brady (1983-04-01; backlinks; similar):

The well-defined but noncomputable functions Σ(k) and S(k) given by T. Rado as the “score” and “shift number” for the k-state Turing machine “Busy Beaver Game” were previously known only for k ≤ 3. The largest known lower bounds yielding the relations Σ(4) ≥ 13 and S(4) ≥ 107, reported by this author, supported the conjecture that these lower bounds are the actual particular values of the functions for k = 4.

The four-state case has previously been reduced to solving the blank input tape halting problem of only 5,820 individual machines. In this final stage of the k = 4 case, one appears to move into a heuristic level of higher order where it is necessary to treat each machine as representing a distinct theorem.

The remaining set consists of two primary classes in which a machine and its tape are viewed as the representation of a growing string of cellular automata. The proof techniques, embodied in programs, are entirely heuristic, while the inductive proofs, once established by the computer, are completely rigorous and become the key to the proof of the new and original mathematical results: Σ(4) = 13 and S(4) = 107.

“OTCA Metapixel”, Wiki 2022

“OTCA metapixel”⁠, Life Wiki:

The OTCA metapixel (RLE) is a 2,048 × 2,048 period 35,328 unit cell that was constructed by Brice Due between the autumn of 2005 and the spring of 2006. It has many advantages over the previous-known unit cells such as the p5760 unit Life cell and deep cell, including the ability to emulate any Life-like cellular automaton and the fact that, when zoomed out, the ON and OFF cells are easy to distinguish (the ON version of the cell is shown to the right and the OFF version of the cell is shown below).

It is designed to run quickly under the Hashlife algorithm, and thus Golly is generally used to view and/​or manipulate meta-patterns made up of OTCA metapixels (and some such patterns even come packaged with Golly).

Meta-metapixels: It is possible to use the OTCA metapixel to emulate itself, and emulate other patterns on the resulting meta-metapixel. Adam P. Goucher presented a meta-meta-blinker in December 2016, with a period of 2,496,135,168 (= 2 · 35,3282), noting that Golly can successfully run the entire period over the course of a day at a step size of 85.

Rule 110




Day and Night (cellular automaton)


Conway's Game of Life


Continuous spatial automaton


Cellular automaton


Book of Soyga


“Building a Working Game of Tetris in Conway’s Game of Life” “Building a working game of Tetris in Conway’s Game of Life” (backlinks)

“From Brainfuck to Domino Computers: A Trip into Esoteric Languages, Turing Machines, Cellular Automata and the Nature of Computation” “From Brainfuck to Domino Computers: A trip into Esoteric Languages, Turing Machines, Cellular Automata and the Nature of Computation” (backlinks)