ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Thread for basic questions

For general discussion about Conway's Game of Life.

Re: Thread for basic questions

Postby 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
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby 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
Macbi
 
Posts: 685
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Postby 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
Redstoneboi
 
Posts: 340
Joined: May 14th, 2018, 3:57 am

Re: Thread for basic questions

Postby 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
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby 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 // Please stop using my full name. Refer to me as dani.

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.
User avatar
danny
 
Posts: 960
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA

Re: Thread for basic questions

Postby 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
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby KittyTac » October 22nd, 2018, 2:38 am

How big is the LTL rulespace for R < 100?
User avatar
KittyTac
 
Posts: 533
Joined: December 21st, 2017, 9:58 am

Re: Thread for basic questions

Postby 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
77topaz
 
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Postby 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
calcyman
 
Posts: 2072
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Postby 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
KittyTac
 
Posts: 533
Joined: December 21st, 2017, 9:58 am

Re: Thread for basic questions

Postby 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
77topaz
 
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Postby 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
calcyman
 
Posts: 2072
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Postby 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
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby 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...
User avatar
gameoflifemaniac
 
Posts: 762
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Postby 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.
Ian07
 
Posts: 280
Joined: September 22nd, 2018, 8:48 am

Re: Thread for basic questions

Postby 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...
User avatar
gameoflifemaniac
 
Posts: 762
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Postby 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 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron
 
Posts: 1209
Joined: August 9th, 2013, 12:45 am

Re: Thread for basic questions

Postby 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:
/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)
AforAmpere
 
Posts: 1041
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby 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:
<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 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron
 
Posts: 1209
Joined: August 9th, 2013, 12:45 am

Re: Thread for basic questions

Postby AforAmpere » November 6th, 2018, 12:18 pm

Command:
$ 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)
AforAmpere
 
Posts: 1041
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Postby 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
2718281828
 
Posts: 735
Joined: August 8th, 2017, 5:38 pm

Re: Thread for basic questions

Postby 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:
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.
User avatar
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Thread for basic questions

Postby 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'
M. I. Wright
 
Posts: 371
Joined: June 13th, 2015, 12:04 pm

Re: Thread for basic questions

Postby wwei23 » November 10th, 2018, 5:05 pm

Is there any way to get betas like Golly 3.2b1?
User avatar
wwei23
 
Posts: 936
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: Thread for basic questions

Postby 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.
User avatar
dvgrn
Moderator
 
Posts: 5746
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 4 guests