Spaceship Discussion Thread

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 1st, 2016, 4:40 am

I just noticed that all known elementary period 7 spaceships end in "er". Loafer, weekender, lobster, spaghetti monster...



Can someone run the potential 3c/14 front end through a search and see what might appear?

Code: Select all

x = 15, y = 7, rule = B3/S23
3b3o3b3o$2bo3bobo3bo$2bo3bobo3bo$2bo3bobo3bo$o2b3o3b3o2bo$o13bo$o13bo!

how do I even run gfind? I must know

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: Spaceship Discussion Thread

Post by Sokwe » July 1st, 2016, 6:10 am

muzik wrote:Can someone run the potential 3c/14 front end through a search and see what might appear?
I have been trying this to some extent. I have been using zfind at search-width 6 to look for a symmetric back end to each side that deletes the three extra blinkers. Unfortunately, the partials aren't too promising. Here is the current longest partial:

Code: Select all

x = 23, y = 43, rule = B3/S23
8bo5bo$7b3o3b3o$7b3o3b3o4$3b3o11b3o$3bobo11bobo$3b3o11b3o3$4bo13bo$3bo
bo11bobo$2b2ob2o9b2ob2o$2b2ob2o9b2ob2o$3bobo11bobo$2b2ob2o9b2ob2o$2b2o
b2o9b2ob2o$4bo13bo2$4bo13bo$3bobo11bobo$2b2ob2o9b2ob2o$2b2ob2o9b2ob2o$
b2obob2o7b2obob2o$obo3bobo5bobo3bobo$o7bo5bo7bo$2bo3bo9bo3bo$obo3bobo
5bobo3bobo2$3o3b3o5b3o3b3o$bo5bo7bo5bo2$b2o3b2o7b2o3b2o$2obobob2o5b2ob
obob2o$2o5b2o5b2o5b2o$2b5o9b5o2$2bo3bo9bo3bo$2bobobo9bobobo$o3bo3bo5bo
3bo3bo$b2o3b2o7b2o3b2o$bobobobo7bobobobo!
This same search could be run at width 7, but it would take a lot longer (my width-6 search is still running).
muzik wrote:how do I even run gfind?
You will need to compile it and run it through a command line interface. There are several threads on the scripts forum about compiling and running gfind. Unfortunately, for a 3c/14 search I think gfind will be too slow. zfind is probably the only program that can handle it in a reasonable length of time (zfind works will with a high period and small width).

Edit: Completely unrelated is this 2c/8 partial:

Code: Select all

x = 18, y = 49, rule = B3/S23
8b2o$7b4o$3bob2ob2ob2obo$2bobo8bobo$bo2bob2o2b2obo2bo$bo4b2o2b2o4bo$bo
bob3o2b3obobo$b2o12b2o$3b3o2b2o2b3o$3b12o$2bo12bo$bo2bo2b4o2bo2bo$2bob
o3b2o3bobo$ob3obo4bob3obo$3b2o2bo2bo2b2o$b3o3bo2bo3b3o$bo14bo$b2o12b2o
$bo4bo4bo4bo$2b2o2b2o2b2o2b2o$2b2o10b2o2$3bo2bo4bo2bo2$2b2o2b2o2b2o2b
2o$6bo4bo$4bo8bo$5b2o4b2o$3bob2o4b2obo$4bo8bo$5b2o4b2o$2bobo8bobo$2b3o
3b2o3b3o$6bo4bo$5b2o4b2o$2ob3o6b3ob2o$b4ob2o2b2ob4o$5bo6bo$3bobo6bobo$
3bobo6bobo$3bo3bo2bo3bo$5b2o4b2o$4bob2o2b2obo$2bobo2bo2bo2bobo$bobo2b
2o2b2o2bobo$2obo2b6o2bob2o$4obobo2bobob4o$5bob4obo$bo14bo!
-Matthias Merzenich

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 1st, 2016, 6:40 am

It uses this reaction (pre-beehive) to delete the three blinkers:

Code: Select all

x = 5, y = 8, rule = B3/S23
2bo$b3o$2ob2o$b3o$2bo2$b3o$b3o!
which is pretty neat I suppose.


Repeating it is the real problem.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Spaceship Discussion Thread

