A Survey of Small Rulespaces

[H. H. P. M. P. Cole]

I have been pondering about the question: what rulespaces are small enough such that every rule in it can be explored systematically in a reasonable amount of time, and if so, what objects can they contain? This question is ill-defined (depending on what 'systematic' and 'reasonable' means), but I set the hard limit for a 'small' rulespace to be less than 2^10, or 1024 rules. In this essay I will only focus on 2-state rules.

First, some definitions:

[...]

Many cellular automata can be expressed as a set of tuples (a,b,c) where a is the state of the central cell, b is the configuration of cells in its neighbourhood (under some equivalence class), and c is the final state of the central cell, under which there is an unique (a,b,c) for all a, b.

In the three types of cellular automata described below, permutations of the elements in b are regarded as equivalent (i.e., b is treated as a multiset of cellstates).

In an anti-totalistic cellular automaton, only the multiset of the states of cells in b determine the final state of the central cell (i.e. the central cell is not considered).
In a pure-totalistic cellular automaton, only the multiset of the states of cells in a∪b determine the final state of the central cell (i.e. the central cell is considered as an element of b and not as a separate entity).
In a semi-totalistic cellular automaton, the tuple (a,b) determines the final state of the central cell (i.e. the central cell is considered separately from b).

Anti-totalistic cellular automata are a subset of semi-totalistic cellular automata, and pure-totalistic rules are a subset of semi-totalistic cellular automata.

The number of such 2-state cellular automata where the neighbourhood of a cell has n neighbours (for some natural number n) have simple formulae: they are:

Code: Select all

Anti-totalistic: 2^(n+1)
Pure-totalistic: 2^(n+2)
Semi-totalistic: 2^(2n+2)

Hence anti-totalistic rules in anti-totalistic 'small' rulespaces must contain less than or equal to 10 neighbours,
pure-totalistic rules in pure-totalistic 'small' rulespaces must contain less than or equal to 9 neighbours, and
semi-totalistic rules in semi-totalistic 'small' rulespaces must contain less than or equal to 4 neighbours.

Allowed neighbourhoods

A neighbourhood is allowed in this survey when the union of all cells in the neighbourhood must have the same symmetry as one cell of the grid the neighbourhood is defined in, i.e. it is 'maximally symmetric'. Hence a maximally symmetric neighbourhood in the 1D grid must be invariant under reflection, a maximally symmetric neighbourhood in the 2D square grid must be invariant under the dihedral group of order 8, etc.

Semi-totalistic 'small' rulespaces with less than or equal to 4 neighbours

These rulespaces contain anti- and pure-totalistic rulespaces with the same neighbourhood, hence I will cover this set of rulespaces first.

The maximally symmetric neighbourhoods with less than or equal to 4 neighbours (up to any linear transformation), (please let me know if I missed anything out) are:
- 1D range-1, 2 neighbours (rulespace size: 2^6)
- 2D tripod (in the triangular grid), 3 neighbours (rulespace size: 2^8)
- 2D von Neumann, 4 neighbours (rulespace size: 2^10)
- and an infinite family of 4-neighbour 1D neighbourhoods, which consist of neighbourhoods where two neighbours are at distance a from the central cell, and two other neighbours are at distance b from the central cell, where a and b are coprime and 0 <= a <= b. (rulespace size: 2^10)

Since the first three rulespaces do not support spaceships (as B1 is required for any pattern to escape its bounding dimensions), then we are left with the last case. To my knowledge, it seems that the cases where (a,b) = (1,2) and (a,b) = (1,3) are the only cases where some rule in their corresponding rulespaces allow unreduced-speed c/1o spaceships in rules in these rulespaces containing B2 (birth on 2 neighbours) as a condition.

(EDIT: proof (please let me know if this is rigorous enough): to allow a unreduced-speed c/1o spaceship we need to have another value c, where c-a and b-c are in the set {0,a,b} (this means that the cells with coordinates a and c can form the frontend of the ship). Since both cannot equal b, one either has to let one of c-a or b-c equal a and the other equal 0 (which results in b = 2a) or to let both equal a (which results in b = 3a).)

