The following is a hypergraph rewriting ruleset to emulate Conway’s Game of Life for the case of two neighbors. I made it to explore the questions of communication and information-driven evolution of space. A few interesting “physics-like” properties emerged in the process – like the principle of locality and time dilation.
This is the second step of my quest to play the Game of Life on a hypergraph. In my previous post, I talked about unfolding a 2D grid.

Main

TLDR on the Game of Life

Conway’s Game of Life is a cellular automaton designed by British mathematician John Horton Conway in 1970. The game is played out on a 2D grid, with each cell existing in one of two states: live or empty (dead).
​
In my simplified version, every cell’s future state is dictated by its current state and the states of its two neighbors, following these rules:
1. Any cell with zero live neighbors becomes empty.
2. Any cell with exactly one live neighbor becomes a live cell.
3. Any cell with two live neighbors becomes empty.
Our universe will have four cells, one of which is alive. With this ruleset, after the first update, its neighboring cells will become alive; updates thereafter, will not change the state of the nodes: all of them will remain empty.

Deconstructing GoL’s “update turn”

The cellular automaton of Game of Life does not care how the cells get updated. From its universe’s standpoint, one tick of time has occurred and updated “just” its state.
​
To devise the updating procedure, let’s see how we would perform it by hand:
1. For every cell,
- note the number of its live neighbors,
- note its future state according to that number and current state.
2. For every cell,
- update it to its future state.
Unfortunately, that introduced sequencing: if we update a cell before figuring out its future state, that’s a mistake; likewise, if we are calculating a future state when a neighbor has already updated – that’s a mistake.
So, a restriction must be enforced: (R1) A cell may update only after it has informed the neighbors about its state AND received information about their states.

Communication framework

Game of Life model

