A map of (half of) all OTCA rules!

For discussion of other cellular automata.
Post Reply
User avatar
Heavpoot
Posts: 45
Joined: August 4th, 2018, 3:58 pm
Contact:

A map of (half of) all OTCA rules!

Post by Heavpoot » March 18th, 2020, 8:20 pm

overlay.png
overlay.png (14.38 KiB) Viewed 6058 times
Each pixel (3x3 square, this has been upscaled by a factor of 3) represents 1 rule!
Purple - Spaceships are proven to not exist, also not explosive (heuristic)
Red - Spaceships are proven to not exist, also explosive (heuristic)
Blue - Spaceships are not disproved from existence, also explosive (heuristic)
Green - Spaceships are not disproved from existence, also not explosive (heuristic)

B0 rules are excluded (due to them having spaceships being hard to theorize about).

How the arrangements of rules works:
Take the X position of the pixel. (divided by 3, due to the upscaling)
Convert it to a 9 bit binary number (e.g 3 becomes 000000011)
Each bit now represents a birth transition (the first bit represents B0, 3 would be B78)
Do the same for the Y position to obtain your rule. For example, B3/S23 can be found at 32, 96 (or due to the upscaling, 96, 228)

The heuristic for whether a rule is explosive or not is not infallible. For example, you may notice a solitary purple dot in the large red area. This is the "fredkin replicator rule", or B1357/S1357. In this rule, every pattern is a replicator, however population experiences regular sharp drops, and the heuristic interprets this as the rule stabilizing (and thus it is not explosive).

Please let me know if you have any suggestions or questions!

User avatar
bubblegum
Posts: 959
Joined: August 25th, 2019, 11:59 pm
Location: click here to do nothing

Re: A map of (half of) all OTCA rules!

Post by bubblegum » March 18th, 2020, 8:33 pm

Code: Select all

x = 1, y = 1, rule = B1357/S1357
o!
This is the replicator rule you mentioned, aptly named "Replicator". Replicator is a rule where everything is a replicator, but you already know that.
So if Replicator (170, 170) is purple, then why not B1357/S02468 (170, 341)?

Code: Select all

x = 1, y = 1, rule = B1357/S02468
o!
Each day is a hidden opportunity, a frozen waterfall that's waiting to be realised, and one that I'll probably be ignoring
sonata wrote:
July 2nd, 2020, 8:33 pm
conwaylife signatures are amazing[citation needed]
anything

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: A map of (half of) all OTCA rules!

Post by Macbi » March 19th, 2020, 7:08 am

You could use the Gray code so that the rules for adjacent pixels only ever differ by one transition.

EDIT: If you wanted you could also order the bits of the Gray code so that the least significant bits (that change most often) represent the transitions that are least likely to affect the colour of a pixel. That way the rules of the same colour would tend to group together.

User avatar
Heavpoot
Posts: 45
Joined: August 4th, 2018, 3:58 pm
Contact:

Re: A map of (half of) all OTCA rules!

Post by Heavpoot » March 19th, 2020, 7:30 am

I don't know the rules for extending the gray code, nor can I find them, though this would be very interesting!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: A map of (half of) all OTCA rules!

Post by Macbi » March 19th, 2020, 7:53 am

Have a look at the 'Converting to and from Gray code' section on that Wikipedia page. You actually only need the very simple BinaryToGray function they give there, which is just n^(n>>1) where ^ is XOR and >>1 is rightshift by 1 (I don't know what you're coding in, but Python would be the same as C). Then for each pixel (x,y), give it the colour that you would have given to (BinaryToGray(x),BinaryToGray(y)).

User avatar
Heavpoot
Posts: 45
Joined: August 4th, 2018, 3:58 pm
Contact:

Re: A map of (half of) all OTCA rules!

Post by Heavpoot » March 19th, 2020, 9:30 am

