130 views
**Gliders and similar phenomena in (categorical) systems theory** Martin Biehl <!-- Gliders should be in trajectories. Trajectories are morphisms from a small system into an other system. But we want to combine the trajectories of two systems so that they form the trajectory of a third (possibly closed) system. This is like combininig two transducers? Probably yes, but that also doesn't allow us to have gliders that are created and destroyed. --> What is the question? Gliders in the Game of Life cellular automaton (CA) and other similar phenomena in neural CAs and reaction diffusion systems remain unaccounted for in categorical systems theory (and mathematics in general). Challenges they pose include: * How to describe a system moving through (a factorization of) another system? * How to describe a system that can grow within the trajectories of a dynamical system (by determining more and more the state of the other system)? * How to describe a system that can appear and disappear within the trajectories of another system? * How to describe a system that can replicate within the trajectories of another system? How does it relate to boundaries? <!-- These phenomena are individualized and maintain themselves under multiple interactions with their environment and therefore exhibit --> These phenomena are usually individualized and therefore exhibit a kind of boundary. This boundary is particularly interesting since it is dynamic, is maintained by the phenomena themselves and can be created as well as broken within a trajectory. What can you do with a solution? <!-- A solution to this problem would provide a formal understanding of glider-like phenomena and the way gliders are novel these glider-like phenomena. --> If we want to prove safety critical features about the interaction between living organisms and AI technology we need faithful formal models of them. Living organisms and technological artifacts like AI agents occur temporarily within our trajectory of the universe. Often they at least partially maintain their own existence (e.g.: computers have error correction, living organisms have a metabolism), can move, grow, appear (by construction or spontaneously), disappear (break, die), and replicate. Glider-like phenomena occur temporarily in trajectories of cellular automato or reaction diffusion systems. There are examples exhibiting each of the features of living organisms and technological artifacts mentioned above. Though, admittedly, not all at once as far as we know. In this sense glider-like phenomena are the closest known analogue to living organisms and technological artifacts that occur in formally well defined systems. However, while the systems they occur in are well defined the phenomena themselves are not formally understood. We hypothesize that a formal account of glider-like phenomena would provide a more faithful formal model of living organisms and technological artifacts than existing ones. It would then also provide a more appropriate and general setting for safety critical proofs about their interaction. <!-- A solution would allow us to prove theorems about systems (in a general sense) that occur temporarily within the trajectories of other systems and maintain their own existence during that time. If agents are systems every agent that occurs withing a larger dynamical system is a special case of such a system. The hypothesis is that this is a more realistic model of the way living organisms and technological artifacts (including AI systems) exist inside our universe. Under this hypothesis proofs about such systems will be relevant for AI safety. --> How does the naive solution fail? The naive solution in the case of the glider itself would be to try and factorize the Game of Life CA into two interacting systems (Moore machines). For this let $X$ be the state space and $h:X \to X$ the update function of the Game of Life CA. We then want to find two Moore machines $(E,A,P,\eta:E \times A \to E,\beta:E \to P)$ and $(V,P,A,\nu:P \times V \to V,\alpha:V \to A)$ such that wring them together forms a closed dynamical system that is isomorphic to the Game of Life CA. However, this is inadequate for capturing the glider for multiple reasons: * The factorization into two Moore machines should come into existence and disappear with the glider. * Even if we assume there is a glider, there is no function $f:X \to V$ mapping the state of the CA to the state of the glider and thus no (constant) factorization of the CA into two interacting systems. The reason for this is that two different states of the 'same' glider can occur in the same CA state and therefore we cannot assign a unique glider state to such CA states. An example of a CA state that contains two different states of the same glider is shown below. After seventeen timesteps the glider at the top left will turn into the glider at the bottome right. ![](https://docs.localcharts.org/uploads/44c2ea67-f3c9-4422-9b57-7886b89df49a.png) <!-- * don't have a unique * This is a due to the fact that gliders maintain their identity while moving through the grid of the CA. If $GL^0(p,d,c,W) \subseteq X$ are the states of the CA in which a glider is at position $p$ with direction $d$, and chirality $c$, then there is a set of states $GL^n(p,d,c) \subseteq X$ of states of the CA that contain a state of the same glider after $n$ steps. It can be shown that $GL^0(p,d,c) \cap GL^{17}(p,d,c) \neq \emptyset$ so that there are states of the CA in which there is a glider $g_1$ of type $(p,d,c)$ and a glider $g_2$ which is indistinguishable from the glider that $g_1$ will turn into seventeen timesteps later. So if there was a function $f_{(p,d,c)}:X \to {R,W}$ telling us the state of the glider at $(p,d,c)$ it would need to map any such CA state $x \in GL^0(p,d,c) \cap GL^{17}(p,d,c)$ $$ If we on the one hand, we want such a projection function to only depend on the configuration of the glider which means we only want it to depend on the 22 cells occupied by the glider. But then the same function cannot also tell us the state of that same glider after it moved So the function should can be multiple gliders in the same Game of Life trajectory that take on the exact same glider configuration in exactly the same place in the CA grid so a function that tells us the state of one glider will at some later point have to tell us the state of the other glider which isn't what we want. --> <!-- The main problem is that --> <!-- * two projection functions <!-- $\pi_V:X \to V$ and $\pi_E: X \to E$ --> <!-- mapping the state space $X$ of the cellular automaton to a state space $E$ of the environment and a state space $V$ of viscera / internal states of the system. In addition we would need to --> What is at least one promising solution direction? There are solutions in categorical systems theory for dynamically changing how multiple systems are wired up to form a combined system. This seems a promising approach for dealing with a system moving through another one. However, further research is necessary to also deal with the case where systems appear and disappear, grow, or replicate as part such a combination of systems.