Thread for basic questions

For general discussion about Conway's Game of Life.
User avatar
dvgrn
Moderator
Posts: 5891
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » October 19th, 2018, 12:11 pm

danny wrote:Can it be proven that amount of still lifes with n cells never exceeds the amount of n glider syntheses?

is there some sort of equation or upper bound for either of these quantities?
Well... there's a difference between "number of n-glider syntheses" and "number of n-glider syntheses that have any decent likelihood of producing the still life you want". But either of those pretty clearly grows faster than the number of N-bit still lifes.

There seem to be about 2.5 times as many (N+1) bit still lifes as N-bit still lifes. See still life. For glider syntheses we only have a few data points, but they make a pretty clear picture: GS(2) = 71, GS(3) = about 500,000, and GS(35 or above) = infinity (!)

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

Re: Thread for basic questions

Post by Macbi » October 19th, 2018, 1:08 pm

danny wrote:Can it be proven that amount of still lifes with n cells never exceeds the amount of n glider syntheses?

is there some sort of equation or upper bound for either of these quantities?
There are only finitely many strict still lives with n cells, but if n-1 gliders suffice to construct an infinite growth pattern then there are infinitely many n glider syntheses.

User avatar
Redstoneboi
Posts: 344
Joined: May 14th, 2018, 3:57 am

Re: Thread for basic questions

Post by Redstoneboi » October 19th, 2018, 7:48 pm

Macbi wrote:
danny wrote:Can it be proven that amount of still lifes with n cells never exceeds the amount of n glider syntheses?

is there some sort of equation or upper bound for either of these quantities?
There are only finitely many strict still lives with n cells, but if n-1 gliders suffice to construct an infinite growth pattern then there are infinitely many n glider syntheses.
if we can synthesize all (x<36) cell still lives with <x gliders then yes it’s possible because any amount of gliders can be done using the 35 glider reverse caber tosser
c(>^w^<c)~*
This is 「Fluffy」
「Fluffy」is my sutando.
「Fluffy」has the ability to engineer r e p l i c a t o r s.
「Fluffy」likes to watch spaceship guns in Golly.
「Fluffy」knows Natsuki best girl.

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

Re: Thread for basic questions

Post by dvgrn » October 19th, 2018, 9:02 pm

Redstoneboi wrote:if we can synthesize all (x<36) cell still lives with <x gliders then yes it’s possible because any amount of gliders can be done using the 35 glider reverse caber tosser
There would only be one hole left in a proof that all N-cell still lifes can be synthesized in less than N gliders. Unfortunately it's a big hole: you have to show that all possible still lifes can be synthesized with some number of gliders. There might still be a still-life solution to the unique-father problem out there somewhere.

User avatar
danny
Posts: 968
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA
Contact:

Re: Thread for basic questions

Post by danny » October 19th, 2018, 9:04 pm

dvgrn wrote:
Redstoneboi wrote:if we can synthesize all (x<36) cell still lives with <x gliders then yes it’s possible because any amount of gliders can be done using the 35 glider reverse caber tosser
There would only be one hole left in a proof that all N-cell still lifes can be synthesized in less than N gliders. Unfortunately it's a big hole: you have to show that all possible still lifes can be synthesized with some number of gliders. There might still be a still-life solution to the unique-father problem out there somewhere.
How would I go about searching for a still life without parents? Should I try writing a script? Or even, dare I say, a distributed computing project? (the last part of that sentence is purely hypothetical as I cannot program well enough or pay for a website)
she/they // dani

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.

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

Re: Thread for basic questions

Post by dvgrn » October 19th, 2018, 9:42 pm

danny wrote:How would I go about searching for a still life without parents? Should I try writing a script? Or even, dare I say, a distributed computing project? (the last part of that sentence is purely hypothetical as I cannot program well enough or pay for a website)
I'm afraid that anyone who could answer that question in enough detail, would probably have written the script already.

It's a tricky problem. All still lifes have one parent, so you have to run something like a JLS predecessor search to prove that there aren't any other parents... but you can't just run a search on a small part of it and show that nothing can change in that limited context. Maybe that small part changes, and at the same time the area around it changes, and you might have a predecessor after all.

Maybe something similar to Nicolay Beluchenko's GoE search program? Add cells consistent with stability around the edge of a pattern, always picking the choice such that the number of predecessors increases as little as possible, or even decreases. That would be a painfully slow search -- you'd have to run a full lifesrc-type scan for predecessors, for each possible addition, and the number of possibilities keeps increasing as the object gets bigger.

The unique-father problem might actually be even more painful than the constructibility-by-gliders problem. We could maybe come up with some delicately balanced still life where we can show that such-and-such key cells can't ever be OFF, because that would cause a lightspeed collapse of some hard-to-reach central area. Something like that, anyway. But it's very hard to make it so every cell is a key cell, and absolutely no alternate predecessors can be found even if they're Gardens of Eden. GoE parents wouldn't be any help in finding a glider construction, but they'd still disqualify a unique-father candidate.

... TL;DR: Just prove omniperiodicity instead, it's much easier!