Post by HartmutHolzwart » July 1st, 2016, 7:55 am

3c/7 -> late congratulations! I was hoping for a distaff or a connection to some of the other old 3c/7 technology, especially a support of the diagonal 3c/14 pi wave!

c/6 -> nice find! Your collection tempts me to search for c/6 grey ships. No really promising frontend so far, but two starting points. What still is missing are some short wide c/6 ships or at least partials.

2c/8 -> A pity you couldn't finalize that!

3c/14 -> I'm impressed how far you can get with zfind. Alas, we need another breakthrough in search technology to be able to seriously work on that!

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: Spaceship Discussion Thread

Post by Sokwe » July 2nd, 2016, 3:50 am

Here are some ways to combine some components from Tim Coe's new c/6 ships:

Code: Select all

x = 133, y = 95, rule = B3/S23
7bo13bo9bo13bo41bo13bo9bo13bo$6bobo11bobo7bobo11bobo39bobo11bobo7bobo
11bobo$6bobo11bobo7bobo11bobo39bobo11bobo7bobo11bobo$7bo13bo9bo13bo41b
o13bo9bo13bo2$6b3o11b3o7b3o11b3o39b3o11b3o7b3o11b3o$5bob2o3b2ob2o3b2ob
o5bob2o3b2ob2o3b2obo37bob2o3b2ob2o3b2obo5bob2o3b2ob2o3b2obo$6bo4bobobo
bo4bo7bo4bobobobo4bo39bo4bobobobo4bo7bo4bobobobo4bo$10b2obobob2o15b2ob
obob2o47b2obobob2o15b2obobob2o$11bobobobo17bobobobo49bobobobo17bobobob
o$13bobo21bobo53bobo21bobo$13bobo21bobo53bobo21bobo$8bo3b2ob2o3bo11bo
3b2ob2o3bo43bo3b2ob2o3bo11bo3b2ob2o3bo$8b3ob2ob2ob3o11b3ob2ob2ob3o43b
3ob2ob2ob3o11b3ob2ob2ob3o$12b2ob2o19b2ob2o51b2ob2o19b2ob2o$8b3o7b3o11b
3o7b3o43b3o7b3o11b3o7b3o$11b2o3b2o17b2o3b2o49b2o3b2o17b2o3b2o$8b2ob2o
3b2ob2o11b2ob2o3b2ob2o43b2ob2o3b2ob2o11b2ob2o3b2ob2o$10bobo3bobo15bobo
3bobo47bobo3bobo15bobo3bobo$8b2o4bo4b2o11b2o4bo4b2o43b2o4bo4b2o11b2o4b
o4b2o$8bo11bo11bo11bo43bo11bo11bo11bo$7bo13bo9bo13bo41bo13bo9bo13bo$9b
o9bo13bo9bo45bo9bo13bo9bo$7b2obo2b3o2bob2o9b2obo2b3o2bob2o41b2obo2b3o
2bob2o9b2obo2b3o2bob2o$7bo2b2ob3ob2o2bo9bo2b2ob3ob2o2bo41bo2b2ob3ob2o
2bo9bo2b2ob3ob2o2bo$7bob11obo9bob11obo41bob11obo9bob11obo2$7bo4bo3bo4b
o9bo4bo3bo4bo41bo4bo3bo4bo9bo4bo3bo4bo$12bo3bo19bo3bo51bo3bo19bo3bo$8b
o3b2ob2o3bo11bo3b2ob2o3bo43bo3b2ob2o3bo11bo3b2ob2o3bo$8b2o2b2ob2o2b2o
11b2o2b2ob2o2b2o43b2o2b2ob2o2b2o11b2o2b2ob2o2b2o$8b2o9b2o11b2o9b2o43b
2o9b2o11b2o9b2o$7b2o11b2o9b2o11b2o41b2o11b2o9b2o11b2o$7b2o11b2o9b2o11b
2o41b2o11b2o9b2o11b2o$10b2o2bo2b2o15b2o2bo2b2o47b2o2bo2b2o15b2o2bo2b2o
$10b2o2bo2b2o15b2o2bo2b2o47b2o2bo2b2o15b2o2bo2b2o$10b3obob3o15b3obob3o
47b3obob3o15b3obob3o4$10b3o3b3o15b3o3b3o47b3o3b3o15b3o3b3o$6b3ob3o3b3o
b3o7b3ob3o3b3ob3o39b3ob3o3b3ob3o7b3ob3o3b3ob3o$6b3ob2o5b2ob3o7b3ob2o5b
2ob3o39b3ob2o5b2ob3o7b3ob2o5b2ob3o2$8bo11bo11bo11bo43bo11bo11bo11bo$8b
o11bo11bo55bo11bo11bo$5bo5bo7b3o9b3o53b3o9b3o9b3o$3bo9bo5b2o11b2o6bo7b
o38b3o9b2o11b2o6bo7bo$3bo9bo6b3o7b3o5b2o9b2o36b3o10b3o7b3o5b2o9b2o$2bo
11bo4bo5b3o5bo4bobo2b3o2bobo48bo5b3o5bo4bobo2b3o2bobo$3b2ob5ob2o5bo5b
3o5bo5b3ob3ob3o49bo5b3o5bo5b3ob3ob3o$4bo7bo5bo3b3o3b3o3bo5bobo3bobo34b
o9bo4bo3b3o3b3o3bo5bobo3bobo$4bobobobobo6bob2obobobob2obo5b2o7b2o32bob
o3bo3bobo4bob2obobobob2obo5b2o7b2o$4bo7bo12b3o11b2o7b2o32bo2b3ob3o2bo
10b3o11b2o7b2o$4bo7bo27bo7bo71bo7bo$2b2o9b2o23bobo7bobo35b5o27bobo7bob
o$2b2o4bo4b2o22bo13bo65bo13bo$2b2ob2o3b2ob2o23b3o7b3o34bo5bo26b3o7b3o$
41bobobobo36b2o5b2o28bobobobo$6b2ob2o30bobobobo35bo9bo27bobobobo$5b3ob
3o29bo5bo33bo2bo7bo2bo25bo5bo$b2o3b2ob2o3b2o21b2o2bobobobo2b2o30b3o7b
3o22b2o2bobobobo2b2o$b2o11b2o21b2o11b2o31bobo5bobo23b2o11b2o$37b3o9b3o
32b2o5b2o24b3o9b3o$2bobo7bobo24bo9bo34b2o5b2o26bo9bo$3bo9bo25bo9bo31b
2o3bo3bo3b2o23bo9bo$38b2o9b2o29bo15bo21b2o9b2o$2b2o9b2o23bo11bo30bobo
9bobo22bo11bo$bo13bo21bobo9bobo31b2o7b2o23bobo9bobo$b2o11b2o21bobo9bob
o31b2o7b2o23bobo9bobo$2b2o9b2o22b3o9b3o30b2o9b2o22b3o9b3o$39bo9bo31bo
13bo23bo9bo$o3bo7bo3bo64bobo9bobo$4bo7bo23b2o13b2o27b2ob2o7b2ob2o19b2o
13b2o$2o13b2o20b2obo7bob2o29bob2o7b2obo21b2obo7bob2o$2b3o7b3o25bo7bo
34bo9bo26bo7bo$2b3o7b3o23bo3bo3bo3bo67bo3bo3bo3bo$4b4ob4o30bobo34b3o
11b3o26bobo$5bobobobo31bobo34b4o9b4o26bobo$4bo2bobo2bo28bobobobo33b2o
2bo5bo2b2o25bobobobo$6b2ob2o29b2obobob2o71b2obobob2o$3bobobobobobo29bo
bo40b2ob2o32bobo$4b3o3b3o26bo3bobo3bo37bobo29bo3bobo3bo$4b3o3b3o30bobo
38b2obobob2o30bobo$5b2o3b2o28bobo3bobo35b2obobob2o27bobo3bobo$40b2o5b
2o35bo2bobo2bo27b2o5b2o$bob2o7b2obo22b3o7b3o35b2ob2o27b3o7b3o$bo2bo7bo
2bo20b2o2b2o5b2o2b2o33b2ob2o25b2o2b2o5b2o2b2o$bo2bo7bo2bo68bobo3bobo$
37bo13bo65bo13bo$obo11bobo20bo13bo29b2o11b2o21bo13bo$bo13bo21bo13bo29b
2ob2o5b2ob2o21bo13bo$80b2o13b2o2$80b3o11b3o!
-Matthias Merzenich

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 2nd, 2016, 9:32 am

