Page 48 of 192
Re: Thread for basic questions
Posted: October 19th, 2018, 12:11 pm
by dvgrn
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 (!)
Re: Thread for basic questions
Posted: October 19th, 2018, 1:08 pm
by Macbi
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.
Re: Thread for basic questions
Posted: October 19th, 2018, 7:48 pm
by Redstoneboi
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
Re: Thread for basic questions
Posted: October 19th, 2018, 9:02 pm
by dvgrn
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.
Re: Thread for basic questions
Posted: October 19th, 2018, 9:04 pm
by dani
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)
Re: Thread for basic questions
Posted: October 19th, 2018, 9:42 pm
by dvgrn
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!
Re: Thread for basic questions
Posted: October 22nd, 2018, 2:38 am
by KittyTac
How big is the LTL rulespace for R < 100?
Re: Thread for basic questions
Posted: October 22nd, 2018, 3:08 am
by 77topaz
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.
Re: Thread for basic questions
Posted: October 22nd, 2018, 7:46 am
by calcyman
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).
Re: Thread for basic questions
Posted: October 22nd, 2018, 10:02 am
by KittyTac
I meant the Golly-accessible LTL rules with R < 100, rather than all LTL rules with R < 100.
Re: Thread for basic questions
Posted: October 22nd, 2018, 5:30 pm
by 77topaz
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...
Re: Thread for basic questions
Posted: October 27th, 2018, 6:59 pm
by calcyman
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.
Re: Thread for basic questions
Posted: October 27th, 2018, 7:46 pm
by dvgrn
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.
Re: Thread for basic questions
Posted: November 3rd, 2018, 3:05 pm
by gameoflifemaniac
What type of variable are the population and generation count in Golly?
Re: Thread for basic questions
Posted: November 3rd, 2018, 3:13 pm
by Ian07
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.
Re: Thread for basic questions
Posted: November 3rd, 2018, 4:57 pm
by gameoflifemaniac
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.
Re: Thread for basic questions
Posted: November 3rd, 2018, 7:32 pm
by wildmyron
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.
Re: Thread for basic questions
Posted: November 6th, 2018, 11:06 am
by AforAmpere
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.
Re: Thread for basic questions
Posted: November 6th, 2018, 11:41 am
by wildmyron
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:
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.
Re: Thread for basic questions
Posted: November 6th, 2018, 12:18 pm
by AforAmpere
Command:
What was posted above was the only output.
Re: Thread for basic questions
Posted: November 9th, 2018, 8:09 pm
by 2718281828
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.
Re: Thread for basic questions
Posted: November 10th, 2018, 12:22 am
by dvgrn
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.
Re: Thread for basic questions
Posted: November 10th, 2018, 12:25 pm
by M. I. Wright
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
Re: Thread for basic questions
Posted: November 10th, 2018, 5:05 pm
by wwei23
Is there any way to get betas like Golly 3.2b1?
Re: Thread for basic questions
Posted: November 10th, 2018, 5:42 pm
by dvgrn
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.