Thread for basic questions

For general discussion about Conway's Game of Life.
muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 8th, 2017, 3:46 pm

Apple Bottom wrote:
gameoflifemaniac wrote: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?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » August 8th, 2017, 3:50 pm

muzik wrote: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.)
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!

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 8th, 2017, 4:20 pm

Is there a list (anywhere) that lists the rules where 2x2 blocks simulate other CA using the margolus neighbourhood?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » August 8th, 2017, 4:23 pm

muzik wrote: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.
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!

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 8th, 2017, 4:28 pm

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?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » August 8th, 2017, 5:46 pm

muzik wrote: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?
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!

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 10th, 2017, 2:52 pm

Are there any ways to play and display RLEs and patterns on the wiki just like on the forums with the code boxes?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

Re: Thread for basic questions

Post by Bullet51 » August 16th, 2017, 2:26 pm

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)
Still drifting.

User avatar
dvgrn
Moderator
Posts: 5874
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » August 16th, 2017, 2:42 pm

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?
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!

User avatar
dvgrn
Moderator
Posts: 5874
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » August 16th, 2017, 3:28 pm

Bullet51 wrote: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.
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)
See the "Argh, kickbacks" section of this message:
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.
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.

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

Re: Thread for basic questions

Post by toroidalet » August 17th, 2017, 11:04 am

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.
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.
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

User avatar
dvgrn
Moderator
Posts: 5874
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » August 17th, 2017, 11:27 am

toroidalet wrote:
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.
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...!
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."

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

Re: Thread for basic questions

Post by toroidalet » August 22nd, 2017, 10:57 pm

Is there any way to join 2 streams of ants?
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

User avatar
drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: Thread for basic questions

Post by drc » August 24th, 2017, 2:24 am

How are oscillator orders determined? Like this? It seems to have a pattern but I can't figure it out.
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y

wildmyron
Posts: 1272
Joined: August 9th, 2013, 12:45 am

Re: Thread for basic questions

Post by wildmyron » August 24th, 2017, 3:25 am

drc wrote: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.
toroidalet wrote: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?
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 24th, 2017, 5:51 am

How many non-totalistic CA are there?


Also, would I be correct in saying that there are 2^512 non-isotopic CA?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
blah
Posts: 244
Joined: April 9th, 2016, 7:22 pm

Re: Thread for basic questions

Post by blah » August 24th, 2017, 6:26 am

muzik wrote:... 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.
succ

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » August 24th, 2017, 7:19 am

muzik wrote: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...)
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.
More precisely still, that's 2-state CAs defined on ℤ² using the range-1 Moore neighborhood. ;)
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!

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 24th, 2017, 8:21 am

Apple Bottom wrote:
muzik wrote: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?
Apple Bottom wrote:
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.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » August 24th, 2017, 9:35 am

muzik wrote: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.
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!

muzik
Posts: 3499
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » August 24th, 2017, 11:06 am

Apple Bottom wrote:
muzik wrote: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.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!

User avatar
gameoflifemaniac
Posts: 774
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Post by gameoflifemaniac » August 24th, 2017, 2:09 pm

muzik wrote: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.
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...

User avatar
dvgrn
Moderator
Posts: 5874
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » August 24th, 2017, 2:30 pm

gameoflifemaniac wrote:
muzik wrote: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.

User avatar
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » August 24th, 2017, 2:43 pm

gameoflifemaniac wrote:
muzik wrote: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.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
A for awesome
Posts: 1901
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

Re: Thread for basic questions

Post by A for awesome » August 24th, 2017, 5:40 pm

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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

Post Reply