This post of mine describes the set of B2 rules in the neighbourhood where (a,b) = (1,2) which allow still-lifes. When (a,b) = (1,3) this is a lot simpler:
- B2 rules where the minimum survival condition is S0 always have at least one SL: namely the dot.
- B2 rules where the minimum survival condition is S1 always have at least one SL: namely o2bo!
- B2/S2 using this neighbourhood does not have SLs. This is because the left terminus of such a hypothetical SL would be 2obo... and for the second cell to have S2 the cell on the right of this should be alive, hence the left terminus must have the form of 2ob2o!. However, the single dead cell two cells to the right of the leftmost cell will be born. To fix this, the next cell should be alive, but the fifth leftmost cell will die because of overpopulation. B2/S24 (and by extension B2/S234) using this neighbourhood does have at least one SL, however:

Code: Select all

x = 9, y = 1, rule = R3,C2,S2,4,B2,NW0000000000000000000001010101000000000000000000000
2ob3ob2o!

I do not know whether the rulespace from B23/S2 to B23/S234 using this neighbourhood has SLs.
- B2 rules where the minimum survival condition is S3 or larger will not have SLs. This is because a cell needs to have other alive cells on both sides of the cell, and a pattern where all cells have this property is not finite.

An example unreduced-speed c/1o ship in both rulespaces:

Code: Select all

x = 4, y = 1, rule = R2,C2,S2,B2-3,NW0000000000110110000000000
ob3o!

Code: Select all

x = 7, y = 1, rule = R3,C2,S,B2,NW0000000000000000000001010101000000000000000000000
o3bobo!

Prior art:

viewtopic.php?f=11&t=5712&p=179907#p179907 (section 3)
viewtopic.php?f=11&t=5497&p=195354#p195354

Diversion: Maximally symmetric neighbourhoods with less than or equal to 10 neighbours

There are far too many neighbourhoods of this type to enumerate, especially when one considers triangular and hexagonal honeycomb-based neighbourhoods (not to mention other nonhypercubic honeycombs in higher dimensions). Here is what I think to be the complete list for hypercubic honeycombs (the linear algebra term 'rank' here is used to show how many free variables there are when defining neighbourhoods in infinite families):

1D grid
- 1D range-1
- 1D 4-neighbour (infinite rank-2 family)
- 1D 6-neighbour (infinite rank-3 family)
- 1D 8-neighbour (infinite rank-4 family)
- 1D 10-neighbour (infinite rank-5 family)

2D square grid
- 2D range-1 von Neumann
- 2D Knight (infinite rank-2 family)
- 2D Far Corners/Edges (infinite rank-2 family)
- 2D 8-neighbour Cross (infinite rank-2 family)

3D cubic grid:
- 3D range-1 von Neumann
- 3D Saltire (equivalent to 3D range-1 Truncated Octahedral)

Higher-dimensional:
- 4D range-1 von Neumann
- 5D range-1 von Neumann

Obviously there are far too many infinite families of rules, hence it is hard to explore all rulespaces less than 1024 rules large in these neighbourhoods systematically.

What next?

With all due honesty I do not know how to proceed with this. I presume that this post would be useful to only a very small number of Lifeenthusiasts. But anyway, I decided to research this topic, so I decided to share the results of this research.

[confocaloid]

One reasonably small space is "2-state isotropic CA on the hexagonal tiling using honeycomb neighbourhood, and with the added restriction that the current state of the middle cell is not considered when deciding on its future state".

There are 13 distinguishable fully-specified conditions (0, 1, 2o, 2m, 2p, 3o, 3m, 3p, 4o, 4m, 4p, 5, 6).
Note that this CA type isn't covered by the variations on the "...-totalistic" theme you mentioned in your post, since different neighbourhood configurations can be distinguished here.