I wrote a Processing program to rearrange the pixels of the original, and it looks like this:
output.png
output.png (19.63 KiB) Viewed 5991 times
Interestingly, everything is more "square". CGOL can be found at 144, 240 (yes, after the upscaling). Here it is shown in the outlined box.
Screenshot_20200319_132620.png
Screenshot_20200319_132620.png (2.92 KiB) Viewed 5991 times

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A map of (half of) all OTCA rules!

Post by LaundryPizza03 » April 2nd, 2020, 6:22 am

Heavpoot wrote:
March 19th, 2020, 9:30 am
I wrote a Processing program to rearrange the pixels of the original, and it looks like this:output.png
Interestingly, everything is more "square". CGOL can be found at 144, 240 (yes, after the upscaling). Here it is shown in the outlined box.Screenshot_20200319_132620.png
How do I navigate this version of the map?

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A map of (half of) all OTCA rules!

Post by LaundryPizza03 » April 10th, 2020, 9:00 am

Just a few comments.

Spaceships are also known not to exist in rules with B23/S0, S123456, B34/S12345, B345/S1234, and S234567 without B2.

For rules with B0, see this post.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: A map of (half of) all OTCA rules!

Post by wzkchem5 » April 18th, 2020, 12:27 am

Nice work!
A small suggestion: I've read from somewhere about a method that can differentiate Class 4 (potentially Turing complete) automata from other, more "trivial" ones, though I forgot where the original source was. Generate many pairs of random soups on a torus consisting of M cells, so that each pair of soups differ by only a single cell. Simulate the soups for a sufficiently long period of time, and observe how many cells differ in each pair of soups; we denote the latter number by N. Then for Class 1 automata (every pattern eventually die out), N=0; for Class 2 (only still lives and oscillators), N=O(1); for Class 3 (chaotic), N=O(M); and for Class 4, N obeys a continuous distribution from O(1) to O(M). Is it possible to classify the CAs using this method? This will yield information about the potential universality of the CAs, which I believe is more important than the presence or absence of spaceships or explosion.
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: A map of (half of) all OTCA rules!

Post by Hunting » April 18th, 2020, 1:07 am

wzkchem5 wrote:
April 18th, 2020, 12:27 am
Nice work!
A small suggestion: I've read from somewhere about a method that can differentiate Class 4 (potentially Turing complete) automata from other, more "trivial" ones, though I forgot where the original source was. Generate many pairs of random soups on a torus consisting of M cells, so that each pair of soups differ by only a single cell. Simulate the soups for a sufficiently long period of time, and observe how many cells differ in each pair of soups; we denote the latter number by N. Then for Class 1 automata (every pattern eventually die out), N=0; for Class 2 (only still lives and oscillators), N=O(1); for Class 3 (chaotic), N=O(M); and for Class 4, N obeys a continuous distribution from O(1) to O(M). Is it possible to classify the CAs using this method? This will yield information about the potential universality of the CAs, which I believe is more important than the presence or absence of spaceships or explosion.
Nice method! It is easy to make a script based on that.

I have to disagree on the last statement, though. Most of the interesting rules won't show anything interesting after a random Ctrl-5 soup.

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: A map of (half of) all OTCA rules!

Post by wzkchem5 » April 18th, 2020, 4:50 am

Hunting wrote:
April 18th, 2020, 1:07 am
Nice method! It is easy to make a script based on that.

I have to disagree on the last statement, though. Most of the interesting rules won't show anything interesting after a random Ctrl-5 soup.
Yes, but the point is that the method can detect if the CA is Class 4 without needing to construct a universal computer, or even simply a reflector or something. The method just probes whether a small perturbation in the initial condition can generate either small scale, medium scale, or large scale changes in the final pattern. Class 1 and 2 automata do not allow for long-range communication, and you'll see N=O(1); Class 3 automata are so chaotic and experience the butterfly effect, that is even a small perturbation will generate a wholly different final outcome, and you'll see N=O(M). Only in Class 4 automata do you see information flows that can both easily transmit over long distances and easily be stopped, so that you have a broad distribution of N.
Of course, Class 4 phenomena does not imply universality, but as Stephan Wolfram famously pointed out, there is empirically a very strong correlation between the presence of Class 4 phenomena and universality. And that's what I mean by the "potential" universality of the CAs.
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: A map of (half of) all OTCA rules!