Futile it may be, but could someone be as kind as to run this reaction through a c/26 orthogonal search (probably a glide symmetric 2c/52 one) to see if any interesting partials come up?

Code: Select all

x = 13, y = 8, rule = B3/S23
ob2o$3o$bo3$10bobo$10b2o$11bo!

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 2nd, 2016, 2:30 pm

muzik wrote:Futile it may be, but could someone be as kind as to run this reaction through a c/26 orthogonal search (probably a glide symmetric 2c/52 one) to see if any interesting partials come up?
c/26, yikes! I think that's probably a search you'll have to run yourself, if you want it done. And at that width, you'd better have a whole new search algorithm, or some really impressive computer hardware. As a rough guess, probably turning the entire mass of the Earth into computer chips wouldn't be enough.

A good rule of thumb seems to be that it's a few orders of magnitude harder to do a search for a period N+1 spaceship, than for a period-N spaceship. As you increase the period, you increase the number of unknown cells that could be either ON or OFF, and you have to check both options for each new cell.

Even if we were looking for a tiny 5x5 spaceship, let's say, and a lot of the cells were forced by the states of other cells, there might be 10 new choices of cell state for the eighth phase of a theoretical period-8 ship, that weren't there at all for an equivalent period 7 ship (where the eighth phase has to be the same as the first phase).

