The topic is interesting, I would be interested to see what is possible, but there are also some interesting unanswered questions and I'm also a bit skeptical on some points.
R2INT wrote: April 3rd, 2025, 8:48 pm
[...] I have plans to make a notation for Range-2 INT rules. [...]
One open question here is, what is/are the intended purpose(s) of the notation? A notation can have different purposes / can be useful in several different ways. What would make sense depends on the purpose(s).
Here is some relevant counting:
- Forgetting about symmetries, there are 2^24 two-state 5-by-5 neighbourhood configurations omitting the middle cell's state (to specify any one of them, one needs to specify states of the 24 cells marked as LifeHistory state 2 below):
Code:
Select all
x = 5, y = 5, rule = LifeHistory
5B$5B$2BF2B$5B$5B!
#C [[ GRID ]]
- Out of those 2^24 neighbourhood configurations omitting the middle cell's state, 2^6 remain unchanged when rotated 90 degrees clockwise, and 2^6 remain unchanged when rotated 90 degrees counterclockwise (it suffices to specify states of the six cells marked as LifeHistory state 2 below):
Code:
Select all
x = 7, y = 7, rule = LifeHistory
7F$F3B2.F$F3B2.F$F2.F2.F$F5.F$F5.F$7F!
#C [[ GRID ]]
- 2^12 neighbourhood configurations omitting the middle cell's state remain unchanged when rotated 180 degrees:
Code:
Select all
x = 7, y = 7, rule = LifeHistory
7F$F5BF$F5BF$F2BF2.F$F5.F$F5.F$7F!
#C [[ GRID ]]
- 2^14 neighbourhood configurations omitting the middle cell's state remain unchanged when mirrored vertically:
Code:
Select all
x = 7, y = 7, rule = LifeHistory
7F$F5BF$F5BF$F2BF2BF$F5.F$F5.F$7F!
#C [[ GRID ]]
and of course the count is the same for horizontal mirroring.
- 2^14 neighbourhood configurations omitting the middle cell's state remain unchanged when mirrored through the main diagonal:
Code:
Select all
x = 7, y = 7, rule = LifeHistory
7F$F5BF$F.4BF$F2.F2BF$F3.2BF$F4.BF$7F!
#C [[ GRID ]]
and of course the count is the same for mirroring through the other diagonal.
- It follows that there are precisely
Code: Select all
2105872 = 1/8 (2^24 + 2^6 + 2^6 + 2^12 + 2^14 + 2^14 + 2^14 + 2^14)
cell conditions, omitting the cell's own state. In other words, there are 2105872 equivalence classes of neighbourhood configurations omitting the middle cell's state (up to rotations and reflections, because the discussion is about isotropic cellular automata).
Is the above counting correct? (which is b.t.w. a question to everyone interested in the CA family "two-state isotropic cellular automata with range-2 Moore neighbourhood")
Assuming it is correct, one would need at least twice as many bits of information to be able to pick an arbitrary CA from this family. (That doesn't mean one would always need that many bits. One might choose to simplify representation for some subspaces/subsets.) Specifically, one would need 2105872 bits to specify which
cell conditions omitting the cell's own state are included in the set of
birth conditions (that is, to specify what are the
birth rules and what are the
nonbirth rules), and one would need 2105872 more bits to specify which
cell conditions omitting the cell's own state are included in the set of survival conditions (that is, to specify what are the
survival rules and what are the
death rules).
That means roughly half a megabyte (526468 bytes) assuming naive uncompressed encoding, and slightly over 700000 characters assuming
base-64 encoding.
Of course any human-readable notation is going to be much longer.
Speaking here for myself, it seems like a notation with multiple assigned letters needed to specify just one cell condition is going to be a non-starter.
I don't see how it would help with intuitive understanding, considering it's reasonable to expect hundreds of thousands (if not millions) of characters in many cases. In terms of being unreadable, I think that's going to overshadow anything that already exists, making RuleLoader ruletrees and weighted neighbourhood based CA definitions look very intuitive and human-readable in comparison.
I don't see how it would help with "bookmarking", it is probably going to be way way too long to serve as a bookmark. It would be simpler to assign autogenerated sequential labels/names and maintain a table of investigated CA.
As far as enforcing self-consistency goes, it would suffice to have roughly half a megabyte (526468 bytes) of raw data, possibly compressed and/or encoded as base64 for storage/transmission.
confocaloid wrote: February 5th, 2025, 5:46 am
Yoel wrote: February 5th, 2025, 3:57 am
confocaloid wrote: February 4th, 2025, 11:07 pm
Probably that would run again into the question "what is the purpose of the notation?" [...]
What I have suggested is still readable for a user who has some experience. [...]
A notation can have different purposes / can be useful in several different ways.
- (Enforcing self-consistency) For "restricted" families of cellular automata (such as your cyclical CA, or self-complementary two-state CA), it can be helpful to have a dedicated notation, because that allows the user of the notation to "forget" the exact constraints/restrictions on the ruleset. (The script used to parse the notation will correctly generate a consistent ruleset satisfying the restrictions.) A notation can be useful when it correctly captures inherent symmetries or repetition.
(By "restricted" I mean here any restrictions of the following general form:
Code: Select all
"either ALL of these birth/survival/mutation/... rules must be in the ruleset,
or NEITHER of these birth/survival/mutation/... rules can be in the ruleset"
For self-complementary two-state CA, those restrictions are that every birth rule implies the corresponding death rule and vice versa, and every survival rule implies the corresponding "abstain" (non-birth) rule and vice versa.)
- (Intuitive understanding) Another way how a notation can be useful, if it helps to "read and understand" the definition. This doesn't directly follow from ensuring self-consistency. A notation can guarantee self-consistency and still be obscure. For comparison:
- Hensel notation can be learned, but it takes time and efforts (and I still can't remember the exact meanings of 3q/3n/3r).
- Weighted neighbourhoods can lead to long rulestrings, but they can have advantages both in terms of guaranteeing consistency ("R1,NW151505151" captures restrictions that would otherwise be hard to describe with Hensel notation) and in terms of human-readability (fewer arbitrarily assigned letters that would require a table to interpret).
- (Bookmarking) Another way how a notation might be helpful, if it makes it possible to "save" or "share" interesting rulesets quickly (by copying a single string, rather than an entire file). This doesn't have to be human-readable, and doesn't have to guarantee self-consistency - it's simply sort of a way to "bookmark" an interesting ruleset.
- ...
[...]