Caterloopillar WIP (all speeds < c/4)

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » April 18th, 2016, 8:38 am

muzik wrote: should we create a seperate wiki page for the 31c/240 caterloopillar?
Don't think so. We should instead add special mention in the caterloopillar page about this speed. Maybe we should add "interesting speeds section", adding there c/8 as the first speed, 31/240 as centipede alternative, and maybe some more (fastest, largest, slowest, minimal bounding box and cell count)...
muzik wrote:Could a caterloopilar with <10000 cells exist?
Don't think so. I've now reached 58K with c/92, Which should be pretty easily optimized by factor of 2, getting into demonoid range. I don't think less than 20K is feasible, remember that all the slow salvo SLs take pretty large space. Maybe some more advanced tricks can be introduced - but with current basic design I don't see it getting under 20K. Lets hope Demonoid can be superseded, thus breaking the smallest designed ship record.

EDIT I've verified the script on a "clean" station. Can more people report success/failures with the script? Please download it from the attached file first, and tell me if you're getting any errors for simple speeds (c/8, c/13 etc.).

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » April 18th, 2016, 1:27 pm

Assuming the speed of light in Life is the same as the speed of light in our universe, the slowest Life ship we have travels at a leisurely 7708237 mph.

The fastest speed travelled by a man-made object is just 157000 mph...




That said, what is the slowest speed you can make (that is not a stationary object)?

User avatar
codeholic
Moderator
Posts: 1147
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Caterloopillar WIP (all speeds < c/4)

Post by codeholic » April 18th, 2016, 1:50 pm

Infinitesimal.
Ivan Fomichev

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by calcyman » April 18th, 2016, 1:56 pm

muzik wrote:Assuming the speed of light in Life is the same as the speed of light in our universe, the slowest Life ship we have travels at a leisurely 7708237 mph.
Which ship is that? My original (6, 3)c/2621440 half-baked knightship travels at 1535 mph (in the L_infinity norm):

Code: Select all

Greetings, APG...

root@kali:~# python
Python 2.7.11 (default, Dec  9 2015, 00:29:25) 
[GCC 5.3.1 20151205] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (299792458 * 3600 / (0.0254 * 36 * 1760)) * (6.0/2621440)
1534.9196534371836
>>> 
That's roughly twice the speed of sound.
muzik wrote:That said, what is the slowest speed you can make (that is not a stationary object)?
If it's not a stationary object, at least one of the four edges of the bounding box must advance at a speed of Omega(sqrt(log(t))). Does that answer your question?
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
biggiemac
Posts: 515
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: Caterloopillar WIP (all speeds < c/4)

Post by biggiemac » April 18th, 2016, 2:15 pm

calcyman wrote:
muzik wrote:That said, what is the slowest speed you can make (that is not a stationary object)?
If it's not a stationary object, at least one of the four edges of the bounding box must advance at a speed of Omega(sqrt(log(t))). Does that answer your question?
That doesn't really make it clear, because the relation between speed and t is confusing.

Say something lives in an M x N bounding rectangle. There are 2^(MN) patterns of ons and offs within such a rectangle, and every one of them has a definite evolution sequence. To not be a stationary object, it has to leave that bounding box before exhausting all of them, or it will be in a loop.

If something hasn't left its initial M x N bounding box after 2^(MN) generations then it has to be stationary. The smallest bound one can make is thus a single cell displacement of the whole pattern after 2^(MN) generations, for a speed of c/2^(MN). But since we can make bounding boxes arbitrarily large then there is no lower bound in an infinite plane.

For example, it's possible to drag the Demonoid construction arms as far apart as you like, making the replication cycle take longer. The bounding box goes up and the overall speed drops.
Physics: sophistication from simplicity.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by dvgrn » April 18th, 2016, 3:28 pm

biggiemac wrote:
calcyman wrote:If it's not a stationary object, at least one of the four edges of the bounding box must advance at a speed of Omega(sqrt(log(t))). Does that answer your question?
That doesn't really make it clear, because the relation between speed and t is confusing.
...
If something hasn't left its initial M x N bounding box after 2^(MN) generations then it has to be stationary.
Definitely confusing. There's no particular reason why a spaceship shouldn't leave its bounding box temporarily, is there? This slowest possible spaceship could perfectly well be highly non-monotonic.

So if the initial bounding box is big enough to contain a universal computer-constructor, or even some non-universal circuitry that calculates... I don't know, the Goodstein function for some value or other? ... then we can arrange to have the constructor wait until the computer has completed its task, and then build and trigger a slow-salvo seed that destroys the whole UCC and rebuilds it at a 1-cell offset.

That will be a perfectly good spaceship, even if the bounding box goes up to a square googolplex and back down again. So then the question is, what's a good tradeoff to aim for, between the slowness of a calculation task and the size of the calculation circuitry?