That's 2^10 times as many cases, or an increase in difficulty of three orders of magnitude.

Again, this is all a gross oversimplification, so please don't take the math seriously -- but it allows for some rough intuition about the difficulty of c/26 searches.

The period-7 Spaghetti Monster spaceship was discovered based on searches that took a couple of months to run. Maybe it could have been found inside a week, if someone had lucked out and tried the right search immediately, instead of going through all the smaller search spaces first. So let's simplify again and say a p7 spaceship search takes a week.

Then a p8 spaceship search with the same methods will take about a thousand weeks, and a p9 search will take a million weeks. Finding a c/26 spaceship will take about 10^54 = 1000000000000000000000000000000000000000000000000000000 weeks of CPU time.

If you only have maybe a week to spend before you run out of patience, you're likely to come up with a partial that represents about 1/1000000000000000000000000000000000000000000000000000000th of a complete c/26 ship.

Your mileage may vary, of course... but it's probably better if you put in your own mileage in this case instead of asking someone else to do it for you. The reaction you're trying to use as a front end looks like it's about 18 cells wide, so probably the "10 new cells per phase" assumption is a really gross underestimate for this particular front end. So there will be a lot more zeroes in the number of weeks you need to find a complete c/26 spaceship with known search utilities -- i.e., the number will be big enough to make a googol look totally insignificant.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 2nd, 2016, 2:44 pm

welp that went better than expected
EDIT: I'm assuming my c/18 question isn't looking good either then? also 10000th view

guess we should perhaps focus on finding that 3c/14 first.




Do you reckon we might be able to find an "elementary replicator" <1000 cells, using the pre-pulsar reaction? We already have an engineerable replicator (the linear propagator) so looking for a small elementary replicator might be an interesting project, however you would do that.

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 2nd, 2016, 3:28 pm

muzik wrote:guess we should perhaps focused n finding that 3c/14 first.
Right... according to the same probably-wrong estimation, we're looking at only 10^21 weeks to finish a period-14 spaceship, or about two quintillion decades of CPU time. Downright quick and easy, compared to the other one.
muzik wrote:Do you reckon we might be able to find an "elementary replicator" <1000 cells, using the pre-pulsar reaction? We already have an engineerable replicator (the linear propagator) so looking for a small elementary replicator might be an interesting project, however you would do that.
It would certainly be an interesting thing to find. So far it doesn't seem to have been an interesting thing to look for, because nobody has figured out a workable way to automate a search for anything like that that has a population in the hundreds.

-- Unless you count what Catagolue is doing, anyway. If there was a really small fast B3/S23 replicator, it might have showed up at the edge of a soup by now, and Catagolue would have collected it. The best plan I can think of for finding something like that would be to encourage everyone on Hacker News, Reddit, Digg and Slashdot to start running apgmera -- but if no sub-1000-cell replicator exists, we'll have a hard time ever knowing that for sure.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 2nd, 2016, 3:50 pm

