A follow up on the Wolfram Summer School 2023 project: [WSS23] Efficient discovery of halting paths in aggregation system multiway graphs
Aggregation systems are cellular automata structures where cells are not removed (turned off) after aggregated. In our previous work, we have proposed a classification system for all the 255 totalistic rules called “k-Bit rule”, upon which we have proved some rules never halt, some always halt, some have a halting path. However, 24 of them remained without conclusions on their halting nature. In this follow up, we finally present results on these rules.

Code:

Base and helpers

Additional (new) show step methods
In[]:=
(*Translationsymmetrymap*)​​CellCanonicalize[state_]:=With[{m=Min/@Transpose[state]},#-m&/@state]
In[]:=
ShowSteps[cells_List,start_Integer,n_Integer]:=PlotCells[#,n,ImageSize->100,Mesh->True]&/@Table[Take[#,i],{i,start,Length[#]}]&@CellCanonicalize@cells
In[]:=
ShowStepsColor[cells_List,rule_Integer,start_Integer,n_Integer]:=ArrayPlot[#,Mesh->True,ColorRules->{0.5->Pink}]&@SparseArray[#,{n,n}]&@Join[Thread[#+2->1],Thread[NextAllowed[#,rule]+2->0.5]]&/@Table[Take[#,i],{i,start,Length[#]}]&@CellCanonicalize@cells
In[]:=
haltCells={{0,0},{1,1},{0,2},{0,1},{1,0},{1,2},{-1,1},{-1,2},{2,1},{2,0},{1,-1},{0,-1},{2,-1},{1,-2},{0,-2},{-1,-1},{-1,-2},{2,2},{1,3},{2,3},{3,2},{3,3},{2,4},{1,4},{3,1},{4,2},{4,3},{4,1},{5,2},{5,3},{4,4},{5,4},{5,1},{6,2},{6,1},{5,0},{6,0},{7,1},{7,2},{4,0},{5,-1},{6,-1},{4,-1},{5,-2},{6,-2},{7,-1},{7,-2},{4,-2},{5,-3},{4,-3},{3,-2},{3,-3},{4,-4},{5,-4},{2,-3},{1,-3},{2,-4},{1,-4}};
In[]:=
ShowStepsColor[haltCells,12,3,11]//ListAnimate[#,3]&
Out[]=
In[]:=
Row[ShowSteps[{{1,3},{2,4},{2,3},{2,2},{3,2},{3,3},{3,1},{4,2}},2],Spacer[1]]
Out[]=

Introduction

Please refer to the previous community post [WSS23] Efficient discovery of halting paths in aggregation system multiway graphs for detailed information on totalistic aggregation systems and our proposed classification system “k-Bit rule”.

Classification so far:

In the previous work we have outlined the following results about our groups of rules:
◼
  • 1-Bit: never halt (128 rules)
    • ◼
  • 2-Bit (64 rules)
    • ◼
  • bit 3 on: never halt (32 rules)
    • ◼
  • bit 3 off (32 rules)
    • ◼
  • bit 5 on: haltable
    (16 rules)
    • ◼
  • bit 6 off: haltable
    (16 rules total, 8 extra)
    • ◼
  • the rest - bits 3, 5 off and bit 6 on - UNKNOWN (8 rules)
    • ◼
  • 3-Bit (32 rules)
    • ◼
  • bit 4 on - UNKNOWN (16 rules)
    • ◼
  • bit 4 off: haltable (many states depending on initial conditions) (16 rules)
    • ◼
  • k>=4-bit: always halt (31 rules)
    • There are 8 rules in 2-Bit group and 16 rules in 3-Bit group that we did not know if always halt, can halt or never halt.
    Here we present our findings, through proofs and empirical examples, on the halting capabilities of these rules.

    New results:

    3-Bit rules with bit 4 set never halt (failed attempt, but leads to the 2 following lemmas)

    The proof did not work, but helped showing patterns that are allowed (and even required) for a halting state, and thus made easier for us to manually find one.
    Proof: we (try to) prove by contradiction by assuming we have a halting state, that is, a state where there are no eligible cells to insert.In this case, no cell with exactly 3 or 4 neighbors.
    Assume that we have a halting state. We are going to define a “walk” along its boundary. We pick the cell to the rightest of the top row of the boundary. Like the gray cell below:​
    ​Apart from the gray corner cell, where we currently are, in general we do not know which cells are active. But we know that every active cell requires at least 3 active neighbors. Breaking up the possibilities:
    ◼
  • If 3 is on and 4 is on, our right has 3 or 4 neighbors, then is eligible: contradiction
    • ◼
  • If 3 is on, 4 is off, and 5 is on, our right has 3 neighbors, then is eligible: contradiction
    • ◼
  • Otherwise, we require 1 to be on, and we are left with 2 possibilities:
    • ◼
  • Case (1)
    (gotta put x’es to left and up of left top block)
    • ◼
  • (2)
    • Let’s develop (2): we move to the bottom row and to the rightmost cell we have there, there are 3 possible situations:
    ◼
  • when there are no other cell to the right of (2):
    ​​We have only 2 possible ways to fill the marked cells:
    • ◼
  • => in this case we move to bottom row and rightmost cell and check again - develop (2)
    • ◼
  • => case 2-a
    • ◼
  • when there are more cells, but cell before rightmost is off
    . Then our right has 3 neighbors, then is eligible. Contradiction
    • ◼
  • when there are more cells, but cell before rightmost is on
    . We go back to the beginning with this configuration.
    • This process is finite, because otherwise we would be moving in a down right direction infinitely, contradicting our hypothesis that we are walking on a finite boundary. So we are going to end in one of these two states:
    ​
    (1)
    ; (2-a)
    Now we (try to) show these local states are impossible to reach with 3-Bit rule
    Case (2-a)
    Expanding it:
    The cells with number 3 have exactly 3 neighbors cells. So each of them require the other to be active before, in order for it to be aggregated, meaning they must have existed as initial state. However the only cell that could be aggregated in a first step of a system with these cells as initial states would be the one in the middle, with the x. Contradiction
    Case (1)
    we realize is actually possible to form a halting state....
    We can have 3 situations:
    ​

    3-Bit rules with bit 4 set, bit 5 unset: can halt

    Based on the boundary pattern found in our failed attempt, we have “manually” investigated and were able to construct a halting configuration (if bit 5 is unset)

    3-Bit rules with bits 4, 5 set never halt

    2-Bit rules with bit 3 unset, bit 6 set, bit 4 unset: can halt

    This will include new rules from our set of unresolved rules: 34, 98, 162, 226
    A bigger example:

    2-Bit rules with bit 3 unset, bit 6 set, bit 4 set: can halt

    Note that having bits 7 and 8 can add the 2 blocks on the inside to the structure, but no more than that - it will still halt.

    Discussion and more findings:

    3-Bit group:

    The “3-Bit rules with bits 4, 5 set never halt” proof guarantee that half the 3-Bit states with previously unknown halting behaviour never halt:
    And the other half are all rules with bit 4 set (and 5 unset). This is enough to reach the following halting state (with up to 3 extra steps to add the cells inside the structure, depending on the rule):
    Completing our 3-Bit group halting classification

    2-Bit group:

    The 8 rules that had halting nature unsolved were:
    These are the rules that escape the subcase analysis we had so far, that is: 2-Bit rules that have: bit 3 unset, bit 5 unset, bit 6 set.
    After our first new 2-Bit rule result, we know that half of these (the ones with bit 4 unset) can halt
    The second 2-Bit rule show the remaining ones (that have bit 4 set) can also halt.
    ​This completes our 2-Bit group halting classification.

    Conclusion:

    We have completed the classification of halting based on the “k-Bit rule” system:
    ◼
  • 1-Bit: never halt
    • ◼
  • 2-Bit
    • ◼
  • bit 3 on: never halts
    • ◼
  • bit 3 off
    • ◼
  • 3-Bit
    • ◼
  • bit 4 on (NEW, previously unknown)
    • ◼
  • bit 5 on: never halts
    • ◼
  • bit 4 off: haltable (many rules depending on initial conditions)
    • ◼
  • k>=4-bit: always halt
    • Even though we have advanced considerably our understanding on halting capabilities, there still is some ground to cover and study, mainly:
    ◼
  • 3-Bit sensitivity to initial minimal configuration.
    • ◼
  • Considerations on arbitrary initial configuration (not minimal) impact on haltability
    • ◼
  • Conditions where a haltable path determines that *there is always a halting path* for the given rule, independent of previous choices.

    • Keywords

    ◼
  • Aggregation systems
    • ◼
  • Discrete Mathematics

    • References

    ◼
  • Wolfram, S. (2002). A new kind of science.
    • ◼
  • [WSS23] Efficient discovery of halting paths in aggregation system multiway graphs

    • CITE THIS NOTEBOOK

    Uncovering new Halting Paths in Aggregation Systems​
    by Pietro Pepe​
    Wolfram Community, STAFF PICKS, June 28, 2024
    ​https://community.wolfram.com/groups/-/m/t/3201811