There are 2^13 = 8192 different rulesets. Although this does exceed your "hard limit" of 2^10 = 1024, this is not too large, and can be further reduced. For example, it makes sense to restrict the rules so that "2o" is a living condition, and also neither "0" nor "1" is a living condition. These additional restrictions lead to a subspace with only 2^10 = 1024 rulesets, matching your "hard limit".

Two known examples of "interesting" cellular automata in this subspace are B2o45/S2o45H and B2o3p45/S2o3p45H.

I have been pondering about the question: what rulespaces are small enough such that every rule in it can be explored systematically in a reasonable amount of time, and if so, what objects can they contain? This question is ill-defined (depending on what 'systematic' and 'reasonable' means), but I set the hard limit for a 'small' rulespace to be less than 2^10, or 1024 rules. In this essay I will only focus on 2-state rules.

[...]

What next?

With all due honesty I do not know how to proceed with this. [...]

Note that the answer to "what next" may depend on what is meant by "rulespace".
To quote essentially the same question from a different context:

[...] I'm curious about what specifically you meant by "rulespaces" [...]; do you mean broad categories (LtL, INT, Generations, etc.), or a bit more specific (i.e., breaking down INT to B0, Whitespace, 1TFL, etc.)? [...]

• First, there are what can be described as "CA types" (types of cellular automata). A CA type may restrict:
  o the underlying tiling (e.g. 2D square, 2D hexagonal, 3D cubic, ...);
  o the number of cellstates (two-state, three-state, ...);
  o the neighbourhood (e.g. range-1 Moore, range-3 cross, honeycomb, knight's move neighbourhood, weighted NW151505151, ...)
  However, a CA type doesn't add restrictions on which rules are allowed and which rules are forbidden. (So, for example, "Life-like CA" is a CA type, but "non-strobing Life-like CA" isn't).
• For every CA type, there is the (unrestricted) space of all possible rulesets for that CA type. (For example, the space of all 2^18 rulesets for Life-like CA.)
  Then many subspaces can be defined, by adding additional restrictions on which rules are allowed and which rules are disallowed.
  For example, "non-strobing Life-like CA without survival" is one such subspace (the cardinality is 2^8 = 256; each of living conditions B1, B2, B3, B4, B5, B6, B7, B8 can be independently either included or excluded; all of the rules B0, D0, D1, D2, D3, D4, D5, D6, D7, D8 are required).
• Moreover, it's possible to define subspaces merely by adding restrictions on which state-to-state transitions are allowed and which state-to-state transitions are disallowed, but without considering specific rules.
  One simple example of such a subspace is "Life-like CA without survival"; this tells only that "1->1" transitions are forbidden (every alive cell will die in the next generation), without telling anything at all about specific rules.
  For another example, see a post about a four-state subspace where every alive cell is either "newborn", "alive non-kid", or "a cell that survived and remained a kid".

So the answer to "what next" may depend on a choice between either exploring CA types or exploring restricted subspaces of some sort.
These are more or less ideas for what could be explored, rather than specific suggestions.

[H. H. P. M. P. Cole]

One reasonably small space is "2-state isotropic CA on the hexagonal tiling using honeycomb neighbourhood, and with the added restriction that the current state of the middle cell is not considered when deciding on its future state".
[...]

You are right, I didn't consider the class of isotropic cellular automata where the future state is not affected by the cell's current state (anti-totalistic rules fall under this class)... Speaking of which, the space of isotropic 1D rules with any maximally symmetric 4-neighbour neighbourhood where the future state is not affected by the cell's current state has exactly 2^10 rules in it.

The ten toggleable conditions in this rulespace can probably be represented by:

Code: Select all

00X00
00X01
00X10
00X11
01X01
01X10
01X11
10X01
10X11
11X11

where X is the central cell, and 0 and 1 represent state-0 and state-1 cells in the central cell's neighbourhood.

[...] For example, it makes sense to restrict the rules so that "2o" is a living condition, and also neither "0" nor "1" is a living condition. These additional restrictions lead to a subspace with only 2^10 = 1024 rulesets, matching your "hard limit". [...]