User avatar
KittyTac
Posts: 533
Joined: December 21st, 2017, 9:58 am

Re: Thread for basic questions

Post by KittyTac » October 22nd, 2018, 2:38 am

How big is the LTL rulespace for R < 100?

User avatar
77topaz
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Post by 77topaz » October 22nd, 2018, 3:08 am

KittyTac wrote:How big is the LTL rulespace for R < 100?
Including non-isotropic rules, it would be on the order of the sum over n from 1 to 100 of 2^(2*n^2), which is approximately 4 * 10^6020. With only isotropic rules, it would be a lot smaller, but still very big - a lower bound being the sum for 1/8 the number of possible neighbourhoods (reflecting and rotating), giving the sum for 2^((1/4)*n^2), which is approximately 4 * 10^752.

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

Re: Thread for basic questions

Post by calcyman » October 22nd, 2018, 7:46 am

77topaz wrote:
KittyTac wrote:How big is the LTL rulespace for R < 100?
Including non-isotropic rules, it would be on the order of the sum over n from 1 to 100 of 2^(2*n^2)
I think it's much larger than that: 2^(2^((2R+1)^2)) for MAP rules. Incredibly, that means that even when R = 9, the number of MAP rules is 2^(2^361). When you restrict to isotropic radius-9 rules, the number of neighbourhoods still exceeds 2^358 (by taking the largest term in Burnside's formula and ignoring the others), so the number of isotropic rules exceeds 2^(2^358) > 10^(10^108) -- and is therefore slightly larger than a googolplex.

The number of rules theoretically supported by lifelib (2^64-state non-B0 rules with range-8 neighbourhood) is (2^64) ^ ((2^64)^289 - 1).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
KittyTac
Posts: 533
Joined: December 21st, 2017, 9:58 am

Re: Thread for basic questions

Post by KittyTac » October 22nd, 2018, 10:02 am

I meant the Golly-accessible LTL rules with R < 100, rather than all LTL rules with R < 100.

User avatar
77topaz
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Post by 77topaz » October 22nd, 2018, 5:30 pm

Oh right, 2^(2*(n+1)^2) would be the number of possible neighbourhood configurations in range n, so the number of possible rules would be 2^that, and the +1's there because range 1 gives a 3x3 neighbourhood, range 2 5x5...

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

Re: Thread for basic questions

Post by calcyman » October 27th, 2018, 6:59 pm

Does anyone have a recipe to 'undo' a Snarkmaker?

With that, it would be possible for slsparse to build patterns where some of the circuitry is directly on top of the construction channel (without any exponential inefficiency incurred by freeze-dried salvos or suchlike). Dave Greene has e-mailed me a use-case that would benefit from being able to do this.
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: Thread for basic questions

Post by dvgrn » October 27th, 2018, 7:46 pm

calcyman wrote:Does anyone have a recipe to 'undo' a Snarkmaker?

With that, it would be possible for slsparse to build patterns where some of the circuitry is directly on top of the construction channel (without any exponential inefficiency incurred by freeze-dried salvos or suchlike). Dave Greene has e-mailed me a use-case that would benefit from being able to do this.
Yes, we've had those for a while now -- the first single-channel Demonoids and the first Orthogonoids both use a Snarkbreaker invented by chris_c and simeks a while back (June 2017). The actual gliders are included at the end of this recipe, for example.