For packing into a smaller initial bounding box, it might be better to encode the destruction/reconstruction information into some kind of stable 2D memory structure. I'm not sure, though. A Geminoid-style glider tape folded into a 2D shape might be able to store construction information a lot more efficiently, especially if there's a way to call "subroutines" to build repeated structures like the reflectors along two edges of the memory area. It will certainly be easier to copy at a 1-cell offset, I would think -- though that's not really a necessary feature. Something like this could still be truly hideously slow even if it moved itself a thousand cells in each cycle.

None of these ultraslow self-constructing spaceships are going to be particularly compact -- but really a Caterloopillar isn't all that small either.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Caterloopillar WIP (all speeds < c/4)

Post by Apple Bottom » April 19th, 2016, 6:58 am

simsim314 wrote:EDIT I also think we should expand caterloopillar in the wiki, to specify all the constructed speeds. At least the interesting ones - say up to period 20, and smallest/fastest/slowest etc.
This sounds sensible to me.

In fact I'd suggest doing two things: listing the interesting speeds (using some generally-accepted notion of interestingness) on the main Caterloopillar page, and adding a auxilliary article listing all speeds for which Caterloopillars have explicitely been constructed.

That kind of "List of ${FOOBAR}" article is common enough on Wikipedia etc., and I think it would strike a good balance between the competing interests of keeping the main article uncluttered on one hand, and providing comprehensive information on an interesting and important piece of technology on the other.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » April 19th, 2016, 8:17 am

@Apple Bottom - my point was not to post all the available speeds at spaceship page, as it looks like real spam.

Having a list of links to all available speeds - is not a bad idea, but needs additional thought of how to avoid explosion. Maybe have some "collection" of caterloopillars, like Jason's collection of guns.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » May 3rd, 2016, 6:30 am

Here's a challenge: make a c/5648 caterloopillar.

I can't run Python scripts, so I'll leave that responsibility to someone else.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » May 3rd, 2016, 8:29 am

muzik wrote:Here's a challenge: make a c/5648 caterloopillar.
Why this speed? the script is currently limited by c/101 or something.
muzik wrote:I can't run Python scripts
Why?

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » May 3rd, 2016, 8:32 am

simsim314 wrote: Why this speed? the script is currently limited by c/101 or something.

I want something that travels at this speed:

Code: Select all

x = 12, y = 14, rule = B3457/S4568
4bo2bo$4b4o$2b8o$2b2ob2ob2o$obobo2bobobo$2ob6ob2o$ob3o2b3obo$3ob4ob3o$
2ob6ob2o$b3o4b3o$b3o4b3o$3b2o2b2o$3bo4bo$5b2o!
simsim314 wrote:Why?
Don't have access to a computer at this second. I'll see if I can download something that can run Python though

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » May 3rd, 2016, 11:17 am

muzik wrote:I want something that travels at this speed:
Heh... anyway the script can be modified to work with more speeds - but it would have some other limit, and it seems people are not interested in covering speeds with caterloopillar or finding the optimal size for some specific speed, it looks like the point of universal speed covering was proven, and the script is working for some wide enough range of speeds.

I'ts still interesting to beat the minimal designed ship record though.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by dvgrn » May 3rd, 2016, 5:08 pm

simsim314 wrote:I'ts still interesting to beat the minimal designed ship record though.
At the moment I'd be tempted to do that by reworking the Demonoid, actually, since the current design is nowhere near optimal. I suspect it can be brought down to around 20,000 ON cells, which might be a hard target for a Caterloopillar to beat.

I haven't come up with a single-channel design that seems likely to improve on the 0hd model -- though it might happen, if single-channel elbow operation recipes turn out to be within a factor of two of the efficiency of 0hd glider-pair recipes.

However, it's definitely possible to find a slow-salvo recipe for the current construction arm constellation that's shorter than 540 gliders. That recipe was generated completely by hand, with no time spent on optimizing it for the 0hd elbow-op library... In fact, the 0hd library didn't even exist when that slow salvo was compiled.

A revised slow salvo using one of the recent eater2 seeds, and a few other optimizations like using the cheapest possible lane to delete extra debris, could easily bring the population below 24,000, and just possibly below 20,000 with enough work.

I can see that the Caterloopillar's initial stage of creating a target block and then pushing it way out, can be replaced by something much lower population, just by building the block in the right place to begin with (right?) But that only reduces a small fraction at the front of the ship.
simsim314 wrote:There are many alternatives which could improve specific speeds. In particular one can send gliders to destroy the salvos, thus the only limitation on the period would be the period of the reading head.
I don't have a clear picture of where those gliders would come from -- is this just for the negative helix, or can you bounce gliders up to the front somehow, too? (Without increasing the total population to something huge, that is, like the shield bug vs. the Centipede.)

