Thread for basic questions

[muzik]

Related: how many two-state black-white reversal rules are there (rules like Day & Night)?

Rules that are their own black/white reversal? According to the wiki, 512.

Didn't there used to be a list of said self-complementary rules on the wiki?

[Apple Bottom]

Didn't there used to be a list of said self-complementary rules on the wiki?

Yes. (It's in my userspace because I didn't consider the list sufficiently interesting to warrant a Main namespace article.)

[muzik]

Is there a list (anywhere) that lists the rules where 2x2 blocks simulate other CA using the margolus neighbourhood?

[Apple Bottom]

Is there a list (anywhere) that lists the rules where 2x2 blocks simulate other CA using the margolus neighbourhood?

Not to my (very limited) knowledge, but David Eppstein notes such simulations on his glider page, e.g. here.

[muzik]

This is the only other rule I know of with this property:

Code: Select all

x = 2, y = 2, rule = B1246/S012348
2o$2o!

Code: Select all

x = 4, y = 4, rule = B1246/S012348
4o$4o$2b2o$2b2o!

Can it be proved that every single such rule can be simulated with a totalistic or non-totalistic rule, given that the 2x2 sections are shrunk down to 1x1 and only every second generation is considered?

[Apple Bottom]

This is the only other rule I know of with this property

Here's a few examples from Eppstein's page (this list is probably not exhaustive):

B3/S15
B3/S25
B347/S045
B35678/S5678
B3568/S2567
B36/S1258
B368/S25
B38/S125
B38/S15
B38/S25
B38/S5

If you want to learn more about these, I'd encourage you to ask yourself a few questions and try to answer them yourselves.

How many different Margolus neighborhood CAs are there? Try to enumerate them, and see if you can compute the total number.

What constraints do the B/S conditions of rules that simulate these CAs satisfy? How many such rules are there?

When you have two identical numbers, i.e. "there are x different Margolus neighborhood CAs, and there are also x different ules satisfying the constraints I have worked out", can you show that each such CA is simulated by one of these rules, and vice versa?

Can you come up with a way to "convert" a rule to its equivalent Margolus neighborhood CA, or to "convert" a Margolus neighborhood CA to its equivalent rule?

[muzik]

Are there any ways to play and display RLEs and patterns on the wiki just like on the forums with the code boxes?

[Bullet51]

Given a pattern P and a number k, is the problem of synthesizing P in k gliders decidable?

A stronger version:
Is it possible to enumerate all K-glider collisions? (K is the largest number such that there is something synthesizable by K+1 gliders but not synthesizable by K gliders)

[dvgrn]

Are there any ways to play and display RLEs and patterns on the wiki just like on the forums with the code boxes?

Check out LifeViewer Build 233 (Tiki bar link). This is a work in progress, but it seems very promising so far.

If you have ideas for what should be possible, or shouldn't be possible, starting from a wiki RLE snippet, please go ahead and add it to that discussion!

[dvgrn]

Given a pattern P and a number k, is the problem of synthesizing P in k gliders decidable?

I guess the problem may not be provably undecidable for small k, but nobody is going to be able to prove that it's decidable either, even for k=4. We can't enumerate 4-glider collisions reliably, and until we can there's not much point in looking at k>4 cases.