(I've been calling the recipe "Snark-destroy" -- silly me! "Snarkbreaker" is much better.)

I'll post the standard single-channel timing offset numbers once I dig them up again. I often just copy in that part of the recipe by hand, then adjust the long delay to match whatever the current elbow position happens to be.

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

Re: Thread for basic questions

Post by gameoflifemaniac » November 3rd, 2018, 3:05 pm

What type of variable are the population and generation count in Golly?
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...

Ian07
Posts: 353
Joined: September 22nd, 2018, 8:48 am

Re: Thread for basic questions

Post by Ian07 » November 3rd, 2018, 3:13 pm

gameoflifemaniac wrote:What type of variable are the population and generation count in Golly?
Assuming you're referring to the getpop() and getgen() functions for scripting, they both return the number as a string, but you can convert it to a number with tonumber(s) in Lua, or int(s) or float(s) in Python.

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

Re: Thread for basic questions

Post by gameoflifemaniac » November 3rd, 2018, 4:57 pm

Ian07 wrote:
gameoflifemaniac wrote:What type of variable are the population and generation count in Golly?
Assuming you're referring to the getpop() and getgen() functions for scripting, they both return the number as a string, but you can convert it to a number with tonumber(s) in Lua, or int(s) or float(s) in Python.
I mean them themselves.
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...

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

Re: Thread for basic questions

Post by wildmyron » November 3rd, 2018, 7:32 pm

gameoflifemaniac wrote:What type of variable are the population and generation count in Golly?
Golly uses a custom bigint type, defined here https://sourceforge.net/p/golly/code/ci ... e/bigint.h for both of these properties.
Essentially, int32 for values that fit, and an array of ints for larger values.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

AforAmpere
Posts: 1049
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » November 6th, 2018, 11:06 am

I was previously able to compile gfind and other C programs, but suddenly I wasn't able to, and this error popped up:

Code: Select all

/tmp/cc4T1Mc8.o:gfind.c:(.text+0x4d0): undefined reference to `qIsEmpty'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x4d0): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `qIsEmpty'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x92d): undefined reference to `enqueue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x92d): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `enqueue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x978): undefined reference to `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x978): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3abb): undefined reference to `isVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3abb): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `isVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3ad0): undefined reference to `enqueue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3ad0): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `enqueue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b20): undefined reference to `pop'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b20): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `pop'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b39): undefined reference to `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b39): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b52): undefined reference to `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x3b52): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `setVisited'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x5bfe): undefined reference to `pop'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x5bfe): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `pop'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x601e): undefined reference to `dequeue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x601e): relocation truncated to fit: R_X86_64_PC32 against undefined symbol `dequeue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x6037): undefined reference to `qIsEmpty'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x6037): additional relocation overflows omitted from the output
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x62ec): undefined reference to `enqueue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x634f): undefined reference to `dequeue'
/tmp/cc4T1Mc8.o:gfind.c:(.text+0x6358): undefined reference to `enqueue'
collect2: error: ld returned 1 exit status
It doesn't really make much sense, can anyone figure out what is happening? This is Windows Cygwin by the way.
I and wildmyron manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule
- Finish a rule with ships with period >= f_e_0(n) (in progress)

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

Re: Thread for basic questions

Post by wildmyron » November 6th, 2018, 11:41 am

AforAmpere wrote:I was previously able to compile gfind and other C programs, but suddenly I wasn't able to, and this error popped up:

Code: Select all

<snip linker errors>
It doesn't really make much sense, can anyone figure out what is happening? This is Windows Cygwin by the way.
I don't think I'll be able to help, but would you please provide the command used and the compiler output in addition to the linker errors. It seems very strange to me that the linker can't find references to names which are defined in the very compilation unit which it is linking if there were no other issues.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

AforAmpere
Posts: 1049
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » November 6th, 2018, 12:18 pm

Command:

Code: Select all

$ gcc -o gfind gfind.c
What was posted above was the only output.
I and wildmyron manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule
- Finish a rule with ships with period >= f_e_0(n) (in progress)

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Thread for basic questions

Post by 2718281828 » November 9th, 2018, 8:09 pm

Wiki states here http://www.conwaylife.com/wiki/Half-bakery that:
"The only other known reactions of this type involve stable reflectors, which have a displacement of (0,0), alongside a constellation of three blocks"
What is this 3-block constellation? I can't find a reference for it.

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

Re: Thread for basic questions

Post by dvgrn » November 10th, 2018, 12:22 am

2718281828 wrote:Wiki states here http://www.conwaylife.com/wiki/Half-bakery that:
"The only other known reactions of this type involve stable reflectors, which have a displacement of (0,0), alongside a constellation of three blocks"
What is this 3-block constellation? I can't find a reference for it.
Will find it tomorrow. If you don't want to wait that long, I do remember that oddly enough, it's a 3-block constellation that you can get by crashing a glider into a half-blockade. When you hit the constellation with the right glider, you get a mirror-image three blocks and an output glider.

EDIT:

Code: Select all

x = 96, y = 48, rule = B3/S23
94bo$93bo$93b3o34$6b2o$6b2o2b2o$10b2o41b2o$53b2o6$3o50b2o4b2o$2bo50b2o
4b2o$bo!
The obligatory oscillator was built a very long time ago, though it could be re-done now with Snarks and syringes and such. I think these postings might have been the last time it came up on the forums, which was after Snarks but before syringes. Now I wish I'd reposted the original oscillator built using this, since I seem to be having a hard time re-finding it.

M. I. Wright
Posts: 372
Joined: June 13th, 2015, 12:04 pm

Re: Thread for basic questions

Post by M. I. Wright » November 10th, 2018, 12:25 pm

It's come up a few times since. Last year, David Bell posted a Snark-enhanced redo of the old osc: viewtopic.php?f=2&t=1437&p=52309#p52303
gamer54657 wrote:God save us all.
God save humanity.

hgkhjfgh
nutshelltlifeDiscord 'Conwaylife Lounge'

User avatar
wwei23
Posts: 936
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: Thread for basic questions

Post by wwei23 » November 10th, 2018, 5:05 pm

Is there any way to get betas like Golly 3.2b1?

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

Re: Thread for basic questions

Post by dvgrn » November 10th, 2018, 5:42 pm

wwei23 wrote:Is there any way to get betas like Golly 3.2b1?
No, not unless the relevant link on trevorrow.com still works -- but Andrew is usually pretty good about cleaning them up as soon as they're out of date -- or unless someone has kept a copy for some reason and is willing to make it available.

It doesn't seem like there would be much use for an archive of these things, since either they're identical to the release version (if no bugs are found)... or else they contain known bugs that have been fixed.

Post Reply