What are other likely reduction points? Might there be a way to use only even-phase *WSSes, for example, instead of a mix of even and odd? That would cut down the minimum population by five percent or so, if it didn't increase the *WSS population (which it probably would).

Of course, the Caterloopillar is an order of magnitude ahead on the bounding box already -- there's no way the Demonoid is going to catch up on that metric.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » May 3rd, 2016, 7:44 pm

I actually see three sources of Caterloopillar improvement:

1. Shortening the front push (which is irrelevant for lower speeds and is minor in any case). Actually I introduced it in some local tests, and it was pretty useless. For high periods it improved maybe by 2-3%, for low periods the distance between the reading heads was too large.

2. Using the skip operation more wisely. This optimization aims to add operations but decrease the distance between "none" operations, i.e. waiting for "magical" period adjustments. For c/8 the waiting couldn't be too long anyway, but for something like c/100 it could wait for 100 distances (which is not too large but currently costs about 50% of the ship).

3. Another small (but important) nuance is that the distance between the front and back in the script, was made intentionally wide - to reduce "chances" of any harm. This made the script universal, but less optimal. This cost is constant and is about extra 2K cells.

All in all I think I can safely say that reduction from the current best which is about 56K to around 25K should be achievable in relatively small amount of work.

Comparing this to Demonoid - tweaking the slow salvo is kinda hell. Maybe you could improve it, but it will take much more work.
dvgrn wrote:Without increasing the total population to something huge, that is, like the shield bug vs. the Centipede.
I was thinking about it again (specifically about chocoholic suggestion to replace the backward helix by self destructing gliders which bounce of some distant self maintaining "islands" of slow salvos), and I see no way such glider will cost less than *WSS. It will require *WSS just to allow it to self maintain itself. I think the self destruct is currently relatively cheap.

In other words - I now simply don't see any way to improve Caterloopillar other than small tweaking of the current script.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by Scorbie » May 4th, 2016, 6:42 am

Is there any way to make use of speed-specific optimizations, if there is any? Sadly I am not sure what kind of speed-specific optimizations there are... Maybe something like integrating the 17c/45 rxn or 31c/240 rxn.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » May 4th, 2016, 8:21 am

The helix is pretty optimized as well, 4 *WSS give you any step and speed you need - this is kinda hard to beat, with something specific - especially for larger steps.

EDIT Minimal caterloopillar step is 98 - I don't see a way one can beat 4 *WSS for such large step.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by calcyman » May 4th, 2016, 12:05 pm

dvgrn wrote:Of course, the Caterloopillar is an order of magnitude ahead on the bounding box already -- there's no way the Demonoid is going to catch up on that metric.
What about an orthogonal Demonoid which uses a tape of MWSSes? I think that has a very good chance of beating the smallest Caterloopillar, not least because H-to-MWSS and MWSS-to-G technology is so cheap.
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: Caterloopillar WIP (all speeds < c/4)

Post by dvgrn » May 5th, 2016, 4:28 pm

calcyman wrote:
dvgrn wrote:Of course, the Caterloopillar is an order of magnitude ahead on the bounding box already -- there's no way the Demonoid is going to catch up on that metric.
What about an orthogonal Demonoid which uses a tape of MWSSes? I think that has a very good chance of beating the smallest Caterloopillar, not least because H-to-MWSS and MWSS-to-G technology is so cheap.
H-to-MWSS technology is either quick to recover and expensive to construct, or Spartan and slow to recover and inexpensive to construct -- right? We don't have a small Spartan H-to-MWSS with a sub-100-tick recovery time. Presumably we'd also need a constructible G-to-H if we're using an MWSS-to-G, and even the cheaper 135-degree MWSS-to-G isn't quite Spartan and might cause expensive troubles with construction order.

It looks to me like the recipe for an Orthogonoid would turn out to explode pretty far beyond the size of a Caterloopillar, once you take all these details into account. The bounding box would probably be smaller than a Demonoid, just because it's a nice narrow rectangle instead of a diagonal line, but the population would be a lot higher.

The biggest piece of untouched Orthogonoid research is that if the construction arm uses signal pairs the way the current 0hd Demonoid does, then the signals would have to be *WSSes, not gliders. We don't have any elbow-op recipes for *WSS pairs, and we also don't have a decent small transparent *WSS-making component, let alone a Spartan *WSS edge shooter.

A Geminoid that moves diagonally but uses an orthogonal tape, couldn't use the Demonoid's mirror-image trick to cut the total amount of circuitry in half. An orthogonal-tape self-constructing spaceship that used gliders in its construction arm, would have to build twice as much circuitry, and then use a different half of it at the two ends of the tape. That's doable, but it doesn't seem like it would set any size or (especially) population records.

