Difference between revisions of "Isotropic non-totalistic Life-like cellular automaton"

From LifeWiki
Jump to: navigation, search
(New entry)
 
m (fixed size)
 
(46 intermediate revisions by 7 users not shown)
Line 1: Line 1:
'''Non-totalistic Life-like cellular automata''' are a generalization of [[Life-like cellular automata]] in which the transition function considers not just the number of cells in a given cell's neighborhood but also their alignment.
+
An '''isotropic non-totalistic Life-like 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.  
  
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.
+
[[Isotropic]] non-totalistic rules are described using Hensel notation, an extension of [[rulestring|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 Life-like cellular automata]].
  
The following table summarizes all possible neighborhood configurations:
+
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]].
  
{| class="wikitable" style="margin-left: auto; margin-right: auto"
+
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''.
 +
 
 +
== Moore neighbourhood ==
 +
 
 +
The following table describes all possible neighborhood configurations for the [[Moore neighbourhood]] of range 1:
 +
 
 +
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
 +
| style="border: none; background: #fff;" |
 +
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8
 
|-
 
|-
! !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8
+
! —<small style="font-weight: normal;"> (no<br/>letter)</small>
 +
| [[File:Neighborhood 0.png]] || || || || || || || || [[File:Neighborhood 8.png]]
 
|-
 
|-
! || [[File:Neighborhood 0.png]] || || || || || || || || [[File:Neighborhood 8.png]]
+
! c<br/><small style="font-weight: normal;">(corner)</small>
 +
| || [[File:Neighborhood 1c.png]] || [[File:Neighborhood 2c.png]] || [[File:Neighborhood 3c.png]] || [[File:Neighborhood 4c.png]] || [[File:Neighborhood 5c.png]] || [[File:Neighborhood 6c.png]] || [[File:Neighborhood 7c.png]] ||
 
|-
 
|-
! c (corner) || || [[File:Neighborhood 1c.png]] || [[File:Neighborhood 2c.png]] || [[File:Neighborhood 3c.png]] || [[File:Neighborhood 4c.png]] || [[File:Neighborhood 5c.png]] || [[File:Neighborhood 6c.png]] || [[File:Neighborhood 7c.png]] ||  
+
! e<br/><small style="font-weight: normal;">(edge)</small>
 +
| || [[File:Neighborhood 1e.png]] || [[File:Neighborhood 2e.png]] || [[File:Neighborhood 3e.png]] || [[File:Neighborhood 4e.png]] || [[File:Neighborhood 5e.png]] || [[File:Neighborhood 6e.png]] || [[File:Neighborhood 7e.png]] ||  
 
|-
 
|-
! e (edge) || || [[File:Neighborhood 1e.png]] || [[File:Neighborhood 2e.png]] || [[File:Neighborhood 3e.png]] || [[File:Neighborhood 4e.png]] || [[File:Neighborhood 5e.png]] || [[File:Neighborhood 6e.png]] || [[File:Neighborhood 7e.png]] ||  
+
! k<br/><small style="font-weight: normal;">(knight)</small>
 +
| || || [[File:Neighborhood 2k.png]] || [[File:Neighborhood 3k.png]] || [[File:Neighborhood 4k.png]] || [[File:Neighborhood 5k.png]] || [[File:Neighborhood 6k.png]] || ||  
 
|-
 
|-
! k (knight) || || || [[File:Neighborhood 2k.png]] || [[File:Neighborhood 3k.png]] || [[File:Neighborhood 4k.png]] || [[File:Neighborhood 5k.png]] || [[File:Neighborhood 6k.png]] || ||  
+
! a<br/><small style="font-weight: normal;">(adjacent)</small>
 +
| || || [[File:Neighborhood 2a.png]] || [[File:Neighborhood 3a.png]] || [[File:Neighborhood 4a.png]] || [[File:Neighborhood 5a.png]] || [[File:Neighborhood 6a.png]] || ||  
 
|-
 
|-
! a (adjacent) || || || [[File:Neighborhood 2a.png]] || [[File:Neighborhood 3a.png]] || [[File:Neighborhood 4a.png]] || [[File:Neighborhood 5a.png]] || [[File:Neighborhood 6a.png]] || ||  
+
! i
 +
| || || [[File:Neighborhood 2i.png]] || [[File:Neighborhood 3i.png]] || [[File:Neighborhood 4i.png]] || [[File:Neighborhood 5i.png]] || [[File:Neighborhood 6i.png]] || ||  
 
|-
 
|-
! i || || || [[File:Neighborhood 2i.png]] || [[File:Neighborhood 3i.png]] || [[File:Neighborhood 4i.png]] || [[File:Neighborhood 5i.png]] || [[File:Neighborhood 6i.png]] || ||  
+
! n
 +
| || || [[File:Neighborhood 2n.png]] || [[File:Neighborhood 3n.png]] || [[File:Neighborhood 4n.png]] || [[File:Neighborhood 5n.png]] || [[File:Neighborhood 6n.png]] || ||  
 
|-
 
|-
! n || || || [[File:Neighborhood 2n.png]] || [[File:Neighborhood 3n.png]] || [[File:Neighborhood 4n.png]] || [[File:Neighborhood 5n.png]] || [[File:Neighborhood 6n.png]] || ||  
+
! y
 +
| || || || [[File:Neighborhood 3y.png]] || [[File:Neighborhood 4y.png]] || [[File:Neighborhood 5y.png]] || || ||  
 
|-
 
|-
! y || || || || [[File:Neighborhood 3y.png]] || [[File:Neighborhood 4y.png]] || [[File:Neighborhood 5y.png]] || || ||  
+
! q
 +
| || || || [[File:Neighborhood 3q.png]] || [[File:Neighborhood 4q.png]] || [[File:Neighborhood 5q.png]] || || ||  
 
|-
 
|-
! q || || || || [[File:Neighborhood 3q.png]] || [[File:Neighborhood 4q.png]] || [[File:Neighborhood 5q.png]] || || ||  
+
! j
 +
| || || || [[File:Neighborhood 3j.png]] || [[File:Neighborhood 4j.png]] || [[File:Neighborhood 5j.png]] || || ||  
 
|-
 
|-
! j || || || || [[File:Neighborhood 3j.png]] || [[File:Neighborhood 4j.png]] || [[File:Neighborhood 5j.png]] || || ||  
+
! r
 +
| || || || [[File:Neighborhood 3r.png]] || [[File:Neighborhood 4r.png]] || [[File:Neighborhood 5r.png]] || || ||  
 
|-
 
|-
! r || || || || [[File:Neighborhood 3r.png]] || [[File:Neighborhood 4r.png]] || [[File:Neighborhood 5r.png]] || || ||  
+
! t
 +
| || || || || [[File:Neighborhood 4t.png]] || || || ||  
 
|-
 
|-
! t || || || || || [[File:Neighborhood 4t.png]] || || || ||  
+
! w
 +
| || || || || [[File:Neighborhood 4w.png]] || || || ||  
 
|-
 
|-
! w || || || || || [[File:Neighborhood 4w.png]] || || || ||  
+
! z
 +
| || || || || [[File:Neighborhood 4z.png]] || || || ||  
 +
|}
 +
 
 +
[http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3808#p71574 A proposed notation] for range-2 von Neumann isotropic non-totalistic rules is based on this.
 +
 
 +
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.
 +
 
 +
==Hexagonal neighbourhood==
 +
{{main|Hexagonal neighbourhood}}
 +
It is possible to define isotropic non-totalistic Life-like 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]];<ref>{{cite web|url=http://www.radicaleye.com/lifepage/hexrule.txt|title=Experiments with a somewhat "Life-like" hexagonal CA (long)|author=Paul Callahan|date=December 3, 1997|accessdate=September 29, 2017}}</ref><ref>{{cite web|url=http://www.conwaylife.com/forums/download/file.php?id=261|title=ExtendedCallahanHexagonal.gif|work=ConwayLife.com forums|accessdate=July 22, 2017}}</ref> the names ''ortho'', ''meta'' and ''para'' were chosen in analogy to [https://en.wikipedia.org/wiki/Arene_substitution_pattern arene substitution patterns] in aromatic chemistry:
 +
 
 +
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
 +
| style="border: none; background: #fff;" |
 +
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6
 
|-
 
|-
! z || || || || || [[File:Neighborhood 4z.png]] || || || ||  
+
! —<small style="font-weight: normal;"> (no<br/>letter)</small>
 +
| [[File:Hexagonal neighborhood 0.png]] || [[File:Hexagonal neighborhood 1.png]] || || || || [[File:Hexagonal neighborhood 5.png]] || [[File:Hexagonal neighborhood 6.png]]
 +
|-
 +
! o<br/><small style="font-weight: normal;">(ortho)</small>
 +
| || || [[File:Hexagonal neighborhood 2o.png]] || [[File:Hexagonal neighborhood 3o.png]] || [[File:Hexagonal neighborhood 4o.png]] || ||
 +
|-
 +
! m<br/><small style="font-weight: normal;">(meta)</small>
 +
| || || [[File:Hexagonal neighborhood 2m.png]] || [[File:Hexagonal neighborhood 3m.png]] || [[File:Hexagonal neighborhood 4m.png]] || ||
 +
|-
 +
! p<br/><small style="font-weight: normal;">(para)</small>
 +
| || || [[File:Hexagonal neighborhood 2p.png]] || [[File:Hexagonal neighborhood 3p.png]] || [[File:Hexagonal neighborhood 4p.png]] || ||  
 
|}
 
|}
  
For instance, B2-a/S12 (the "Just Friends" rule) indicates that a live cell will survival on 1 or 2 neighbors, or a dead cell get born on 2 neighbors, except when they are adjacent.
+
[[Golly]] does not support isotropic non-totalistic hexagonal rules using this syntax, so they must instead be simulated using either rule tables or [[Non-isotropic Life-like cellular automaton|MAP strings]]. [[LifeViewer]] and [[lifelib]] support them natively.
 +
 
 +
== 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.<ref name="post70180" />
 +
 
 +
==Soup-searching non-totalistic rules==
 +
[[Adam P. Goucher]]'s [[apgsearch]] was modified to support isotropic non-totalistic rules by [[Aidan F. Pierce]] on December 17, 2015.<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=9&t=1480&p=25942#p25942|author=Aidan F. Pierce|title=Re: Hacking apgsearch|date=December 17, 2015|accessdate=June 12, 2016|work=ConwayLife.com forums}}</ref> This hacked version was later modified in late January 2016 to be able to upload the search results to [[Catagolue]].<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=7&t=1784&start=225#p26878|author=Adam P. Goucher|title=Re: apgsearch v2.2|date=January 21, 2016|accessdate=June 12, 2016|work=ConwayLife.com forums}}</ref> 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]].<ref name="post50771" /> v4.66 and above also support the searching of isotropic hexagonal neighborhood rules.<ref>{{cite web|title = Re: Non-totalistic hex rules|author  = Adam P. Goucher|date = December 1, 2018|accessdate = December 1, 2018|url = http://www.conwaylife.com/forums/viewtopic.php?p=66090#p66090|work=ConwayLife.com forums}}</ref>
 +
 
 +
==See also==
 +
* [[Totalistic Life-like cellular automaton]]
 +
* [[Non-isotropic Life-like cellular automaton]]
 +
* [[Generations]]
 +
* [[Larger than Life]]
 +
* [[Weighted Life]]
 +
 
 +
==References==
 +
<references>
 +
<ref name="post70180">{{LinkForumThread
 +
|format = ref
 +
|title  = Range-2 von Neumann isotropic non-totalistic rulespace
 +
|p      = 70180
 +
|author = muzik
 +
|date  = February 9, 2019
 +
}}</ref>
 +
<ref name="post50771">{{LinkForumThread
 +
|format = ref
 +
|title  = Re: apgsearch v4.2
 +
|p      = 50771
 +
|author = Adam P. Goucher
 +
|date  = September 10, 2017
 +
}}</ref>
 +
</references>
  
 
==External links==
 
==External links==
 
* {{cite web|author=Alan Hensel|url=http://www.ibiblio.org/lifepatterns/neighbors2.html|title=Table of non-totalistic neighborhoods|accessdate=2016-06-12}}
 
* {{cite web|author=Alan Hensel|url=http://www.ibiblio.org/lifepatterns/neighbors2.html|title=Table of non-totalistic neighborhoods|accessdate=2016-06-12}}
 
* {{cite web|author=Alan Hensel|url=http://www.ibiblio.org/lifepatterns/neighbors.html|title=Rule notation|accessdate=2016-06-12}} (note that the table on this page describes an earlier version of Hensel notation that has fallen into disuse)
 
* {{cite web|author=Alan Hensel|url=http://www.ibiblio.org/lifepatterns/neighbors.html|title=Rule notation|accessdate=2016-06-12}} (note that the table on this page describes an earlier version of Hensel notation that has fallen into disuse)
 +
{{LinkForumThread|f=11|t=936|title=Non-totalistic Rules - notations, projects, & discussion}}
  
[[Category:Cellular automata]]
+
[[Category:Cellular automata| Isotropic non-totalistic Life-like cellular automaton]]
 +
__NOTOC__

Latest revision as of 22:35, 18 August 2019

An isotropic non-totalistic Life-like 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 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 Life-like 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.

Moore neighbourhood

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

A proposed notation for range-2 von Neumann isotropic non-totalistic rules is based on this.

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.

Hexagonal neighbourhood

Main article: Hexagonal neighbourhood

It is possible to define isotropic non-totalistic Life-like 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;[1][2] 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)
Hexagonal neighborhood 0.png Hexagonal neighborhood 1.png Hexagonal neighborhood 5.png Hexagonal neighborhood 6.png
o
(ortho)
Hexagonal neighborhood 2o.png Hexagonal neighborhood 3o.png Hexagonal neighborhood 4o.png
m
(meta)
Hexagonal neighborhood 2m.png Hexagonal neighborhood 3m.png Hexagonal neighborhood 4m.png
p
(para)
Hexagonal neighborhood 2p.png Hexagonal neighborhood 3p.png Hexagonal neighborhood 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.

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.[3]

Soup-searching non-totalistic rules

Adam P. Goucher's apgsearch was modified to support isotropic non-totalistic rules by Aidan F. Pierce on December 17, 2015.[4] This hacked version was later modified in late January 2016 to be able to upload the search results to Catagolue.[5] 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.[6] v4.66 and above also support the searching of isotropic hexagonal neighborhood rules.[7]

See also

References

  1. Paul Callahan (December 3, 1997). "Experiments with a somewhat "Life-like" hexagonal CA (long)". Retrieved on September 29, 2017.
  2. "ExtendedCallahanHexagonal.gif". ConwayLife.com forums. Retrieved on July 22, 2017.
  3. muzik. Range-2 von Neumann isotropic non-totalistic rulespace (discussion thread) at the ConwayLife.com forums
  4. Aidan F. Pierce (December 17, 2015). "Re: Hacking apgsearch". ConwayLife.com forums. Retrieved on June 12, 2016.
  5. Adam P. Goucher (January 21, 2016). "Re: apgsearch v2.2". ConwayLife.com forums. Retrieved on June 12, 2016.
  6. Adam P. Goucher. Re: apgsearch v4.2 (discussion thread) at the ConwayLife.com forums
  7. Adam P. Goucher (December 1, 2018). "Re: Non-totalistic hex rules". ConwayLife.com forums. Retrieved on December 1, 2018.

External links