This project investigates totalistic aggregation systems, which exhibit cellular automata behavior with an unique twist. The focus is on totalistic rules that determine cell eligibility based on the total number of active neighboring cells. By developing a simulation software using Lua and the LÖVE framework, the project enables the exploration of different rule sets and initial conditions. Multiway graphs are used to visualize the system’s behavior, and the concept of translation, rotation and reflection canonicalization simplifies the analysis of equivalent states. The project also proposes a new classification system - k-Bit rules-, systematically identifies halting states based on rules and minimal initial conditions, and uncovers insights into system growth and eventual halting. Overall, this project provides valuable insights into totalistic aggregation systems and their dynamics.

Code:


Introduction

Aggregation systems are like cellular automata with a twist: once cells are set - i.e. aggregated - they remain set. The deterministic nature of standard CA is here replaced by a (standardly random) choice of what cell to add to the system, from a list of eligible cells according to the system rule.We focus our study on totalistic rules - rules that inform if a cell is eligible based on the total number of neighbor cells active, instead of specific configurations around it.Neighborhood can be von Neumann
(
4
2
rules
) or Moore
(
8
2
rules
), even though Moore is our main focus, and all graphs and simulations will be based on it, unless explicitly mentioned otherwise.Here is an example of a Totalistic Moore aggregation system evolution, with rule 18 (10010). This system expands to cells with 2 or 5 active neighbors (the positions of bits set in the decimal representation)​
​​
,
,
,
,
,
,
Depending on the cells selected, we can get to a state where no new cell can be added, because none of them has an accepted quantity of active neighbor cells. We call this halting and is exactly what happens in the example above when we reach
​Since we have, potentially, many ways to expand the system, is natural to ponder how and when the aggregation choices affect the future of the system:
◼
  • When is possible to make the system halt? When can it grow “forever”?
    • ◼
  • When does a system always halt, regardless of path/choices? When does it never halt?
    • ◼
  • “Haltable” systems always halt, that is, is there a halting path from any given state?
    • Our goal is to explore visualization and computation of halting states when starting from minimal initial states.

    Simulation Software

    We implement a simulation software to explore any set of rules, initial conditions, with both manual and random selection of aggregated cells.
    The simulation was developed with the framework LÖVE, using the Lua programming language.
    Executable file and source code is available at: https://github.com/LexLoki/WSS23_AggSystems​
    ​This notebook has a desktop version that has an integration with the simulator: clicking a node in a graph launches this external simulator with that specific node state set. For it to work, the executable folder of the simulator needs to be in the same directory as the notebook file.
    In this software, aggregated cells are white, and eligible cells are pink. Several halting states were found manually with the aid of the software:
    Out[]=
    Andalsosomebigfancyone,fromrule4:​​
    However interesting, this simulations are done following a single path at a time, and are then far from an fully broad approach to understand and visualize these aggregation systems. So let’s get started with using Mathematica.

    Multiway graphs

    Since many choices can be made, is natural to consider the multiway graph representation of these systems. These graph represent all possible states a system can assume as vertices, and viable transitions between two states as edges.
    For instance, if we consider rule 255, that accepts all cells, starting with a single cell
    :
    ◼
  • 1 step:
    • In[]:=
    TotalisticGraph[1,255,{{0,0}},True,True,"SpringElectricalEmbedding"]
    Out[]=
    ◼
  • 2 steps:
    • In[]:=
    TotalisticGraph[2,255,{{0,0}},True,True,"SpringElectricalEmbedding"]
    Out[]=
    Showing these systems can grow pretty fast, although this highly varies based on the rule.See for instance the multiway graphs of rule 2, that accepts only cells with 2 neighbors, on
    , for 1, 2, and 3 steps:
    In[]:=
    Row[TotalisticGraph[#,2,{{0,0},{1,1}},True,True,"SpringElectricalEmbedding"]&/@Range[3],Spacer[10]]
    Out[]=
    Unfortunately, rendering the graph takes a substantial amount of time, specially when generating the cells plot for each vertex:
    Rule 2 execution times demonstrate that:
    In[]:=
    ParallelTable[TotalisticGraph[n,2,{{0,0},{1,1}},False,True]//VertexCount,{n,Range@12}]
    Out[]=
    {3,11,29,69,157,369,861,2017,4867,12039,30329,77021}
    (*steps=Range@12;​​MeasureTimes[plotCells_:False,moore_:True]:=ParallelTable[TotalisticGraph[n,2,{{0,0},{1,1}},plotCells,moore]//Timing//First,{n,steps}]​​graphTimes=MeasureTimes[False,True];​​graphPlotTimes=MeasureTimes[True,True];​​Grid[Transpose[{Prepend[steps,"Steps"],Prepend[graphTimes,"Graph(seconds)"],Prepend[graphPlotTimes,"Graph+cells(seconds)"]}]//Transpose,Frame->All]*)
    This multiway graph seems to be growing even slower than the previous (rule 2). Is not hard to see why: this requires more neighbors active, so is natural that less cells are eligible to be added to the system.
    Even though the growth is lower, computations show it also “explodes”, making it hard to study many interactions, specially when we analyze other rules.
    ◼
  • So far we are not able to find any halting state, represented by a leaf in the multiway graph, and is hard to inspect visually as we go further.
    • ◼
  • One should note that these graphs has many states that are equivalent under translations, rotations, and reflections, and so could be collapsed/merged in single states.

    • Introducing translation canonicalization

    We want to apply some transformation on the set of cells that represent a state, in a way that two different sets that are equivalent under translation, i.e., by a offset, map to the same value. One simple way to do this is to translate our state to the origin. More specifically: push the minimum boundary of the grid to the origin (top left corner). This is what CellCanonicalize does.
    This allows more merges in the multiway graphs. For instance:
    We can see how that allows us to go deeper in reading the graph:
    The cost of performing the canonicalization is proportional to the quantity of cells of a given state. This cost is overly compensated by the amount of merges, thus reduced branching.
    Rule 2 execution times demonstrate that:
    But we can do better, since we still got to consider degrees of symmetry.

    Introducing rotational and reflectional canonicalization

    Same idea applies. The approach is to calculate, for a given state, all its 8 combinations of orthogonal rotation and reflection, and map it to the first one, given some ordering algorithm. This is achievable in Mathematica using the resource function ArrayRotation, and relying on Order, through Sort. This is what CellCanonicalizeRotation does (it also does translation).
    This greatly reduces the size of the graph in most cases, specially with symmetric and small initial conditions. Is easy to see why:
    One extra step comparing both canons:
    Rule 2 execution times are even more impressing:
    Allowing us to go even deeper.
    See some other rules:
    For visual exploration this is great, and with the added performance upgrade we can probably start to try to look for halting states.

    Halting states computation

    Halting states can be found by looking on the multiway system graphs, like in the one for rule 18:
    Although this state might have been easy to find, depending on the rule, and the initial state, they can be really hard (too deep) to find, sometimes even impossible. One challenge here is to be able to tell when we are not finding halting because it requires too many iterations, or because it indeed does not halt.
    Moreover, an automated method to find halting states is what we look to do. It can be implemented by simply using these graphs. However, we can make it more efficient without it, since the graph, with or without the grid plots, also maps the edges. Since we are only interested about finding halts, we just need to keep the vertices, thus we can replace NestedGraph with a appropriate implementation using NestWhile and some modifications.
    Trying to find same halting - rule 18 with our special method is quite simple, and of course, runs faster:
    And what about a harder to find halt? Rule 2 is one example where we cannot seem to find halting at depth 8:
    And trying more levels than that is unfeasible. We can find it though:
    Now we are well equipped to study systematically the set of possible rules, what will be done in theory and practice (simulation) through following sections.

    Bit groups and general halting proofs

    As we know, the system rules are numbers whose binary digits represent eligibility of a cell based on the quantity of its active neighbors. The less significant bit means 1 neighbor, the most significant bit means 8 neighbors. From here on, when we say Bit k, we refer to the bit of k neighbor acceptance, or then a shorthand for the acceptance.
    We adopt also a distinct term: “k-Bit rule”, used to arrange our set of 255 possible rules (moore/8 connectivity) in a relevant way for our analysis, as explained below.

    Remarks:

    ◼
  • See for instance how the multiway graphs for rule 2 (binary 10) is contained in the one for rule 6 (binary 11):
    • ◼
  • The lower rule in a k-Bit group is contained by all other rules in the same group. It should then be the easiest to compute.
    • ◼
  • Analogously, the higher rule (in a same group) contains all others, and then should be harder to compute.

    • 4 connectivity halting lemmas:

    4 connectivity was not the focus of this study, and the following simple proofs make it clear why: they are far too simple in terms of determining halting. (note that for 4 connectivity, there are only 16 rules, and 4 bit groups).

    8 connectivity halting lemmas:

    We can use similar arguments from 4 connectivity to 8, but the conclusion results only apply to a small subset of the rules

    Now we are left with the set of 2-Bit and 3-Bit rules, 98 in total. We computationally analyze them in the following section. However there is one interesting result:

    This reduces our halting study set to 64 rules.

    Bit group halt-finding analysis and results

    PlotBinaryGroupsHalt gives us the list of halting states found for given rule, initial cells and maximum depth.
    A k-Bit rule requires a minimum of k initial cells in order to not halt instantly (trivially). MinimalInitials provides the set of minimal initial cells for a given rule.

    1-Bit

    As we already know, we cannot halt with 1-Bit rules:

    2-Bit

    3-Bit

    (reduction explained in the following section)

    Concluding remarks

    In this project, we explored totalistic aggregation systems with minimal initial conditions, which proved to be a challenging yet intriguing subset of aggregation systems. Our efforts resulted in the development of a diverse collection of visual computations for these systems, offering valuable tools for further exploration and optimization. However, due to the combinatorial nature of the problems involved, significant optimizations beyond specific purposes or systems with particular properties are unlikely.
    Nonetheless, we made significant contributions to the understanding of these systems. By proposing a relevant classification of rules, we focused on a subset of 96 rules and demonstrated that 32 of them never halt, further narrowing down the “gray area for conclusions” to a group of 64 rules. Among these, 24 rules (8 2-Bit and 16 3-Bit) have yet to reveal a halting state, leaving the question open as to whether they are haltable or not. The remaining 40 rules were shown to halt, but we have not determined which of their halting configurations represent possibilities in higher branching steps of their multiway graphs.
    Looking ahead, there are several promising avenues for future research:
    ◼
  • The 16 3-Bit rules that resisted halting have a shared property that suggests they may be impossible to halt, similar to the proven non-halting nature of the 2-Bit subset. Constructing a definitive proof for this observation would be a significant step forward.
    • ◼
  • Further in-depth exploration of 2-Bit and 3-Bit rules, specially 3-Bit sensitivity to some initial configurations.
    • ◼
  • We considered an alternative halt-finding method, involving pruning subgraphs of the multiway graph that are deemed unlikely to halt soon using greedy and heuristic criteria. Although not developed in this study, it presents an intriguing approach for future investigation.
    • ◼
  • The simulator offers the capability to simulate random paths, opening up possibilities for individual “smart” path finding queries to explore and discover halting states. Developing cell selection policies for these paths could prove fruitful, providing an alternative to the classical broad-breadth search on multiway graphs.

    • Keywords

    ◼
  • Aggregation Systems
    • ◼
  • Multiway Graphs
    • ◼
  • Discrete Mathematics

    • Acknowledgment

    I would like to thank all Wolfram Staff involved in making Wolfram Summer School 2023, and for giving me this opportunity to challenge myself in this exciting environment and assisting me along the way.
    Special thanks to my mentor Robert Nachbar, for all the assistance he provided me and other students, with his keen eye, technical knowledge and communication skill.
    To Eric Parfitt, that helped me save (or avoid spending) countless hours with some technical issues. All in a glance of an eye.
    And last but not least, to Stephen Wolfram, that introduced me to this project and made sure I would have a great project on my hand, despite of how picky I am.

    References

    ◼
  • Wolfram, S. (2002). A new kind of science.
    • ◼
  • [WSS19] Aggregation Systems: A stochastic approach to CA by Kabir Khanna
    • ◼
  • [WSS21] Study aggregation systems with multiway graphs

    • CITE THIS NOTEBOOK

    Efficient discovery of halting paths in aggregation system multiway graphs​
    by Pietro Pepe​
    Wolfram Community, STAFF PICKS, July 12, 2023
    ​https://community.wolfram.com/groups/-/m/t/2959726