On Wed, 20 Oct 2021 02:56:21 +0300, Stefan W wrote:
Let's count a number of rules that can be built in GoL-like automatas.
Rule is the matrix that maps some condition of cells to new state.
Cell itself could be alive or dead. And cell could have 0-8 neighbors.
So, there are 2^(2*9) = 262144 different rules. Well known, that the
majority of them are primitive and produces some pure pattern or just
dies in finite number of generations / infinitely fills the world with
alive cells. We also know that some rules are symmetric to each other as
if we just rename (swap colors of) alive and dead cells.
Conway found the most interesting rule from entropy point of view.
2^18 is not so much. Let's take a look at 2D automata known as Rule 110. State 100 keeps cell dead:
100 -> 0
While state 001 makes cell alive:
001 -> 1
In terms of neighborhood, this two rules are indifferent: both means one
live neighbor next to dead cell. But in Rule 110 not only a /number/ of neighbors is meaningful, but the /position/ of separate neighbor.
Let's imagine the GoL-like rule with the same property: we will look not
only at number of neighbors, but at their position. What if to have one neighbor at north-west gives not the same result as if neighbor were at south-east.
This change gives us much more different rules. If each neighbor is meaningful, then we have 2 ^ 8 different states of neighborhood, and
cell could be still alive or dead. If I'm not wrong there must be 2 ^ (2
* (2 ^ 8)) = 2 ^ 512 different rules.
Obviously, this space includes Conway's Game of Life and all different
rules from that 262144, and gives billions of new ones. Obviously the majority of them are trivial too. But there may be some interesting entropy-like rules different from the Conway's one.
This space is too huge to be discovered manually, and even with
bruteforce algorithms too. But evolution algorithms could be used to
find rules with some special properties.
So, I have two questions:
1) Does this space has a given name, anybody researched that?
2) I will be glad to hear any ideas on how to make this space simpler by excluding symmetric states etc. to save the time for discovering.
Quick disclaimer: I'm not a mathematician working on Cellular Automata,
but a hobbyist participating in a Cellular Automata community, so some nomenclature may differ from that accepted in the mathematics community.
1) I've seen this space colloqually referred to as MAP (presumably since
it maps a 3x3 neighborhood into a future cell state), or more precisely
and if you want to be pedantic, since there are a lot of variants of
cellular automata: 2D Range-1 Moore neighborhood 2-state (non-totalistic) cellular automata (regular euclidean grid implied, although some people
explore toroidal configurations, nonstandard tilings, or arbitrary
graphs).
Changing any of these parameters results in various interesting rulespaces
that other people have explored quite deeply.
2) This is referred to as INT - Isotropic Non-Totalistic Cellular
Automata. The isotropy means all patterns behave the same regardless of orientation in space, they can be flipped or rotated without changing
their behavior. This makes the MAP space much more manageable to explore,
but still contains many rich and interesting rules.
There are several online communities that explore cellular automata like
these. The biggest one I know of is conwaylife.com. It includes a very
useful wiki and web forum where rules, rulespaces, search programs, discoveries, etc. are discussed.
The standard software for exploring cellular automata rules and patterns
is Golly, which supports both these mentioned rulespaces and many more, including completely custom ones. Many people in the community write their
own tools that allow things like encoding various problems or searches as boolean SAT problems, which an off-the-shelf SAT solver can usually solve.
This is usually done to search for patterns or rules that satisfy some property.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)