dvgrn wrote:-- Unless you count what Catagolue is doing, anyway. If there was a really small fast B3/S23 replicator, it might have showed up at the edge of a soup by now, and Catagolue would have collected it. The best plan I can think of for finding something like that would be to encourage everyone on Hacker News, Reddit, Digg and Slashdot to start running apgmera -- but if no sub-1000-cell replicator exists, we'll have a hard time ever knowing that for sure.
Digg still exists?

Even if we don't find this replicator, we might still be able to find something like a loafer, copperhead, 25P3H1V0.2, or maybe even biggiemac's legendary tiny c/18 ship emerging from soup. Which, in terms of a spaceship thread, is pretty good.

And even at that, I think that encouraging everyone at all those sites to search the hell out of life is someone we should have already done ages ago anyway. (Uhm, what are we all waiting for?)


However, I'd definitely like to see the unholy 2-number gap in the elementary spaceship speeds be filled in ASAP. How long should it take to discover our c/8 or c/9?

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: Spaceship Discussion Thread

Post by drc » July 2nd, 2016, 4:22 pm

muzik wrote:biggiemac's legendary tiny c/18 ship
When did this happen? I've trying searching but C and 18 are too common

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 2nd, 2016, 4:45 pm


Sphenocorona
Posts: 549
Joined: April 9th, 2013, 11:03 pm

Re: Spaceship Discussion Thread

Post by Sphenocorona » July 2nd, 2016, 6:05 pm

drc wrote:
muzik wrote:biggiemac's legendary tiny c/18 ship
When did this happen? I've trying searching but C and 18 are too common
It's from a post about how sad it would be for a soup to produce an unusual spaceship like a loafer or some new velocity, only for it to run into a blinker or something. c/18 was a velocity simply pulled out of thin air; there is nothing special about c/18, or any evidence that such a ship might exist. Maybe it does, but same thing could be said for a ship that fits in a rectangle of width 10 in at least one phase, length of under 200 cells long, and a velocity of (7,13)c/67 or something equally arbitrary. We don't really have a way to effectively search for these theoretical ships.

No c/18 ships have been discovered.

The main thing we can do to find such ships right now is probably to keep doing soup searches and trying to find new ways to improve search programs so that they might someday be able to handle such high periods.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 3:53 am

Still kind of surprised this hasn't appeared from asymmetric soup:

Code: Select all

x = 11, y = 11, rule = B3/S23
b5o$bo4bo$bo$2bo4bo$4bo$5b2o2bo$3bo2bo3bo$bo7bo$o5bo2bo$o3b2o$4o2b2o!
or the sidecar for that matter.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 8:20 am

Can someone send the famous glider-pulling-block reaction through an oblique search and see what comes up?

(Hint: probably nothing interesting, but who cares)

Code: Select all

x = 7, y = 4, rule = B3/S23
2o$2o2bo$4bobo$4b2o!

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 3rd, 2016, 9:47 am

muzik wrote:Can someone send the famous glider-pulling-block reaction through an oblique search and see what comes up?

(Hint: probably nothing interesting, but who cares)
Anyone who is considering spending weeks of time and effort setting up and running the search might care. Run a few of these searches yourself and you'll see why. If you don't define your searches very carefully so that they have the maximum odds of success, you're very likely spend the rest of your life running searches and never finding anything at all.

A block-pulling spaceship would have to have a minimum period of 10, it looks like, and that's currently pretty far out of reach with known search methods.

You can extrapolate from my crackpot estimates from yesterday that completing an exhaustive search for a c/10 knightship will take a billion weeks of CPU time, using currently known search methods -- and that's only if there happens to be one out there that's fairly small.

Also, in my not-really-expert opinion, that's a very optimistic minimum estimate. Knightships can't be symmetric, and there are a lot more unknown cells in asymmetric searches. And the reaction you're suggesting would require searching forward from the back end of the spaceship, right? So add several more zeroes due to the inefficiency of known algorithms in searching forward from the tail of a ship... or invent a new algorithm that can do better, and then make new estimates based on that.

----------------------

