Didn't there used to be a list of said self-complementary rules on the wiki?Apple Bottom wrote:Rules that are their own black/white reversal? According to the wiki, 512.gameoflifemaniac wrote:Related: how many two-state black-white reversal rules are there (rules like Day & Night)?
Thread for basic questions
Re: Thread for basic questions
Help wanted: How can we accurately notate any 1D replicator?
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
Yes. (It's in my userspace because I didn't consider the list sufficiently interesting to warrant a Main namespace article.)muzik wrote:Didn't there used to be a list of said self-complementary rules on the wiki?
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
Is there a list (anywhere) that lists the rules where 2x2 blocks simulate other CA using the margolus neighbourhood?
Help wanted: How can we accurately notate any 1D replicator?
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
Not to my (very limited) knowledge, but David Eppstein notes such simulations on his glider page, e.g. here.muzik wrote:Is there a list (anywhere) that lists the rules where 2x2 blocks simulate other CA using the margolus neighbourhood?
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
This is the only other rule I know of with this property:
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?
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!
Help wanted: How can we accurately notate any 1D replicator?
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
Here's a few examples from Eppstein's page (this list is probably not exhaustive):muzik wrote:This is the only other rule I know of with this property
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?
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
Are there any ways to play and display RLEs and patterns on the wiki just like on the forums with the code boxes?
Help wanted: How can we accurately notate any 1D replicator?
Re: Thread for basic questions
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)
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)
Still drifting.
Re: Thread for basic questions
Check out LifeViewer Build 233 (Tiki bar link). This is a work in progress, but it seems very promising so far.muzik wrote:Are there any ways to play and display RLEs and patterns on the wiki just like on the forums with the code boxes?
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!
Re: Thread for basic questions
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.Bullet51 wrote:Given a pattern P and a number k, is the problem of synthesizing P in k gliders decidable?
(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.
See the "Argh, kickbacks" section of this message:Bullet51 wrote: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)
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.*dvgrn wrote: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.
-- 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
- Posts: 1514
- Joined: August 7th, 2016, 1:48 pm
- Location: My computer
- Contact:
Re: Thread for basic questions
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 wrote: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.
Any sufficiently advanced software is indistinguishable from malice.
Re: Thread for basic questions
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.toroidalet wrote: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 wrote: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.
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...!
calcyman wrote: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
- Posts: 1514
- Joined: August 7th, 2016, 1:48 pm
- Location: My computer
- Contact:
Re: Thread for basic questions
Is there any way to join 2 streams of ants?
Any sufficiently advanced software is indistinguishable from malice.
Re: Thread for basic questions
How are oscillator orders determined? Like this? It seems to have a pattern but I can't figure it out.
Re: Thread for basic questions
The comparison method is detailed on the site. This comparison method is used to determine the standard form of objects in Small Object Format.drc wrote:How are oscillator orders determined? Like this? It seems to have a pattern but I can't figure it out.
I don't understand what you mean. Can you show what the input and output of the joining process should look like?toroidalet wrote:Is there any way to join 2 streams of ants?
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.
Semi-active here - recovering from a severe case of LWTDS.
Semi-active here - recovering from a severe case of LWTDS.
Re: Thread for basic questions
How many non-totalistic CA are there?
Also, would I be correct in saying that there are 2^512 non-isotopic CA?
Also, would I be correct in saying that there are 2^512 non-isotopic CA?
Help wanted: How can we accurately notate any 1D replicator?
Re: Thread for basic questions
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.muzik wrote:... would I be correct in saying that there are 2^512 non-isotopic CA?
succ
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
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.muzik wrote:How many non-totalistic CA are there?
No, because there's no agreed-on definition of "non-isotopic". ("Non-isotRopic", on the other hand...)Also, would I be correct in saying that there are 2^512 non-isotopic CA?
More precisely still, that's 2-state CAs defined on ℤ² using the range-1 Moore neighborhood.blah wrote: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.
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?Apple Bottom wrote: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.muzik wrote:How many non-totalistic CA are there?
The next time you see autocorrect, give it a massive slap across the face. Preferably with a cactus.Apple Bottom wrote:No, because there's no agreed-on definition of "non-isotopic". ("Non-isotRopic", on the other hand...)Also, would I be correct in saying that there are 2^512 non-isotopic CA?
Help wanted: How can we accurately notate any 1D replicator?
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: Thread for basic questions
Yes: you're not counting survival conditions.muzik wrote:So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?
If you speak, your speech must be better than your silence would have been. — Arabian proverb
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
Right, so that would make it 2^102.Apple Bottom wrote:Yes: you're not counting survival conditions.muzik wrote:So since there's 51 different birth conditions, that would be 2^51. Am I making any mistakes here?
Help wanted: How can we accurately notate any 1D replicator?
- gameoflifemaniac
- Posts: 1242
- Joined: January 22nd, 2017, 11:17 am
- Location: There too
Re: Thread for basic questions
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.muzik wrote:How many non-totalistic CA are there?
Also, would I be correct in saying that there are 2^512 non-isotopic CA?
I was so socially awkward in the past and it will haunt me for the rest of my life.
Code: Select all
b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!
Re: Thread for basic questions
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.gameoflifemaniac wrote: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.muzik wrote:How many non-totalistic CA are there?
Also, would I be correct in saying that there are 2^512 non-isotopic CA?
-- 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.
Re: Thread for basic questions
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.gameoflifemaniac wrote: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.muzik wrote:How many non-totalistic CA are there?
Also, would I be correct in saying that there are 2^512 non-isotopic CA?
What do you do with ill crystallographers? Take them to the mono-clinic!
- praosylen
- Posts: 2443
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: Thread for basic questions
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.
former username: A for Awesome
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...