Isotropic non-totalistic rule

From LifeWiki
Revision as of 15:38, 28 August 2022 by Gzaytman (talk | contribs) (→‎Moore neighbourhood: actually linkify)
Jump to navigation Jump to search

An isotropic non-totalistic cellular automaton is a generalization of the concept of a Life-like cellular automaton in which transitions take into account not only the total number of live neighbors of a cell, but also the relative configuration of those neighbors.

Isotropic non-totalistic rules are described using several different classes of notation.

Rulespaces

Moore neighbourhood

Isotropic non-totalistic rules are described using Hensel notation, an extension of B/S notation developed by Alan Hensel additionally describing allowed or forbidden configurations. Each digit in the rule's birth and survival conditions is 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 neighbors, except when they are adjacent (indicated by the "-a"), and that a live cell will survive with 1 or 2 neighbors in any configuration. This exclusion of the "B2a" transition prevents the rule from exploding in a similar manner as 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 neighborhood 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

Rules using the von Neumann neighbourhood can be simulated via isotropic non-totalistic rules on the Moore neighbourhood; for example, B1/SV becomes B1e2ak3inqy4ny5e/S.

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 MiloJacquet 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 cellular automaton simulation software 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

It is possible to define isotropic non-totalistic CAs on a hexagonal grid as well. The following table describes all possible neighborhood configurations for the hexagonal neighbourhood, using notation due to Paul Callahan;[10][11] the names ortho, meta and para were chosen in analogy to arene substitution patterns in aromatic chemistry:

0 1 2 3 4 5 6
— (no
letter) 		INT hexagonal R1 0.png INT hexagonal R1 1.png INT hexagonal R1 5.png INT hexagonal R1 6.png
o
(ortho) 		INT hexagonal R1 2o.png INT hexagonal R1 3o.png INT hexagonal R1 4o.png
m
(meta) 		INT hexagonal R1 2m.png INT hexagonal R1 3m.png INT hexagonal R1 4m.png
p
(para) 		INT hexagonal R1 2p.png INT hexagonal R1 3p.png INT hexagonal R1 4p.png

Golly does not support isotropic non-totalistic hexagonal rules using this syntax, so they must instead be simulated using either rule tables or MAP strings. LifeViewer and lifelib support them natively.

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:

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[n 1] Trivial (Unnecessary)
Non-totalistic hexagonal {6,3} 1 2 hexagonal 13 Yes No[n 2] 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 3] 51 Yes No Some[n 4] Some[n 5]
Cross INT {4,4} 2 2 cross 55 Yes No No No
- {4,4} 2 2 nonstandard[n 6] 570 No No No No
- {4,4} 2 2 nonstandard[n 7] 570 No No No No
- {4,4} 2 2 nonstandard[n 8] 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 9] 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 WIP No[n 10] No[n 10] No[n 10]
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 No No[n 10] No[n 10] No[n 10]
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 11] No No No No
R2 Moore INT {4,4} 2 2 Moore 2105872 No No No No
  1. ↑ For n states, the number of unique transitions is given by the doubly triangular numbers: A002817
  2. ↑ The rulespace can be simulated via MAP strings, or, less preferably, ruletables, however no direct support for the notation exists.
  3. ↑ Based on the Moore neighbourhood, with the four edge cells and/or the four corner cells moved away from the origin a defined distance.
  4. ↑ The range-N "far corners" + range-M "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
  5. ↑ The range-2 "far corners" and range-3 "far edges" cases are supported, but the general case of exploded Moore neighbourhoods are not.
  6. ↑ A "circle" formed of four three-cell lines at distance 2 from the center
  7. ↑ Four "pre-blocks" with the gaps facing the center
  8. ↑ Four "pre-blocks" with the gaps facing outwards
  9. ↑ Range-1 Moore, with added range-2 corners
  10. ↑ 10.0 10.1 10.2 10.3 10.4 10.5 The rulespace can be simulated via ruletables, however no direct support for the notation exists.
  11. ↑ Upper bound; calculations by Milo Jacquet returned this number of transitions, however calculations by wildmyron returned 1426132

Range-1 von Neumann neighbourhood (or equivalent neighbourhood) rulespaces with n states follow the doubly triangular numbers (A002817) for number of unique 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.[12] This hacked version was later modified in late January 2016 to be able to upload the search results to Catagolue.[13] 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.[14] v4.66 and above also support the searching of isotropic hexagonal neighborhood rules.[15] Range 2 von Neumann isotropic rules can also be search via the means of a ruletable using a custom neighbourhood.[16]

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 https://conwaylife.com/forums/viewtopic.php?f=3&t=1622&p=128945#p128945
  9. ↑ Connor Steppie (January 19, 2020). Re: 3-state range-1 outer-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  10. ↑ Paul Callahan (December 3, 1997). "Experiments with a somewhat "Life-like" hexagonal CA (long)". Retrieved on September 29, 2017.
  11. ↑ "ExtendedCallahanHexagonal.gif". ConwayLife.com forums. Retrieved on July 22, 2017.
  12. ↑ praosylen (December 17, 2015). "Re: Hacking apgsearch". ConwayLife.com forums. Retrieved on June 12, 2016.
  13. ↑ Adam P. Goucher (January 21, 2016). "Re: apgsearch v2.2". ConwayLife.com forums. Retrieved on June 12, 2016.
  14. ↑ Adam P. Goucher (September 10, 2017). Re: apgsearch v4.2 (discussion thread) at the ConwayLife.com forums
  15. ↑ Adam P. Goucher (December 1, 2018). "Re: Non-totalistic hex rules". ConwayLife.com forums. Retrieved on December 1, 2018.
  16. ↑ lemon41625 (June 19, 2020). Re: Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums

External links

Retrieved from "https://conwaylife.com/w/index.php?title=Isotropic_non-totalistic_rule&oldid=114526"