It might make sense to restrict the rulespace to the rules that can be proven to potentially have spaceships solely based on what conditions are in the ruleset and what others aren't. Hence in the range-2 semi-totalistic 1D rulespace there are only 2^7 rules which potentially have spaceships (B2 is in the ruleset and B0 and B1 are not, toggleable conditions are B3, B4, S0, S1, S2, S3, S4). I haven't computed the number of rules under this constraint for different neighbourhoods and 'parent' rulespaces, and I might do it soon.

[H. H. P. M. P. Cole]

Doubleposting but I feel that this warrants a doublepost.

Pruning rulespaces

It would make sense to treat the semi-totalistic condition A0 and all conditions that are a subset of semi-totalistic condition A1 as untoggleable, as B0/Dn (where n is the neighbour count in the neighbourhood) rules are generally unpredictable, and B1 rules usually have runaway behaviour.

Specifying these conditions as untoggleable reduces the size of anti-, pure-, and semi-totalistic rulespaces by a factor of 2^2, or 4. In addition, consider the comment below (from the previous post):

It might make sense to restrict the rulespace to the rules that can be proven to potentially have spaceships solely based on what conditions are in the ruleset and what others aren't. Hence in the range-2 semi-totalistic 1D rulespace there are only 2^7 rules which potentially have spaceships (B2 is in the ruleset and B0 and B1 are not, toggleable conditions are B3, B4, S0, S1, S2, S3, S4). I haven't computed the number of rules under this constraint for different neighbourhoods and 'parent' rulespaces, and I might do it soon.

For simplicity, I will only consider, in this post, rulespaces where:

there is exactly one condition in this rulespace that is not a superset of any condition that is a subset of the semi-totalistic conditions B0 or B1, which also allows growth in all bounding dimensions. I call this condition the critical condition. If there are more such conditions then they are called critical conditions.

Hence I define a spaceshipful subrulespace in this rulespace where the untoggleable conditions in the rulespace are:
- the smallest set of conditions in this rulespace that is a superset of the semi-totalistic condition A0
- the smallest set of conditions in this rulespace that is a superset of the semi-totalistic condition A1
- the critical condition

Keep in mind that this only works when there is exactly one critical condition. I do not know how to define a similar concept in rulespaces where there are two or more such 'critical conditions' (i.e. consider the situation in R1 Moore, where both B2 and B3 allow bounding dimension growth).

Hence:
- the members of the infinite family of spaceshipful subrulespaces of the 1-dimensional semi-totalistic rulespaces where a cell has four neighbours and the neighbourhood is maximally symmetric all have a size of 2^7 (untoggleable conditions A0, A1, B2, critical condition B2),
- and the set of pure-totalistic rules within the above spaceshipful subrulespace has a size of 2^3 (untoggleable conditions A0, A1/D0, B2/S1, critical condition B2/S1)
- and the set of anti-totalistic rules within the first spaceshipful subrulespace mentioned has a size of 2^2 (untoggleable conditions A0/D0, A1/D1, B2/S2, critical condition B2/S2)

(In the last two entries, semi-totalistic notation was used to specify the untoggleable conditions for simplicity and convenience.)

Open questions:
- Is it possible to enumerate CA types (i.e. a combination of a neighbourhood and an equivalence class of the union of the set of cells in the neighbourhood and the central cell itself) that have exactly one critical condition?
- Is it possible to create a program to enumerate small spaceshipful subrulespaces within those CA types?

(Okay, I am really out of my depth with this one.)

[confocaloid]

Incomplete reply:

[...] It might make sense to restrict the rulespace to the rules that can be proven to potentially have spaceships solely based on what conditions are in the ruleset and what others aren't. [...]

See related discussion:
viewtopic.php?f=11&t=5471 "Speed limits and theorems about the existence of periodic objects"
https://arxiv.org/abs/0911.2890 "Growth and Decay in Life-Like Cellular Automata"