Now, I'm fairly sure that there is an elementary knight-rake-ship out there somewhere, with a period of 10 or above -- the search space is so huge that the odds seem very good, actually. And there will be a similarly extensible blinker-puller spaceship and a loaf-puller spaceship, and an elementary rake that can pull half-bakeries along after itself, and so forth.

It's just that there's no known way to run a search that has any hope of finding most of these interesting objects, because most of them will be too big to find. The smallest block-pulling knightship might happen to be several hundred cells in size. Even if it was just 100 cells, current search methods would run out of memory before setting up the first pattern that could possibly be a block-pulling knightship of that size.

In fact, all the computers currently on Earth would run out of memory before that point... and even if we somehow upgraded them all so memory wasn't an issue, the Sun would burn out before they were done inspecting the gazillions of candidates before the first actual knightship would be likely to appear.

And by this time we've gone way too far into the realm of hand-waving and wishful thinking. Sure, we might get lucky and the first candidate we look at might be a working knightship -- but the odds of that are really no better than the odds that the first generation of a Catagolue soup will turn out to be a knightship. Might as well just keep running Catagolue, really -- that way we're running a search for all possible periods at once.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 10:00 am

So how would we go about getting everyone to use Catagolue? We already have a Reddit post, but I could go about making a different one.


Also, a stupid question, because I really like asking them: When we reach 1 quadrillion objects, how likely do you think it would be that we witness a loafer, copperhead or Tiny C/18 Ship™ emerging from an asymmetric soup?



Has anyone run a search for a new backend for the almost knightship yet?

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 3rd, 2016, 10:10 am

muzik wrote:However, I'd definitely like to see the unholy 2-number gap in the elementary spaceship speeds be filled in ASAP. How long should it take to discover our c/8 or c/9?
I answered that question very specifically in my long-winded post yesterday:
Then a p8 spaceship search with the same methods will take about a thousand weeks [of CPU time], and a p9 search will take a million weeks.
This suggests that a c/8 spaceship is likely to be within reach of a good distributed search, or even a few weeks of the otherwise unused cycles of some high-performance computing cluster somewhere ... but a c/9 ship would take either a very ambitious distributed search, or a few more years while we wait for Moore's Law to make things a little easier for us.

Of course my estimate is very probably wrong, because it requires very specific assumptions about the size of the p8 and p9 spaceships that are going to be found. If they're really big, or asymmetric, or both, they're going to be harder to find.

