Isotropic non-totalistic rule
An isotropic non-totalistic rule (abbreviated INT) is a generalization of the concept of a Life-like rule, where the state of a cell after one tick depends on the configuration of the alive neighbours, not just their counts.
Hensel notation
Isotropic non-totalistic rules (on the square grid with range-1 Moore neighbourhood and two cellstates) are described using Hensel notation developed by Alan Hensel, an extension of the birth/survival notation additionally describing allowed or forbidden configurations. Each digit in the rule's birth and survival conditions can be followed by an optional suffix, with each allowed configuration described by a specific letter; a minus sign may be used to forbid configurations rather than allow them. If no configurations are specified, all are considered to be allowed, as in the totalistic case. This notation is not used by non-isotropic cellular automata.
For instance, B2-a/S12 (the Just Friends rule) indicates that a dead cell will be born with 2 neighbours, except when they are adjacent (indicated by the "-a"), and that a live cell will survive with 1 or 2 neighbours in any configuration. This exclusion of the "B2a" transition prevents the rule from exploding in a similar manner to Seeds.
This notation has the following symmetry: For any letter x and number n ≠ 4, nx is defined if and only (8 - n)x is defined and moreover (8 - n)x is the complement (change live cells to dead and dead cells to live; ignore the center cell) of nx.
Alongside the conventional Moore neighbourhood, this notation can also be used to describe transitions on the 8-cell "exploded" Moore neighbourhoods,^{[1]} such as the "Far Corners" and "Far Edges" neighbourhoods supported by CAViewer.
The following table describes all possible neighbourhood configurations for the Moore neighbourhood of range 1:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|---|
— (no letter) |
|||||||||
c (corner) |
|||||||||
e (edge) |
|||||||||
k (knight) |
|||||||||
a (adjacent) |
|||||||||
i | |||||||||
n | |||||||||
y | |||||||||
q | |||||||||
j | |||||||||
r | |||||||||
t | |||||||||
w | |||||||||
z |
Subsets
To allow patterns to exceed their initial bounding box, a rule must have at least one of b1(c,e), b2(c,a) and b3i enabled, and to escape their bounding diamond, at least one of b1(c,e), b2(e,a), b3a. Irrespective of other transitions, for patterns in a rule to be able to exit their bounding octagon, of the 2^{7} combinations across these 7 transitions, those where any of b1c,b1e and b2a are enabled provide 2^{6}+2^{5}+2^{4}, leaving only 2^{4} cases in which both b2e and b2c, or both b3i and b3a, must be on, of which there are 7 such cases, providing an upper bound of 119/128ths of the 2^{102} such INT rules. These are necessary for spaceships, as well as for a finite pattern to be Turing-complete (because otherwise, it may only enter fixedly many states depending on its initial size).
The 2^{6}=64 isotropic 2-state rules in the von Neumann neighbourhood can be simulated via isotropic non-totalistic rules on the Moore neighbourhood; for example, B1/SV becomes B1e2ak3inqy4ny5e/S.
To be a von Neumann rule, birth and survival transitions in the following equivalence classes must be the same:
- 0 : 0=1c=2n=2c=3c=4c
- 1 : 1e=2a=2k=3i=3n=3y=3q=4n=4y=5e
- 2e: 2e=3k=3a=3j=4k=4a=4q=4w=5a=5j=5k=6e
- 2i: 2i=3r=4i=4t=4z=5r=6i
- 3 : 3e=4j=4r=5i=5n=5y=5q=6a=6k=7e
- 4 : 4e=5c=6c=6n=7c=8
For it to be outer-totalistic, the 2e and 2i transitions must be equivalent.
A similar set of constraints is given in the static symmetry article, that are sufficient for the preservation of D8_2 symmetry.
Dualities
They are generated as follows,
- For the black/white reversal, take the bitwise NOT of the input and output.
- For the strobing dual,
- in even generations, take the bitwise NOT of the output, and
- in odd generations, take the bitwise NOT of the input.
- For the checkerboard dual,
- for even-parity cells, XOR the input with an "X" in the four corners and centre, and
- for odd-parity cells, XOR the input with an "O" in the four edges.
Outer total |
Identity | Black/white reversal |
Strobing dual |
Checkerboard dual | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|
b | s | even | odd | even | odd | ||||||
b | s | b | s | b | s | b | s | ||||
0 | ~s8 | ~b8 | ~b0 | ~s0 | s8 | b8 | ~s4c | ~b4c | b4e | s4e | |
1 | c | ~s7c | ~b7c | ~b1c | ~s1c | s7c | b7c | ~s3c | ~b3c | b5c | s5c |
e | ~s7e | ~b7e | ~b1e | ~s1e | s7e | b7e | ~s5e | ~b5e | b3e | s3e | |
2 | c | ~s6c | ~b6c | ~b2c | ~s2c | s6c | b6c | ~s2c | ~b2c | b6c | s6c |
e | ~s6e | ~b6e | ~b2e | ~s2e | s6e | b6e | ~s6e | ~b6e | b2e | s2e | |
k | ~s6k | ~b6k | ~b2k | ~s2k | s6k | b6k | ~s4n | ~b4n | b4r | s4r | |
a | ~s6a | ~b6a | ~b2a | ~s2a | s6a | b6a | ~s4y | ~b4y | b4j | s4j | |
i | ~s6i | ~b6i | ~b2i | ~s2i | s6i | b6i | ~s6i | ~b6i | b2i | s2i | |
n | ~s6n | ~b6n | ~b2n | ~s2n | s6n | b6n | ~s2n | ~b2n | b6n | s6n | |
3 | c | ~s5c | ~b5c | ~b3c | ~s3c | s5c | b5c | ~s1c | ~b1c | b7c | s7c |
e | ~s5e | ~b5e | ~b3e | ~s3e | s5e | b5e | ~s7e | ~b7e | b1e | s1e | |
k | ~s5k | ~b5k | ~b3k | ~s3k | s5k | b5k | ~s5a | ~b5a | b3a | s3a | |
a | ~s5a | ~b5a | ~b3a | ~s3a | s5a | b5a | ~s5k | ~b5k | b3k | s3k | |
i | ~s5i | ~b5i | ~b3i | ~s3i | s5i | b5i | ~s3y | ~b3y | b5y | s5y | |
n | ~s5n | ~b5n | ~b3n | ~s3n | s5n | b5n | ~s3n | ~b3n | b5n | s5n | |
y | ~s5y | ~b5y | ~b3y | ~s3y | s5y | b5y | ~s3i | ~b3i | b5i | s5i | |
q | ~s5q | ~b5q | ~b3q | ~s3q | s5q | b5q | ~s3q | ~b3q | b5q | s5q | |
j | ~s5j | ~b5j | ~b3j | ~s3j | s5j | b5j | ~s5j | ~b5j | b3j | s5j | |
r | ~s5r | ~b5r | ~b3r | ~s3r | s5r | b5r | ~s5r | ~b5r | b3r | s3r | |
4 | c | ~s4e | ~b4e | ~b4c | ~s4c | s4e | b4e | ~s0 | ~b0 | b8 | s8 |
e | ~s4c | ~b4c | ~b4e | ~s4e | s4c | b4c | ~s8 | ~b8 | b0 | s0 | |
k | ~s4k | ~b4k | ~b4k | ~s4k | s4k | b4k | ~s4a | ~b4a | b4a | s4a | |
a | ~s4a | ~b4a | ~b4a | ~s4a | s4a | b4a | ~s4k | ~b4k | b4k | s4k | |
i | ~s4t | ~b4t | ~b4t | ~s4t | s4t | b4t | ~s4i | ~b4i | b4t | s4t | |
n | ~s4r | ~b4r | ~b4r | ~s4r | s4r | b4r | ~s2k | ~b2k | b6k | s6k | |
y | ~s4j | ~b4j | ~b4j | ~s4j | s4j | b4j | ~s2a | ~b2a | b6a | s6a | |
q | ~s4w | ~b4w | ~b4w | ~s4w | s4w | b4w | ~s4w | ~b4w | b4q | s4q | |
j | ~s4y | ~b4y | ~b4y | ~s4y | s4y | b4y | ~s6a | ~b6a | b2a | s2a | |
r | ~s4n | ~b4n | ~b4n | ~s4n | s4n | b4n | ~s6k | ~b6k | b2k | s2k | |
t | ~s4i | ~b4i | ~b4i | ~s4i | s4i | b4i | ~s4t | ~b4t | b4i | s4i | |
w | ~s4q | ~b4q | ~b4q | ~s4q | s4q | b4q | ~s4q | ~b4q | b4w | s4w | |
z | ~s4z | ~b4z | ~b4z | ~s4z | s4z | b4z | ~s4z | ~b4z | b4z | s4z | |
5 | c | ~s3c | ~b3c | ~b5c | ~s5c | s3c | b3c | ~s7c | ~b7c | s1c | b1c |
e | ~s3e | ~b3e | ~b5e | ~s5e | s3e | b3e | ~s1e | ~b1e | b7e | s7e | |
k | ~s3k | ~b3k | ~b5k | ~s5k | s3k | b3k | ~s3a | ~b3a | b5a | s5a | |
a | ~s3a | ~b3a | ~b5a | ~s5a | s3a | b3a | ~s3k | ~b3k | b5k | s5k | |
i | ~s3i | ~b3i | ~b5i | ~s5i | s3i | b3i | ~s5y | ~b5y | b3y | s3y | |
n | ~s3n | ~b3n | ~b5n | ~s5n | s3n | b3n | ~s5n | ~b5n | b3n | s3n | |
y | ~s3y | ~b3y | ~b5y | ~s5y | s3y | b3y | ~s5i | ~b5i | b3i | s3i | |
q | ~s3q | ~b3q | ~b5q | ~s5q | s3q | b3q | ~s5q | ~b5q | b3q | s3q | |
j | ~s3j | ~b3j | ~b5j | ~s5j | s3j | b3j | ~s3j | ~b3j | b5j | s5j | |
r | ~s3r | ~b3r | ~b5r | ~s5r | s3r | b3r | ~s3r | ~b3r | b5r | s5r | |
6 | c | ~s2c | ~b2c | ~b6c | ~s6c | s2c | b2c | ~s6c | ~b6c | b2c | s2c |
e | ~s2e | ~b2e | ~b6e | ~s6e | s2e | b2e | ~s2e | ~b2e | b6e | s5e | |
k | ~s2k | ~b2k | ~b6k | ~s6k | s2k | b2k | ~s4r | ~b4r | b4n | s4n | |
a | ~s2a | ~b2a | ~b6a | ~s6a | s2a | b2a | ~s4j | ~b4j | b4y | s4y | |
i | ~s2i | ~b2i | ~b6i | ~s6i | s2i | b2i | ~s2i | ~b2i | b6i | s6i | |
n | ~s2n | ~b2n | ~b6n | ~s6n | s2n | b2n | ~s6n | ~b6n | b2n | s2n | |
7 | c | ~s1c | ~b1c | ~b7c | ~s7c | s1c | b1c | ~s5c | ~b5c | b3c | s3c |
e | ~s1e | ~b1e | ~b7e | ~s7e | s1e | b1e | ~s3e | ~b3e | b5e | s5e | |
8 | ~s0 | ~b0 | ~b8 | ~s8 | s0 | b0 | ~s4e | ~b4e | b4c | s4c |
Generalizations
Von Neumann extensions
While not a rulespace in itself, a notation exists that allows for existing neighbourhoods to be extended by four cells. This is the notation used for range-2 von Neumann isotropic non-totalistic rules (in which it is combined with the range-1 Moore isotropic non-totalistic notation), and range-3 cross isotropic non-totalistic rules (in which it is combined with the range-2 cross isotropic non-totalistic notation).
This extension notation was initially proposed on February 24, 2019 by AforAmpere and Milo Jacquet for range-2 von Neumann isotropic non-totalistic rules.^{[2]}
For each transition, use the transition corresponding to the configuration of the center 8 cells, aligned with the canonical directions in the table above. Then take the outside 4 cells, and depending on the configurations in the table below, add that letter.
a | c | d | e | f | g | i | j | |
---|---|---|---|---|---|---|---|---|
— |
k | l | m | n | o | p | q | r | |
---|---|---|---|---|---|---|---|---|
— |
For transitions that are the same under reflections or rotations, the canonical transition is the lowest alphabetically.
'x' is used after a totalistic number. An example range-2 von Neumann rulestring is 'B3x2ic1ei5x-3kr/S0x8x'.
bubblegum has also proposed to use the 'v' character to represent outer totalistic transitions for the inner 8 cells for range-2 von Neumann rules.^{[3]}
Range-2 von Neumann neighbourhood
There are 618 different transitions possible in the range-2 von Neumann neighbourhood. Four notations have been proposed as of February 2018.^{[4]}
As of 27 November 2020, the only CA simulation software which natively supports such rules is CAViewer.^{[5]}
An earlier proposed notation for range-2 von Neumann isotropic non-totalistic rules is based on Hensel notation.^{[2]} It never entered common use.
Range-2 cross neighbourhood
A proposal for this neighbourhood was mistakenly created in 2017,^{[6]} and a second notation was created in mid-2020^{[7]} (although missing a 3-cell and 5-cell transition).^{[8]}
Range-2 knight neighbourhood
A notation for this was proposed in mid-2020^{[7]} (with a duplicated 4-cell transition).^{[8]}
3-state Moore neighbourhood
A notation for 3-state range-1 rules is underway.^{[9]}
Hexagonal neighbourhood
- Main article: Hexagonal neighbourhood#Isotropic non-totalistic rules
It is possible to define isotropic non-totalistic CAs on a hexagonal grid as well, using a notation due to Paul Callahan.
Table of isotropic non-totalistic rulespaces
It has been suggested that this page or section be split into List of rulespaces. (Discuss) |
The number of unique transitions for higher ranges tends to be extremely large, and the development of notations for such rules is generally infeasible. The following table documents notable examples (grids are notated with Schläfli symbols as to simultaneously convey grid type and dimension):
Common name | Rulespace definitions | Transitions | Notated? | Major software support | |||||
---|---|---|---|---|---|---|---|---|---|
Grid | Range | States | Neighbourhood | Golly | LifeViewer | lifelib | |||
Block cellular automata | {4,4} | 1/2 | 2 | Moore | 6 | Yes | (Unnecessary) | ||
- | {4,4} | 1 | 2 | von Neumann | 6 | Trivial | (Unnecessary) | ||
3D vN non-totalistic | {4,3,4} | 1 | 2 | von Neumann | 10 | No | No | No | No |
Non-totalistic hexagonal | {6,3} | 1 | 2 | hexagonal | 13 | Yes | No^{[n 1]} | Yes | Yes |
Knight INT | {4,4} | 2 | 2 | knight | 43 | Yes | No | No | No |
Isotropic non-totalistic | {4,4} | 1 | 2 | Moore | 51 | Yes | Yes | Yes | Yes |
Exploded | {4,4} | ≥1 | 2 | variable^{[n 2]} | 51 | Yes | No | Some^{[n 3]} | Some^{[n 4]} |
Cross INT | {4,4} | 2 | 2 | cross | 55 | Yes | No | No | No |
- | {4,4} | 2 | 2 | nonstandard^{[n 5]} | 570 | No | No | No | No |
R2 von Neumann INT | {4,4} | 2 | 2 | von Neumann | 618 | Yes | No | No | Yes |
- | {4,4} | 2 | 2 | nonstandard^{[n 6]} | 618 | No | No | No | No |
3-state knight INT | {4,4} | 2 | 3 | knight | 873 | No | No | No | No |
3-state INT | {4,4} | 1 | 3 | Moore | 954 | Yes | No^{[n 7]} | No^{[n 7]} | No^{[n 7]} |
3-state cross INT | {4,4} | 2 | 3 | cross | 1035 | No | No | No | No |
4-state knight INT | {4,4} | 2 | 4 | knight | 8356 | No | No | No | No |
4-state INT | {4,4} | 1 | 4 | Moore | 8740 | Yes | No^{[n 7]} | No^{[n 7]} | No^{[n 7]} |
4-state cross INT | {4,4} | 2 | 4 | cross | 9316 | No | No | No | No |
R2 hexagonal INT | {6,3} | 2 | 2 | hexagonal | 22668 | No | No | No | No |
3-state R2 vN INT | {4,4} | 2 | 3 | von Neumann | 68715 | No | No | No | No |
R2 Moore-without-corners | {4,4} | 2 | 2 | circular | 132744 | No | No | No | No |
3D non-totalistic | {4,3,4} | 1 | 2 | Moore | 1426144^{[n 8]} | No | No | No | No |
R2 Moore INT | {4,4} | 2 | 2 | Moore | 2105872 | No | No | No | No |
4D non-totalistic | {4,3,3,4} | 1 | 2 | Moore | 3148244699232062849152^{[n 9]} | No | No | No | No |
- ↑ The rulespace can be simulated via MAP strings, or, less preferably, ruletables, however no direct support for the notation exists.
- ↑ Based on the Moore neighbourhood, with the four edge cells and/or the four corner cells moved away from the origin a defined distance.
- ↑ The range-N "far corners" + range-M "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
- ↑ The range-2 "far corners" and range-3 "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
- ↑ The number is the same for a "circle" formed of four three-cell lines at distance 2 from the center, and four "pre-blocks" with the gaps all facing the center or all facing outwards (or any configuration of eight eightfold neighbours and two fourfold ones)
- ↑ Range-1 Moore, with added range-2 corners
- ↑ ^{7.0} ^{7.1} ^{7.2} ^{7.3} ^{7.4} ^{7.5} The rulespace can be simulated via ruletables, however no direct support for the notation exists.
- ↑ first calculated by Milo Jacquet
- ↑ first calculated using the Pólya enumeration theorem by DroneBetter's dimensional_INT_enumerator.py (explained here)
A rule with an n-dimensional range-k Moore neighbourhood has A361870(n,2*k+1) transitions.
Soup-searching non-totalistic rules
Adam P. Goucher's apgsearch was modified to support isotropic non-totalistic rules by praosylen on December 17, 2015.^{[10]} This hacked version was later modified in late January 2016 to be able to upload the search results to Catagolue.^{[11]} However, apgsearch did not gain native support for these rules until v4.2, released on September 10, 2017, which can search isotropic non-totalistic rules without B0.^{[12]} v4.66 and above also support the searching of isotropic hexagonal neighbourhood rules.^{[13]} Range 2 von Neumann isotropic rules can also be searched by means of a ruletable using a custom neighbourhood.^{[14]} However, note that GPU censuses support only outer-totalistic rules.
See also
- Life-like cellular automaton
- Non-isotropic cellular automaton
- Generations
- Larger than Life
- Dualities
References
- ↑ Connor Steppie (April 23, 2021). Re: Lemon41625's Cellular Automaton (discussion thread) at the ConwayLife.com forums
- ↑ ^{2.0} ^{2.1} AforAmpere (February 23, 2019). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
- ↑ bubblegum (August 26, 2020). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
- ↑ Connor Steppie (February 9, 2019). Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
- ↑ lemon41625 (November 29, 2020). Re: CAViewer - A Cellular Automaton Simulator written in Java (discussion thread) at the ConwayLife.com forums
- ↑ toroidalet (September 2, 2017). Re: Golly suggestions (discussion thread) at the ConwayLife.com forums
- ↑ ^{7.0} ^{7.1} lemon41625 (July 23, 2020). Re: Pattern viewer for forum threads (discussion thread) at the ConwayLife.com forums
- ↑ ^{8.0} ^{8.1} Re: Pattern viewer for forum threads (discussion thread) at the ConwayLife.com forums
- ↑ Connor Steppie (January 19, 2020). Re: 3-state range-1 outer-totalistic rulespace (discussion thread) at the ConwayLife.com forums
- ↑ praosylen (December 17, 2015). Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher (January 21, 2016). Re: apgsearch v2.2 (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher (September 10, 2017). Re: apgsearch v4.2 (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher (December 1, 2018). Re: Non-totalistic hex rules (discussion thread) at the ConwayLife.com forums
- ↑ lemon41625 (June 19, 2020). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
External links
- Alan Hensel. "Table of non-totalistic neighborhoods". Retrieved on 2016-06-12.
- Alan Hensel. "Rule notation". Retrieved on 2016-06-12. (note that the linked page describes an earlier version of Hensel notation that has fallen into disuse)
- Non-totalistic Rules - notations, projects, & discussion (discussion thread) at the ConwayLife.com forums