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, 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⁷ combinations across these 7 transitions, those where any of b1c,b1e and b2a are enabled provide 2⁶+2⁵+2⁴, leaving only 2⁴ 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¹⁰² 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⁶=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.

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.

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.

As of 27 November 2020, the only CA simulation software which natively supports such rules is CAViewer.

An earlier proposed notation for range-2 von Neumann isotropic non-totalistic rules is based on Hensel notation. It never entered common use.

Range-2 cross neighbourhood

A proposal for this neighbourhood was mistakenly created in 2017, and a second notation was created in mid-2020 (although missing a 3-cell and 5-cell transition).

Range-2 knight neighbourhood

A notation for this was proposed in mid-2020 (with a duplicated 4-cell transition).

3-state Moore neighbourhood

A notation for 3-state range-1 rules is underway.

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

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	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	51	Yes	No	Some	Some
Cross INT	{4,4}	2	2	cross	55	Yes	No	No	No
-	{4,4}	2	2	nonstandard	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	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	No	No
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	No	No
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	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	No	No	No	No

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. This hacked version was later modified in late January 2016 to be able to upload the search results to Catagolue. 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. v4.66 and above also support the searching of isotropic hexagonal neighbourhood rules. Range 2 von Neumann isotropic rules can also be searched by means of a ruletable using a custom neighbourhood. 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

• Checkerboard dual

• List of isotropic non-totalistic cellular automata

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