It's theoretically possible that a c/8 doesn't happen to have any symmetric solutions below some horribly high width like 30 or 40, but that there's a c/9 that's only just barely bigger than [whatever the most ambitious c/9 search is that's been done so far], that will be found as soon as someone looks for it.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 10:14 am

So how long would c/11, c/12, 2c/9 and 2c/11 orthogonal take, respectively?


And how was the copperhead found so fast if it has such a high period?

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 3rd, 2016, 10:55 am

muzik wrote:So how long would c/11, c/12, 2c/9 and 2c/11 orthogonal take, respectively?
If you believe my crackpot estimate, then just multiply by a thousand every time you increase the period by one. But don't believe my crackpot estimate -- or maybe use that as a base estimate but then think to yourself, "... plus or minus ten orders of magnitude."
muzik wrote:And how was the copperhead found so fast if it has such a high period?
Because it's very very small, and symmetrical. You can try all the possible symmetrical patterns inside a 6x11 bounding box in a reasonable amount of time, and see if they move at c/10. That's a very different kind of search from finding, for example, the narrowest pattern that moves at 3c/7.

The Spaghetti monster spaceship doesn't fit into anything like 6x11. So if zdr had done an equivalent 6x11 bounding box search at 3c/7, it would have been very boring and returned no solutions, without giving much indication of whether something bigger was out there to be found.

No doubt there are other periods besides c/7 and c/10 where a relatively small spaceship can be cherry-picked with a speculative search. It's just not so likely that we'll be enormously lucky and those other periods will happen to include both c/8 and c/9!

...Not to increase your mental anguish about gaps, but why aren't you worried about the equally painful empty space between c/7 diagonal and c/12 diagonal?

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 11:07 am

dvgrn wrote:...Not to increase your mental anguish about gaps, but why aren't you worried about the equally painful empty space between c/7 diagonal and c/12 diagonal?
Just... don't mention it, okay? I cry thinking about it.


I'm assuming that searches for diagonal ships are even harder? How long would searches for c/8, 9, 10 and 11 diagonal take?

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Spaceship Discussion Thread

Post by Scorbie » July 3rd, 2016, 12:30 pm

Similar situation to the orthogonal search, but the diagonal searches seem to be slower. Wonder why.

Also, there are gaps in oblique speeds... But let us not talk about that.

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 3rd, 2016, 12:34 pm

muzik wrote:I'm assuming that searches for diagonal ships are even harder? How long would searches for c/8, 9, 10 and 11 diagonal take?
Seems like diagonal ships are bigger on average than "equivalent" orthogonal ones -- the glider being the lonely B3/S23 counterxample that proves the rule. So yes, they take exponentially-proportionally longer to find on average.

I'd like to refuse to answer your c/8 through c/11 diagonal questions, on the grounds that it should be clear from previous messages that I really have no idea either!

But sometimes it's hard for me to stop typing, so I've made up an answer below.

If you want to figure these answers out yourself based on my previous crackpot rule-of-thumb estimates, you just need to know how long Sokwe's search took that found the c/7 diagonal ship -- assuming (on no particularly good grounds) that the higher-period ships are about the same size as the lobster.

Let's say it took a week of searching. Then
  • the c/8 ship might take a thousand weeks,
  • the c/9 ship might take a million weeks,
  • the c/10 ship might take a billion weeks,
  • and the c/11 ship might take a trillion weeks.
We could conceivably somehow convince a million people to distribute the million-week search and get done in a reasonable amount of time, but above that we're getting above the spare-computing-power capacity of the Earth today.

-- That's all assuming that my expansion factor of a thousand is correct, which of course it isn't. That would be only ten cells with completely unknown states that WinLifeSearch-or-equivalent has to test in all possible combinations, for each added phase of the spaceship.

If WinLifeSearch actually has to check twenty unknown cells for each added phase (which might be more likely for a lobster-sized spaceship, but I'm not at all sure so please don't quote me on it) then the expansion factor would be more like a million than a thousand.

You can recalculate the above based on that expansion factor... but at some point the ridiculously large numbers stop mattering. The key idea is what's important: higher period searches are hard, and they get harder very quickly as the period increases.

Clever new algorithms, or continued Moore's Law hardware improvements, might shift the point at which searches become really hard. Currently it seems to be around c/7, except that we can define very limited small search spaces for higher periods and hope to find something like a copperhead or a loafer in them. And every now and then that will keep happening, because there are a lot of strange and wonderful Life patterns out there.

But even when (if?) algorithms or computer hardware become a thousand or a million times better than they are now, that might only shift the easy/hard frontier from c/7 to c/8.

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Spaceship Discussion Thread

Post by muzik » July 3rd, 2016, 12:39 pm

I guess what we should be looking for now is not spaceships, but reactions.

We have the switch engine, which moves at c/12 and can be tamed to move at c/12. So what about a reaction that moves at c/9 diagonal or so?

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

Re: Spaceship Discussion Thread

Post by dvgrn » July 3rd, 2016, 12:50 pm

muzik wrote:I guess what we should be looking for now is not spaceships, but reactions.

We have the switch engine, which moves at c/12 and can be tamed to move at c/12. So what about a reaction that moves at c/9 diagonal or so?
I think it's the same kind of problem, unfortunately. For c/12, Charles Corderman picked the low-hanging fruit back in 1971, by running nonominoes and watching what happened. zdr's discovery of the copperhead was a more recent kind of low-hanging fruit -- hanging not nearly so low, but still within easy reach of today's computing capacity.

But reactions that run at c/9 and don't need continuous outside support are either spaceships in their own right, or they're puffers of some kind. Puffers analogous to the switch engine do show up in all sorts of rules, but if they happened very often in B3/S23, Catagolue would have catagolued a bunch of them by now.

I'm still surprised that that hasn't happened, actually. A self-sustaining repeating reaction seems like it shouldn't be so unlikely -- bounce a pi-heptomino off a beehive, let's say, and happen to produce some junk and another pi-heptomino... and another beehive offset by the same amount.

It's that last "offset by the same amount" that brings the odds down so close to zero, along with the unspoken caveat "and no other random junk that happens to get in the way."

Post Reply