Isotropic non-totalistic rule

From LifeWiki
Jump to navigation Jump to search

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)
INT Moore R1 0.png INT Moore R1 8.png
c
(corner)
INT Moore R1 1c.png INT Moore R1 2c.png INT Moore R1 3c.png INT Moore R1 4c.png INT Moore R1 5c.png INT Moore R1 6c.png INT Moore R1 7c.png
e
(edge)
INT Moore R1 1e.png INT Moore R1 2e.png INT Moore R1 3e.png INT Moore R1 4e.png INT Moore R1 5e.png INT Moore R1 6e.png INT Moore R1 7e.png
k
(knight)
INT Moore R1 2k.png INT Moore R1 3k.png INT Moore R1 4k.png INT Moore R1 5k.png INT Moore R1 6k.png
a
(adjacent)
INT Moore R1 2a.png INT Moore R1 3a.png INT Moore R1 4a.png INT Moore R1 5a.png INT Moore R1 6a.png
i INT Moore R1 2i.png INT Moore R1 3i.png INT Moore R1 4i.png INT Moore R1 5i.png INT Moore R1 6i.png
n INT Moore R1 2n.png INT Moore R1 3n.png INT Moore R1 4n.png INT Moore R1 5n.png INT Moore R1 6n.png
y INT Moore R1 3y.png INT Moore R1 4y.png INT Moore R1 5y.png
q INT Moore R1 3q.png INT Moore R1 4q.png INT Moore R1 5q.png
j INT Moore R1 3j.png INT Moore R1 4j.png INT Moore R1 5j.png
r INT Moore R1 3r.png INT Moore R1 4r.png INT Moore R1 5r.png
t INT Moore R1 4t.png
w INT Moore R1 4w.png
z INT Moore R1 4z.png

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 27 combinations across these 7 transitions, those where any of b1c,b1e and b2a are enabled provide 26+25+24, leaving only 24 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 2102 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 26=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

Note that though the black/white reversal exists for all rules, in general the strobing dual of a rule is a pair of INT rules that alternate over time (even and odd iterations), and the checkerboard dual a pair that alternate over space (even and odd squares in a chequerboard tiling). The members of each pair coincide in duals of self-complementary rules (that are their own black/white reversal), such as Day & Night. Each self-complementary rule is a member of an equivalence class of not a pair but a quartet.

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
INT vN Extensions a.png INT vN Extensions c.png INT vN Extensions d.png INT vN Extensions e.png INT vN Extensions f.png INT vN Extensions g.png INT vN Extensions i.png INT vN Extensions j.png
k l m n o p q r
INT vN Extensions k.png INT vN Extensions l.png INT vN Extensions m.png INT vN Extensions n.png INT vN Extensions o.png INT vN Extensions p.png INT vN Extensions q.png INT vN Extensions r.png

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

Ambox notice.png 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
  1. The rulespace can be simulated via MAP strings, or, less preferably, ruletables, however no direct support for the notation exists.
  2. Based on the Moore neighbourhood, with the four edge cells and/or the four corner cells moved away from the origin a defined distance.
  3. The range-N "far corners" + range-M "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
  4. The range-2 "far corners" and range-3 "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
  5. 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)
  6. Range-1 Moore, with added range-2 corners
  7. 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.
  8. first calculated by Milo Jacquet
  9. 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 OEISicon light 11px.pngA361870(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

References

  1. Connor Steppie (April 23, 2021). Re: Lemon41625's Cellular Automaton (discussion thread) at the ConwayLife.com forums
  2. 2.0 2.1 AforAmpere (February 23, 2019). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  3. bubblegum (August 26, 2020). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  4. Connor Steppie (February 9, 2019). Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  5. lemon41625 (November 29, 2020). Re: CAViewer - A Cellular Automaton Simulator written in Java (discussion thread) at the ConwayLife.com forums
  6. toroidalet (September 2, 2017). Re: Golly suggestions (discussion thread) at the ConwayLife.com forums
  7. 7.0 7.1 lemon41625 (July 23, 2020). Re: Pattern viewer for forum threads (discussion thread) at the ConwayLife.com forums
  8. 8.0 8.1 Re: Pattern viewer for forum threads (discussion thread) at the ConwayLife.com forums
  9. Connor Steppie (January 19, 2020). Re: 3-state range-1 outer-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  10. praosylen (December 17, 2015). Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
  11. Adam P. Goucher (January 21, 2016). Re: apgsearch v2.2 (discussion thread) at the ConwayLife.com forums
  12. Adam P. Goucher (September 10, 2017). Re: apgsearch v4.2 (discussion thread) at the ConwayLife.com forums
  13. Adam P. Goucher (December 1, 2018). Re: Non-totalistic hex rules (discussion thread) at the ConwayLife.com forums
  14. lemon41625 (June 19, 2020). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums

External links