(Someone please correct me if I'm wrong. I usually am, about things like decidability questions.)

Here's an example of why 4-glider enumeration is a nearly neverending process. Take a 3-glider synthesis of a switch engine -- not the recently-discovered "clean" synthesis, but one of simsim314's messy ones where the switch engine doesn't self-destruct. Now figure out where you can safely stop colliding one more glider into that switch engine. As long as you can produce a big messy explosion that interacts with the entire length of the switch engine's debris, you might get something different by waiting longer to send in that glider.

A stronger version:
Is it possible to enumerate all K-glider collisions? (K is the largest number such that there is something synthesizable by K+1 gliders but not synthesizable by K gliders)

See the "Argh, kickbacks" section of this message:

From the point of view of 4G collisions, that's actually not good enough. A fourth glider could hit a piece of junk, or the last dying spark from let's say the 2-glider-mess reaction, and prolong it for long enough that a very long-delayed kickback glider might do something unique.

Even in the 4-glider case, there's no way to prove that one of those long-delayed kickbacks might not hit the Prolonged 2-Glider Mess and improbably turn it into Pattern P.*

-- Yes, we know that that's too improbable to happen in almost any conceivable case... but we also know how to make arbitrarily high-population "diehard seeds" that are statistically indistinguishable from Prolonged 2-Glider Mess ash. It doesn't seem to me a valid proof will ever be able to find its way around that problem.

-------------------------------

* Well, okay, Pattern P plus N output gliders. But you could shoot those down, making a synthesis of P with 4+N gliders. That doesn't seem to make very much difference to the basic problem.

[toroidalet]

Here's an example of why 4-glider enumeration is a nearly neverending process. Take a 3-glider synthesis of a switch engine -- not the recently-discovered "clean" synthesis, but one of simsim314's messy ones where the switch engine doesn't self-destruct. Now figure out where you can safely stop colliding one more glider into that switch engine. As long as you can produce a big messy explosion that interacts with the entire length of the switch engine's debris, you might get something different by waiting longer to send in that glider.

But this only proves that a depth-first search fails. A breadth-first search (although slower) will not end up fixated on the SE+G explosions.

[dvgrn]

Here's an example of why 4-glider enumeration is a nearly neverending process. Take a 3-glider synthesis of a switch engine -- not the recently-discovered "clean" synthesis, but one of simsim314's messy ones where the switch engine doesn't self-destruct. Now figure out where you can safely stop colliding one more glider into that switch engine. As long as you can produce a big messy explosion that interacts with the entire length of the switch engine's debris, you might get something different by waiting longer to send in that glider.

But this only proves that a depth-first search fails. A breadth-first search (although slower) will not end up fixated on the SE+G explosions.

If you can prove that none of the SE+G explosions produces Pattern P, then maybe breadth-first vs. depth-first could make a difference somehow... though I'm not quite sure how: if it's a complete enumeration, then you'll have to get to all the same cases eventually, either way.

Maybe you can prove that about SE+G, for some target P anyway, if there are unwanted output gliders. Unfortunately you'll also have to be able to prove something similar for all possible Two Interacting Two-Glider-Messes, and for any of the gazillion three-glider methuselahs with a fourth glider added at any point... and so forth and so on.

For any long-lived 3G crash that _doesn't_ produce output gliders or spaceships, how do you prove that it can't be made to settle into your target Pattern P, without trying every possible glider you can hit the active reaction with before it settles? That should give some sense of the size of the problem, and that's just for k=4.

For most P, we know immediately that it's so unlikely that there's no point in bothering to check... but a positive answer to the question would require a provably correct algorithm, not a common-sense statistical argument that's likely to have occasional incredibly rare exceptions.

Here's a related opinion about proofs involving 4-glider and k-glider collisions, from someone with much more respectable mathematical credentials than mine...!

Corollary: producing a complete list of constructions with k gliders is, at least morally, impossible.

Maybe 3-glider collisions can be fully classified (I'm imagining tens of thousands of individual cases together with a few hundred infinite families), but I doubt anyone could ever manage an exhaustive classification of all possible 4-glider collisions.

In particular, I doubt anyone could ever prove the falsity of the following claim:

"There is a 4-glider synthesis of the Caterpillar."

[toroidalet]

Is there any way to join 2 streams of ants?

[drc]

How are oscillator orders determined? Like this? It seems to have a pattern but I can't figure it out.

[wildmyron]

How are oscillator orders determined? Like this? It seems to have a pattern but I can't figure it out.

The comparison method is detailed on the site. This comparison method is used to determine the standard form of objects in Small Object Format.

Is there any way to join 2 streams of ants?

I don't understand what you mean. Can you show what the input and output of the joining process should look like?

[muzik]

How many non-totalistic CA are there?


Also, would I be correct in saying that there are 2^512 non-isotopic CA?

[blah]

... would I be correct in saying that there are 2^512 non-isotopic CA?

No. There are 2^512 2-state CA with moore neighbourhoods, but note that this is a superset of the set of all isotropic 2-state CA with moore neighbourhoods. To get the amount of non-isotropic CA you'd have to subtract one from the other.

[Apple Bottom]

How many non-totalistic CA are there?

Come on, that's high school-level mathematics. It would likely have taken you less time to figure out the answer yourself than to write this post.

Also, would I be correct in saying that there are 2^512 non-isotopic CA?

No, because there's no agreed-on definition of "non-isotopic". ("Non-isotRopic", on the other hand...)

No. There are 2^512 2-state CA with moore neighbourhoods, but note that this is a superset of the set of all isotropic 2-state CA with moore neighbourhoods. To get the amount of non-isotropic CA you'd have to subtract one from the other.

More precisely still, that's 2-state CAs defined on ℤ² using the range-1 Moore neighborhood.

[muzik]

How many non-totalistic CA are there?

Come on, that's high school-level mathematics. It would likely have taken you less time to figure out the answer yourself than to write this post.

So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?

Also, would I be correct in saying that there are 2^512 non-isotopic CA?

No, because there's no agreed-on definition of "non-isotopic". ("Non-isotRopic", on the other hand...)

The next time you see autocorrect, give it a massive slap across the face. Preferably with a cactus.

[Apple Bottom]

So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?

Yes: you're not counting survival conditions.

[muzik]

So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?

Yes: you're not counting survival conditions.

Right, so that would make it 2^102.

[gameoflifemaniac]

How many non-totalistic CA are there?


Also, would I be correct in saying that there are 2^512 non-isotopic CA?

2^64. Since every transition can have 8 different orientations (rotation and reflection), there are 2^64 non-totalistic rules, because 512 divided by 8 is 64.

[dvgrn]

How many non-totalistic CA are there?

Also, would I be correct in saying that there are 2^512 non-isotopic CA?

2^64. Since every transition can have 8 different orientations (rotation and reflection), there are 2^64 non-totalistic rules, because 512 divided by 8 is 64.

Yes, but now you're back to calculating isotropic rules, aren't you? The question was (supposed to be) about non-isotropic rules. Also, some transitions are twofold or fourfold rotationally symmetric, or mirror symmetric, so you can't really just divide like that, you end up with much too small a number. 2^102 is pretty clearly right for isotropic rules, isn't it? That accounts for all the isotropic rule strings that you could possibly generate.

-- This is the problem with the term "non-totalistic". People have been using it to mean "isotropic non-totalistic", but that's not really what it means. If you pick a MAP rule at random, it's definitely not going to be totalistic, probability near zero -- but it's also very very unlikely to be isotropic. Those near-2^512 rules are the full set of (mostly kinda boring) non-totalistic rules.

When these new rule types first started showing up on LifeViewer, I tried to be careful to use "totalistic", "isotropic non-totalistic", "anisotropic non-totalistic" as the three categories, in hopes that people would pick those terms up. But I have to admit those last two are pretty horrible terms.

[calcyman]

How many non-totalistic CA are there?


Also, would I be correct in saying that there are 2^512 non-isotopic CA?

2^64. Since every transition can have 8 different orientations (rotation and reflection), there are 2^64 non-totalistic rules, because 512 divided by 8 is 64.

That same reasoning would lead you to believe that there are 3^(3^9/8) such 3-state rules, which is nonsensical since that number isn't an integer.

[praosylen]

There should be 2^102 isotropic rules in total, 2^101 essentially distinct because every rule has either an ON/OFF dual rule or an ON-OFF-symmetric/strobing dual rule. There should be 2^512 - 2^102 non-isotropic rules, but the number of essentially distinct ones is harder to calculate due to rotations/reflections.