◼
  • we use nodes of a hypergraph as “places” for cells
    • ◼
  • cells are presented by the Alive/Empty markers (self-loops over the node)
    • ◼
  • “neighbors” are the cells, whose nodes are connected with an edge
    • ◼
  • the edge can be marked as either “ready”, “sent” or “red” (using distinct hyperedges)
    • ◼
  • a cell is connected to N neighbors – for this model: two
    • ◼
  • any other information (tally, the “ready to update” flag, etc) is also stored as markers

    • Algorithm for a localized update turn

    1. A cell communicates its state to a neighbor, only when connected with the “ready” edge.
    - After this, the edge is changed to “sent”.
    - It separately keeps a tally of the number of times it communicated.
    2. A cell is ready to update when it has all of its N incoming edges marked as “sent” (“it knows the neighbors’ states”) and its tally is equal to N (“it has updated the neighbors”).
    - It changes its state according to the GoL rules.
    - All incoming edges are marked as “red”.
    - The cell is marked as “updated”.
    3. When a cell has all of its outgoing edges marked as “red” (“if all my neighbors have updated”), it changes them to “ready”. This indicates a restart of the update cycle for this cell.
    Please note, that in step 2 we used a tally for “the cell has updated its neighbors”. We cannot just count outgoing “sent” edges, as they could be swapped for “red” during 2-b. And having “red” is important, because that’s the signal to neighbors that they can proceed with its update (their messages were red).

    Inventing how to count

    For a cell to update, it needs to know the number of alive neighbors. When communication happens, how do we store and process it?
    ​
    My solution is to make a mark (self-loop) for every alive and empty cell – and then refer to it in an update rule. Two empty marks mean 0, one alive and one empty – 1, two alive – 2. The reason for noting both is that the rules are reductive, and the shortest rule supersedes the longer one:
    rule {x,x} will affect both {{x,x}} and {{x,x}, {x,x}}
    rule {{x,x}, {x,x}} will never execute
    This means: we cannot use omission in rules and need an explicit marker to indicate lack of something.
    You need six rules just for substitutes: 3 per the number of alive neighbors for both ALIVE/EMPTY states. We need to explicitly mention the current state of the rules could remove that.
    I used an alternative approach when I only had three rules that cared only about the number – and were severing the old cell (ALIVE/EMPTY marker) and creating a new one in its stead. The severed cells were marked for termination and had a separate rule taking care of them – which turned out to be five rules and not that much of an efficiency win. But this was an interesting exercise to imagine how an OR statement would look as a hypergraph rewriting rule.

    Notes and Observations

    Designing the hypergraph

    It is crucial to have an unambiguous topology to prevent rules misapplication.
    There are three structures that we can utilize for that:
    1. Hyper-self-loops (or “markers”): {x,x…,x} – used to identify a single node or store information that pertains uniquely to it (like, ALIVE or EMPTY).
    - Interestingly, a basic self-loop {x,x} is a bad marker, as it can be mistaken for an edge {x,y}.
    2. Hyper-edges: {x,…,y}. For example, when a cell communicates its state to a neighbor, the edge between them could be updated to encode the flag “message sent”.
    3. Edge composition: {x,a},{x,b},{x,c} (“the node with at least three outgoing edges”). I personally do not like this one, as it modifies the topology and makes it harder to read.
    Unambiguous topology might lead to distinct zones, to which only certain rules apply. I like a metaphor of “higher planes of existence” for them: distinct pockets of the universe with their unique physics.
    For this model, I had a “spatial” and a “cellular” planes. The former was modeling the square grid and maintaining communications, while the latter stored such abstractions as the cell (alive or empty), counters, and sequencing logic for the update turn.

    Physics-like properties

    - A model for particles: this communication framework facilitates the exchange of information between entities. That might be an object with mass, pulling something. Or a lit thing, illuminating the surroundings.
    - Movement: with “higher planes of existence”, movement becomes as simple, as a retying a balloon to different intersections on a mesh grid. It’s almost as if we encapsulate physical properties into an object and then store its position within – the position being the edge connecting the object and its coordinates on the “spatial plane”
    - Relativistic time dilation: if we adjust our setup to allow the cells to have a variable number of neighbors, then an “update turn” will take longer in the areas where that number is bigger, in hypergraph rewritings per update turn. From the perspective of cells, all of them update within the same turn – but an external observer will see that the more neighbors you have, the longer you need to wait for all of them to communicate.
    - That agrees with the suggestion that energy is the amount of activity on the hypergraph. And energy curves the spacetime.
    - Is time dilation a consequence of discrete time? Any observer within the universe could not notice discretization, as their computation would be bound to it.
    - Other properties of the communication framework:
    - Principle of Locality: an object is directly influenced only by its immediate surroundings.
    - Causal Invariance: the Principle of Locality allows high parallelization – that, in turn, will result in branching. But the results converge if we take “update turn” as our frame of reference.
    - Speed of Light: we specifically restart the flow of information such, that it cannot move faster than one spatial edge (“between neighbors”) per update cycle.
    - Arrow of Time: for our universe, the update turn is the quantum of time.

    “Universe Programming” Advice

    Aliasing and readability

    That goes both for rules and for displaying the hypergraph.

    Debugging

    There are ways to display step-by-step substitutes – WolframModel[“StatesList”] – but it has the drawback of not highlighting the changes.
    ​
    My advice is to parse the output themselves, highlighting what rule was applied, which edges were removed, which added – plus some additional, universe-dependent information (on the illustration below, the “alive neighbors” counters).
    Also, it doesn’t look like Wolfram Language supports the trailing comma, so watch out for that.
    It is generally a good idea to output the substitute rules (as graphs or as text) to visually inspect that they were imputed correctly.

    Code

    Aliases for Hypergraph Structures

    Human-readable Output

    Fold back the MarkerNames (self - loops)
    Should produce something like that : EMPTY[x_]  StringForm[“EMPTY(``)”, x]

    Rules for the Universe

    Bigger Circle

    Graphs

    CITE THIS NOTEBOOK

    "How Do Particles Talk?" – a communication framework​
    by Myk Konovalow​
    Wolfram Community, STAFF PICKS, December 8, 2023
    ​https://community.wolfram.com/groups/-/m/t/3080342