Post by Hunting » April 18th, 2020, 7:33 am

wzkchem5 wrote:
April 18th, 2020, 4:50 am
Hunting wrote:
April 18th, 2020, 1:07 am
Nice method! It is easy to make a script based on that.

I have to disagree on the last statement, though. Most of the interesting rules won't show anything interesting after a random Ctrl-5 soup.
Yes, but the point is that the method can detect if the CA is Class 4 without needing to construct a universal computer, or even simply a reflector or something. The method just probes whether a small perturbation in the initial condition can generate either small scale, medium scale, or large scale changes in the final pattern. Class 1 and 2 automata do not allow for long-range communication, and you'll see N=O(1); Class 3 automata are so chaotic and experience the butterfly effect, that is even a small perturbation will generate a wholly different final outcome, and you'll see N=O(M). Only in Class 4 automata do you see information flows that can both easily transmit over long distances and easily be stopped, so that you have a broad distribution of N.
Of course, Class 4 phenomena does not imply universality, but as Stephan Wolfram famously pointed out, there is empirically a very strong correlation between the presence of Class 4 phenomena and universality. And that's what I mean by the "potential" universality of the CAs.
Your method will classify Snowflakes, LeapLife, ATPP and Dominoplex as class 2.

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: A map of (half of) all OTCA rules!

Post by wzkchem5 » April 19th, 2020, 11:45 am

Hunting wrote:
April 18th, 2020, 7:33 am


Your method will classify Snowflakes, LeapLife, ATPP and Dominoplex as class 2.
Sorry but I'm not familiar with the names of these rules. I just learned about Snowflakes and found that it supports guns; therefore chances are that perturbing a single cell of a soup (that will not produce a gun otherwise) may produce a gun, and the gun can induce changes of N>O(1) cells. Did I miss anything?
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: A map of (half of) all OTCA rules!

Post by toroidalet » April 19th, 2020, 4:19 pm

The problem here is choosing the right scale. For example, Life is class 4 with practical soup sizes, but on extremely impractical scales (2^millions), it becomes class 3 due to the formation of junk-clearing replicators and class-3 metacells. The same thing happens with Snowflakes, which is normally class 2, eventually becomes class 4 (due to guns and stuff), and probably transitions into class 3 as well. There is also the possibility of a rule that appears to be class 4 but turns out to just be a really active class 2 rule.

