On a similar vein, what B3 totalistic rules allow C/2? B3478/S15678 seems to only allow speeds up to C/3 orthogonal, but for some reason C/4 diagonal.danny wrote:Are spaceships faster than c/3 really impossible in justfriends? Is there a proof?
Thread for basic questions

 Posts: 1080
 Joined: July 1st, 2016, 3:58 pm
Re: Thread for basic questions
I and wildmyron manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
 Finish a rule with ships with period >= f_e_0(n) (in progress)
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
 Finish a rule with ships with period >= f_e_0(n) (in progress)
 cordership3
 Posts: 128
 Joined: August 23rd, 2016, 8:53 am
 Location: haha long boy
Re: Thread for basic questions
Would it be practical at all to make a version of apgsearch that works in a browser?
fg
 Apple Bottom
 Posts: 1027
 Joined: July 27th, 2015, 2:06 pm
 Contact:
Re: Thread for basic questions
Not entirely impractical, I'd guess, as you could take the current C++ codebase, replace the assembly language bits with C++ code, and then compile the whole shebang for asm.js. (This obviously leaves out a lot of work that would have to be done, still.)cordership3 wrote:Would it be practical at all to make a version of apgsearch that works in a browser?
I think the bigger question is: whyever would you want to?
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
 Majestas32
 Posts: 524
 Joined: November 20th, 2017, 12:22 pm
 Location: 'Merica
Re: Thread for basic questions
1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation
1a. With/without leaving behind debris showing every generation
moose#0915
Re: Thread for basic questions
Hmm... Naszvadi's rule110 guns in his Turingcompleteness thread have a somewhat similar concept to that.danny wrote:1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation
Re: Thread for basic questions
When Calcyman gets done compiling his replicatormegapixel, it will be trivial to program it to emulate various CA rules, so you can get all kinds of behavior along these lines.danny wrote:1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation
That's going to be an impressively huge pattern, though. For something slightly more reasonable sized, maybe modify the selfsynthesizing spaceship idea  just knock out the selfdestruct part, and it's certainly a puffer. It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.
Re: Thread for basic questions
I meant like a puffer that evolves a pattern specified by gliders or otherwise and puffs its evolution out onto the grid. So it would look like:dvgrn wrote:It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.
Code: Select all
x = 45, y = 4, rule = B3/S23
21bo9b2o$2o8b3o8b2o7b3o$b2o9bo7bo2bo6bo2bo6bobobo$bo9b2o8b2o8b2o!
moose#0915
Re: Thread for basic questions
Hmm... I can imagine a metapixelpuffer doing that for a onedimensional CA, but it would be rather more difficult for a twodimensional one. You'd have to specify a fixed bounding box for the pattern for that to work, I think.danny wrote:I meant like a puffer that evolves a pattern specified by gliders or otherwise and puffs its evolution out onto the grid. So it would look like:dvgrn wrote:It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.Code: Select all
x = 45, y = 4, rule = B3/S23 21bo9b2o$2o8b3o8b2o7b3o$b2o9bo7bo2bo6bo2bo6bobobo$bo9b2o8b2o8b2o!
 cordership3
 Posts: 128
 Joined: August 23rd, 2016, 8:53 am
 Location: haha long boy
Re: Thread for basic questions
The thing is, I work on a lot of shared computers, where downloading cygwin and other programs to compile apgsearch would be inconvenient for others (or just hard to explain away). Since I can't use existing methods to run apgsearch, I thought of a browserbased apgsearch that could be run in a browser quickly. If this, for whatever reason, gets created, I hope the server doesn't get overrun by small hauls...Apple Bottom wrote:Not entirely impractical, I'd guess, as you could take the current C++ codebase, replace the assembly language bits with C++ code, and then compile the whole shebang for asm.js. (This obviously leaves out a lot of work that would have to be done, still.)cordership3 wrote:Would it be practical at all to make a version of apgsearch that works in a browser?
I think the bigger question is: whyever would you want to?
(also, would a .exe for apgsearch be at all practical?)
fg
 Apple Bottom
 Posts: 1027
 Joined: July 27th, 2015, 2:06 pm
 Contact:
Re: Thread for basic questions
Ah, fair enough.cordership3 wrote:The thing is, I work on a lot of shared computers, where downloading cygwin and other programs to compile apgsearch would be inconvenient for others (or just hard to explain away).
This SHOULD be possible  you can probably copy over the apgsearch executable from another computer, though if Cygwin's not installed you may have to link it statically, or else distribute whatever DLLs it depends on along with it.(also, would a .exe for apgsearch be at all practical?)
Your mission, should you choose to accept it: investigate this, create a binary distribution of apgsearch that does not rely on Cygwin being installed, and build an MSI package for it.
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
Re: Thread for basic questions
Answering my own question from last December:
I tried this using Golly's native Wolfram rule support  e.g., W90:T96,0 for a period32 repetition. Every number I tried checked out perfectly.
This method is definitely not recommended for longer periods, though. It seems that Golly's boundedgrid implementation slows things down more than usual for 1D rules. A custom rule table that simulates Rule 90 in place runs hundreds of times faster, and it's compatible with oscar.lua:
Of course a compiled C executable would be several orders of magnitude faster again. Golly is still doing a silly amount of extra work not really needed for this specific case.
I'm very curious about what shortcuts might have been used to generate the numbers in the Wolfram Cloud document, to find out for example that the repetition period for WolframIndex 199 is 90546471444873528678335943241... especially given that many of the interesting cases (like the one above) don't return to their initial state, so you have to run for some number of ticks before starting to look for a repeat.
You certainly couldn't apply the rule that many times and check for a repeated pattern, no matter how fast your computer might be, so it seems like it must be an impressively good shortcut.
EDIT: See the quote in this post for a workable approach.
EDIT 1/11/2019: I did some incomplete spotchecking of the Wolfram Cloud numbers a while back. There are other reductions by a factor of three in the Wolfram Cloud list, not previously mentioned anywhere that I've seen 
WolframIndex 101 > 375299968947541 = (2^501)/3
WolframIndex 197 > 105637550019019116791391933781 = (2^981)/3
And as stated elsewhere, WolframIndex 74 is wrong  it should be twice the value of WolframIndex 37.
A little experimenting seems to indicate that the RepetitionPeriods are what you get if you run Rule 90 on a ring containing {WolframIndex} cells, starting with a single ON cell anywhere in the ring. (By "ring" I just mean the equivalent of a torus for 2D rules.)dvgrn wrote:How exactly are we supposed to use Rule 90 to reproduce all those other "RepetitionPeriods" from that mysterious Wolfram Cloud document? The "inbetween" numbers not included in the A268754 sequence are even bigger and more outlandish, on average, than the A268754 values.
I tried this using Golly's native Wolfram rule support  e.g., W90:T96,0 for a period32 repetition. Every number I tried checked out perfectly.
This method is definitely not recommended for longer periods, though. It seems that Golly's boundedgrid implementation slows things down more than usual for 1D rules. A custom rule table that simulates Rule 90 in place runs hundreds of times faster, and it's compatible with oscar.lua:
Code: Select all
@RULE Wolfram90
@RULE Wolfram90
@TABLE
n_states:2
neighborhood:oneDimensional
symmetries:reflect
1,1,1,0
1,1,0,1
1,0,0,0
0,1,1,0
0,1,0,1
0,0,0,0
Code: Select all
#C 1tick predecessor of a period 87381 oscillator
x = 1, y = 1, rule = Wolfram90:T37,1
o!
I'm very curious about what shortcuts might have been used to generate the numbers in the Wolfram Cloud document, to find out for example that the repetition period for WolframIndex 199 is 90546471444873528678335943241... especially given that many of the interesting cases (like the one above) don't return to their initial state, so you have to run for some number of ticks before starting to look for a repeat.
Code: Select all
#C apparently an oscillator or predecessor of an oscillator,
#C with a 7fold reduction in the default period:
#C 90546471444873528678335943241 = (2^991)/7, not
#C 633825300114114700748351602688 = (2^991)
x = 1, y = 1, rule = Wolfram90:P199,1
o!
EDIT: See the quote in this post for a workable approach.
EDIT 1/11/2019: I did some incomplete spotchecking of the Wolfram Cloud numbers a while back. There are other reductions by a factor of three in the Wolfram Cloud list, not previously mentioned anywhere that I've seen 
WolframIndex 101 > 375299968947541 = (2^501)/3
WolframIndex 197 > 105637550019019116791391933781 = (2^981)/3
And as stated elsewhere, WolframIndex 74 is wrong  it should be twice the value of WolframIndex 37.
Re: Thread for basic questions
How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?
Bored of using the Moore neighbourhood for everything? Introducing the Range2 von Neumann isotropic nontotalistic rulespace!
Re: Thread for basic questions
It's going to be a pretty large number, considering that there are roughly 90'000 exactly20bit still lifes alone that haven't yet appeared on Catagolue in b3s23/C1.muzik wrote:How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?
Re: Thread for basic questions
Waytoomany (for still lifes), plus somewhere around 5000 (for oscillators), plus one (if you count the 18bit pseudospaceship LWSS on LWSS, which I suspectbutdon'tknowforsure is separated by apgsearch so it's probably occurred but we haven't noticed it), plus the loafer. Plus any other tiny spaceships that we haven't discovered.muzik wrote:How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?
All of which adds up to precisely waytoomany  well over a hundred thousand. As of just now Catagolue only has 12,863 of the 112,243 20bit still lifes, and only 10,352 of the 45,759 19bit still lifes, and so on down to where darn it all we're still missing one of the 619 14bitters.
My sources of information are Catagolue's statistics page and Mark Niemiec's spaceships page. The 5000 figure for oscillators comes from Mark's oscillators page, but I'm not quite clear on whether any more 20bit or smaller oscillators might still show up the way the 21bit Runny Nose did.
Re: Thread for basic questions
Let's see... 1+61+597+3053+11480+35411+99385 comes out to 149988 still lifes, 149989 objects including the loafer, and roughly 154989 including the about 5000 oscillators. Can someone get a Dyson sphere or something over here already?
Bored of using the Moore neighbourhood for everything? Introducing the Range2 von Neumann isotropic nontotalistic rulespace!
Re: Thread for basic questions
We don't need a Dyson sphere, we just need a less ambitious threshold! Just pick 14 instead of 20 and we have a chance of finding everything.muzik wrote:Let's see... 1+61+597+3053+11480+35411+99385 comes out to 149988 still lifes, 149989 objects including the loafer, and roughly 154989 including the about 5000 oscillators. Can someone get a Dyson sphere or something over here already?
Conversely, pick 40 instead of 20 and even a Dyson sphere might not be enough, since a Dyson sphere only gives us a factor of 10^20 or 10^25 or so improvement over the current status quo. I guess you could add another 10^10 or 10^20 improvement if you want to assume we'll figure out how to make computers that much faster and more efficient, by the time we've finished building the Dyson sphere.
I think that still doesn't get us to 10^77, the size of 16x16soup space. If we run the Dyson sphere for enough years, we might manage to get there before the Sun burns out, but it might be a close call.
Anyway, somewhere up there Catagolue's methodology will become kind of questionable, since we already know there are 16x16 soups containing loafers and every other spaceship, oscillator or still life with a 16x16 or smaller bounding box. But somehow we're not really as interested if the object is already there at T=0. Might as well just enumerate all the 16x16 patterns instead of picking them randomly  would save a lot of time if we're going to end up trying them all anyway.
There's a simpler reason why a Dyson sphere might not be sufficient for a 40bit threshold. Never mind Sir Robinsized things, possibly some spaceships with 40 bits or less don't have a 16x16 predecessor, in which case no matter how long we run apgsearch they'll never show up. Some known 40bit spaceships are 13x25, for example, so at least there definitely isn't a soup where they appear before T=5.
 Yes, it's a strange thought experiment where we convert the entire solar system into computronium but never think of bumping up Catagolue's soup size at least to 32x32.
Re: Thread for basic questions
I don't think even Dyson Sphere + quantum computers would let us run every 16*16 soup. There are 2^256 soups, but Grover's algorithm will give a quadratic speedup so we "only" have to run 2^128 of them. The power output of the sun is about 2^75 times what my computer requires, and my computer does 2^11 soups per second, so we would need about 2^(128  11  75) seconds, which is 140000 years.
That's assuming my computer does as many operationspersecond as a quantum computer in the far future, which is unrealistic (although I couldn't tell you in which direction it was unrealistic).
On the other hand, once you have the technology to build one Dyson sphere it isn't actually much harder to build 140000 of them, so it's not impossible we will have the answer one day.
That's assuming my computer does as many operationspersecond as a quantum computer in the far future, which is unrealistic (although I couldn't tell you in which direction it was unrealistic).
On the other hand, once you have the technology to build one Dyson sphere it isn't actually much harder to build 140000 of them, so it's not impossible we will have the answer one day.
Re: Thread for basic questions
Oh, good, then my math isn't too far off. I did sayMacbi wrote:The power output of the sun is about 2^75 times what my computer requires, and my computer does 2^11 soups per second, so we would need about 2^(128  11  75) seconds, which is 140000 years.
However, I didn't even try to sort out the probability power laws. I guess we're guaranteed to find most of the 20bit still lifes and oscillators, though there are a few that don't fit in 16x16. 20bit barber poles and ludicroussquaredly long canoe (or whatever you call that) are 17x17, so it's not an absolutely foregone conclusion that 16x16 soups even exist that produce these. Grover's algorithm can't find soups that don't exist.dvgrn wrote:If we run the Dyson sphere for enough years, we might manage to get there before the Sun burns out...
And that doesn't even count the famous PiRSquared spaceship*, where two pi grandparents and two Rpentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.
* seen briefly in 1974 on a PDP12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.
Re: Thread for basic questions
Wait, isn't Grover's algorithm very much nonparallelisable? As I understand it, don't you have to perform the Grover rotation gate O(2^128) times in succession and then make a measurement?
What do you do with ill crystallographers? Take them to the monoclinic!
Re: Thread for basic questions
Hmmm... you could be right. We would need an extension of Grover's algorithm anyway, since we're not searching only one thing, and we also want to tally up object counts (essentially a quantum counting algorithm). Since Grover's algorithm is probabilistic it requires repeats to find the answer with certainty, and these repeats could definitely be done in parallel (which it what I was thinking earlier). But each repeat still needs to do O(N^1/2) operations, and it doesn't immediately seem like these can be done in parallel. So it looks like you're right.calcyman wrote:Wait, isn't Grover's algorithm very much nonparallelisable? As I understand it, don't you have to perform the Grover rotation gate O(2^128) times in succession and then make a measurement?
In fact it looks like no quantum search algorithm can be parallelised (https://arxiv.org/pdf/quantph/9711070.pdf).
EDIT: It's probably still good for each individual computer to be using Grover's algorithm. We can give them each a portion of the search space. So not being parallelisable doesn't hurt us by O(number of computers), but only by O(sqrt(number of computers)). Which is still terrible.
EDIT2: Also, the catagolue currently uses 10^9 of the world's energy, and there are only 10^11 stars in the Milky Way, so we might only have about 100 to play with.
Re: Thread for basic questions
Where can I read more about this? My googlefu has failed me.dvgrn wrote:And that doesn't even count the famous PiRSquared spaceship*, where two pi grandparents and two Rpentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.
* seen briefly in 1974 on a PDP12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.
Re: Thread for basic questions
dvgrn is pulling your leg Tony Honcho Jarnow is an anagram of John Horton Conway.Hooloovoo wrote:Where can I read more about this? My googlefu has failed me.dvgrn wrote:And that doesn't even count the famous PiRSquared spaceship*, where two pi grandparents and two Rpentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.
* seen briefly in 1974 on a PDP12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.
Re: Thread for basic questions
I just got on to edit my post to ask if if I was being messed with
I definitely didn't notice the anagram, though, nice job!
I definitely didn't notice the anagram, though, nice job!
Re: Thread for basic questions
You can tell when dvgrn is messing with you because he uses the number 137.