Maybe we could string together a single-channel Orthogonoid -- orthogonal tape _and_ orthogonal movement perpendicular to the tape. That could still use gliders for the construction arm. In fact, it might be a very nice application of single-channel technology, since the construction-arm elbow could always stay a safe distance away from the circuitry it was constructing.

But then we'd still need a Spartan H-to-MWSS with a recovery time of 90 ticks, or at least down around 120 ticks, so that the single-channel library will work. I think that would still be a pretty expensive piece of circuitry. (?)

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » June 28th, 2016, 8:42 am

Trying to complete a table on the wiki, what are the minimum populations for the c/9, c/11 and c/12 caterloopillars?

Also, apparently Daniel found a c/8 caterloopillar smaller than the one in the OP, but the file he attached doesn't seem to show it?

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » June 28th, 2016, 10:31 am

muzik wrote:what are the minimum populations for the c/9, c/11 and c/12 caterloopillars?
Need to calculate it... couldn't find any published numbers.
muzik wrote:Also, apparently Daniel found a c/8 caterloopillar smaller than the one in the OP, but the file he attached doesn't seem to show it?
I don't think he "found" a smaller one... it could be the script generates a smaller caterloopillar than initially posted (that one was generated with more manual labor). You can simply run the script and get it.

I think he managed to post c/21 cateloopillar, and he's also the only one who confirmed the script is working.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » June 28th, 2016, 10:48 am

simsim314 wrote:
muzik wrote:what are the minimum populations for the c/9, c/11 and c/12 caterloopillars?
Need to calculate it... couldn't find any published numbers.
I got bored checking, but the smallest number I got for c/9 was 169476.

So probably something below that.

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by dvgrn » June 28th, 2016, 1:31 pm

muzik wrote:
simsim314 wrote:
muzik wrote:what are the minimum populations for the c/9, c/11 and c/12 caterloopillars?
Need to calculate it... couldn't find any published numbers.
I got bored checking, but the smallest number I got for c/9 was 169476.

So probably something below that.
You can run Golly Python scripts, right? Don't let yourself get bored looking at numbers one generation at a time. That's what computers are for:

Code: Select all

# find-minimum-population.py
import golly as g

genstr=g.getstring("Enter number of generations to run:")
if not genstr.isdigit(): g.exit("Invalid number.")
gens=int(genstr)

p, minpopgen = int(g.getpop()), 0
for i in range(gens):
  g.run(1)
  q=int(g.getpop())
  if q<p: p,minpopgen=q,i
  g.show("Minimum population as of T="+str(i)+": " + str(p) + " at generation " + str(minpopgen))
  # g.update()
Laziness isn't generally worth advertising, but it can be very useful as motivation to keep looking for new ways to dodge tedious work...!

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » July 4th, 2016, 11:05 am

Being as stupid as I am, I've decided to list all of the caterloopillar-achieved speeds on the table of spaceship speeds, and, ehm, might need a bit of help completing that task.

I've created a separate page without them just to make sure things don't get entirely too crazy.


Of course, measuring the minimum population for each caterloopillar is also going to be a necessary task...

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Caterloopillar WIP (all speeds < c/4)

Post by simsim314 » July 4th, 2016, 11:49 am

muzik wrote: and, ehm, might need a bit of help completing that task.
You can see my two posts with more releavnt info, here and here (the published pop value refers to min. pop).

I also need to commit some caterloopillars, which are current record holders in size and speed.
muzik wrote:I've created a separate page without them just to make sure things don't get entirely too crazy.
I think copperhead had appeared in some soup (although it might be symmetric, yet it's still soup friendly).

And 4 engine cordership is definitely engineered from smaller components, although it's much less components than other engineered ships (4 instead of couple thousands).

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

Re: Caterloopillar WIP (all speeds < c/4)

Post by muzik » July 4th, 2016, 12:02 pm

simsim314 wrote:
muzik wrote: and, ehm, might need a bit of help completing that task.
You can see my two posts with more releavnt info, here and here (the published pop value refers to min. pop).
I'm mainly looking for the ones I haven't added to the page to be sorted by fastest speed first, so I can organise them by speed.
simsim314 wrote:
muzik wrote:I've created a separate page without them just to make sure things don't get entirely too crazy.
I think copperhead had appeared in some soup (although it might be symmetric, yet it's still soup friendly).

And 4 engine cordership is definitely engineered from smaller components, although it's much less components than other engineered ships (4 instead of couple thousands).
Copperhead's soup was definitely symmetric. I'm only listing assymetric soups, since those are the commonly accepted definition of natural. (Here's hoping for the future that the Loafer/Copperhead/C18Ship dream comes true)

The Corderships are a weird one. This begs the question; are corderships actually considered engineered? Who knows, one could emerge from a diagonally symmetric soup any day

Post Reply