Thread for basic questions

For general discussion about Conway's Game of Life.
User avatar
dvgrn
Moderator
Posts: 10610
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: 903
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: 429
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: 10610
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.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Thread for basic questions

Post by dani » 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)

User avatar
dvgrn
Moderator
Posts: 10610
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: 535
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: 1496
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
Moderator
Posts: 2932
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: 535
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: 1496
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
Moderator
Posts: 2932
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: 10610
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: 1242
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?
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!

User avatar
Ian07
Moderator
Posts: 891
Joined: September 22nd, 2018, 8:48 am
Location: New Jersey, US

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: 1242
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.
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!

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

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 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.

AforAmpere
Posts: 1334
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 manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

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 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.

AforAmpere
Posts: 1334
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 manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

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: 10610
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

wwei23

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: 10610
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