Also, in my experience class-4-ish rules tend to be pretty boring and difficult to search (I used to look for them based on the idea that they would be interesting). What is more indicative of Turing-completeness is the presence of small spaceships and multiple small high-period oscillators. (Also, we don't actually know any ways for something to be universal without spaceships or signals)
Any sufficiently advanced software is indistinguishable from malice.

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: A map of (half of) all OTCA rules!

Post by Hunting » April 19th, 2020, 7:39 pm

P. S. Non-explosive rules supports soup-searching, which is usually the most fruitful search method.

googoIpIex
Posts: 292
Joined: February 28th, 2019, 4:49 pm
Location: Sqrt(-1)

Re: A map of (half of) all OTCA rules!

Post by googoIpIex » May 21st, 2020, 2:25 pm

This is probably unreasonable, but is there a way to do this with non-totalistic rules?

also, bump
woomy on a vroomy

User avatar
Heavpoot
Posts: 45
Joined: August 4th, 2018, 3:58 pm
Contact:

Re: A map of (half of) all OTCA rules!

Post by Heavpoot » May 22nd, 2020, 7:23 am

Hello, sorry, I keep forgetting to check the forums!
googoIpIex wrote:
May 21st, 2020, 2:25 pm
This is probably unreasonable, but is there a way to do this with non-totalistic rules?

also, bump
Well, technically, but you would need a 2251799813685248x2251799813685248 image (still excluding B0), and that seems very unreasonable (if memory serves, there are 51 survival and 51 birth conditions in INT rules!).
LaundryPizza03 wrote:
April 10th, 2020, 9:00 am
Just a few comments.

Spaceships are also known not to exist in rules with B23/S0, S123456, B34/S12345, B345/S1234, and S234567 without B2.

For rules with B0, see this post.
Alright, thank you! I may post an updated version of this soon :D
LaundryPizza03 wrote:
April 2nd, 2020, 6:22 am
How do I navigate this version of the map?
Very late, sorry!
First of all, you need to convert the X and Y position to binary, from greycode (EDIT: downscale them first!). Then, just follow the instructions on the original post:
Heavpoot wrote:
March 18th, 2020, 8:20 pm
Take the X position of the pixel. (divided by 3, due to the upscaling)
Convert it to a 9 bit binary number (e.g 3 becomes 000000011)
Each bit now represents a birth transition (the first bit represents B0, 3 would be B78)
Do the same for the Y position to obtain your rule. For example, B3/S23 can be found at 32, 96 (or due to the upscaling, 96, 228)

User avatar
Heavpoot
Posts: 45
Joined: August 4th, 2018, 3:58 pm
Contact:

A map of all OTCA rules!

Post by Heavpoot » May 22nd, 2020, 9:14 am

UPDATE:
Included more axioms, and all of the B0 axioms (thanks laundrypizza03!) which were very tedious to copy, so hopefully I didn't make any mistakes!

WITHOUT GRAYCODE:
(without graycode)
(without graycode)
img.png (27.1 KiB) Viewed 4892 times
WITH GRAYCODE:
(with graycode)
(with graycode)
output.png (34.75 KiB) Viewed 4892 times

User avatar
DroneBetter
Posts: 94
Joined: December 1st, 2021, 5:16 am
Location: The UK (a delightful place)
Contact:

Re: A map of all OTCA rules!

Post by DroneBetter » August 13th, 2023, 9:29 am

I found this forum thread after making a map of my own (intended for the wiki), I too thank LaundryPizza03 very much.

Firstly, in implementing it I noticed the post with the conditions for strobing rules can be expressed more simply, as the set of rules which do not contain all transitions in at least one member of the set {B1,B2/S0123,B3/S0123,B23/S0,S01234}, but do contain all in at least one of {B/S7,B45678,B5678/S6,B5678/S5,B8/S56}.

Additionally, it uses jedlimlx's spaceship collection, an extension of David Eppstein's glider database. Red pixels are disproven rules, green ones are proven to contain spaceships by the existence of explicit examples.

With some experimentation, I found the best way to arrange it is in a piecewise patchwork function. In all quadrants, the birth conditions are in a Gray code on the x axis, and the survivals on the y.
In the left half, in both the x and y, the 0-transition has maximum precedence, and the 8-transition has minimum.
In the right half, the survival is flipped, and 8 has maximum precedence, because survival becomes equivalent to birth in the bitwise-NOT'ed iteration when it's strobing, and to not-birth in the rules with B0 and S8 (in which the background agar is considered to be all-on, making them duals of half of the left side).
In the bottom-right quadrant, the x's precedence is inverted also, which makes it look much more orderly and less fragmented.
OT_map.png
OT_map.png (17.86 KiB) Viewed 515 times
I also like this one, there are no piecewise parts, birth iterates by standard binary counting with B0 at highest precedence, and survival with S8 at highest, this way you can see the black/white duality amongst all but the bottom-left quadrant (representing B0-less S8 rules, with an empty background agar by convention) through the symmetry of the map.
OT_map_(non-Gray).png
OT_map_(non-Gray).png (21.57 KiB) Viewed 515 times
That concludes my post (I hope you liked it)

Post Reply