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

Caterloopillar WIP (all speeds < c/4)

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

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

Postby simsim314 » July 4th, 2016, 12:17 pm

muzik wrote: are corderships actually considered engineered?


My answer is definitely yes. Even if they can occur in soup with high probability, yet they were found by using simpler components and "logical manipulations" with those components, they by definition engineered. This is why Gosper gun is engineered in my opinion.

In other words: everything is "natural" in a sense that for every pattern there is some very rare soup that precedes it. The definition of naturality should be limited by some reasonable probability (like the probability to appear in a random soup > 1/10^12 or something).

Another point is that in my view symmetric soups should also be included in the definition natural objects, like the symmetrical ships are considered "elementary" although they're symmetrical (and symmetry is definitely a "designed" feature in those ships). Symmetry is natural feature.
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby dvgrn » July 4th, 2016, 2:00 pm

simsim314 wrote:
muzik wrote: are corderships actually considered engineered?


My answer is definitely yes. Even if they can occur in soup with high probability, yet they were found by using simpler components and "logical manipulations" with those components, they by definition engineered. This is why Gosper gun is engineered in my opinion.

Seems like a reasonable argument. Coming at it from a slightly different direction: Corderships are built out of natural puffers -- not the bare switch engine per se, but block-laying and glider-producing switch engines show up in C1 soups very regularly. So while they may be engineered, they're much less engineered than other types of macro-spaceships.

Is it worth having different terminology for minimally-engineered (Cordership), moderately-engineered (Caterpillar), and maximally-engineered (Demonoid) objects? The current distinction between "engineered" and "engineerable" seems a little too subtle, when it's really trying to distinguish "non-adjustable" vs. "adjustable".

What I've been using for the last several years is "engineered" for stuff like the various Corderships, high-period rakes, and so on... but then "self-supporting" for the Caterpillar, Centipede, HBKs, and waterbear, and "self-constructing" for any object that carries around a construction recipe for itself. Caterpillars and HBKs and so on don't contain their own construction recipe -- the positions of the pi climbers or the half-bakeries or whatever aren't encoded anywhere. They do the work of closing the cycle so that the pi climbers can keep climbing indefinitely, or the half-bakeries will continue to get activated by the right gliders... but the spaceship as a whole is definitely not self-constructing.

But you could convert a Demonoid glider stream into, say, a stream of loafers, and feed it into a completely different-looking loafer-based replicator unit, and it would still construct a Demonoid replicator unit. The construction data is important, but the particular encoding is irrelevant.

simsim314 wrote:Another point is that in my view symmetric soups should also be included in the definition natural objects, like the symmetrical ships are considered "elementary" although they're symmetrical (and symmetry is definitely a "designed" feature in those ships). Symmetry is natural feature.

People have been pretty consistent about calling symmetric-soup objects like the pufferfish "almost natural". Really big areas of perfect symmetry happen very-nearly-never in random soup, so there is something highly artificial about starting with a symmetric soup. But yes, the products of symmetric soup are still elementary and not engineered.
User avatar
dvgrn
Moderator
 
Posts: 5718
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

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

Postby simsim314 » July 4th, 2016, 2:40 pm

I think in a way the glider stream is preparing the "rail" for itself in Demonoid, similarly to the way pi climbers preparing its own rail in caterpillar. Just the rail in case of pi climbers are simple blinkers, while in case of demonoid is more complex conduit. No spaceship "contains" its own tape, so you always can say the tape is "gliding" over some sort of "self constructible" rails. The only question is how complex the rails are? In case of more complex ships the rails could be very complex and the tape can be pretty simple (gliders, or array of SLs), or the rail can be simple and the tape can contain all the logic (like in case of centipede/caterpillar/waterbear).

What's unique in case of complex rail and simple tape, is that due to this feature the speed is usually adjustable (Geminiods and cateloopillars have adjustable speeds), while when you place the logic into the tape, and the rail stay simple, you usually have very limited options for adjusting the speed.

EDIT Another way to look at it, is the option to add some artificial artifact (like SL array in shape of santa claus). All the designed ships can add such feature.
----

About constructability I agree - it should be considered continuous property. I would say the probability to appear in random soup is good estimation of the degree of entropy some component has, we should obviously get into logarithmic scale on this one.

----

Well why people use "almost natural" regarding objects appeared in symmetrical soup, but not "almost elementary" for ships appeared in symmetrical search? If the term elementary is placed to distinguish designed and not-designed ships, symmetry is definitely artificially designed property introduced into the search.

More than that, does ships found using zfind are designed or elementary (and this goes for any new search utility)? Are ships found by iterating different parameters during the search, like the new 3c/7 is designed? because it's everything but elementary, Tim Coe did a lot of tweaks and played with huge amount of parameters to find that one, it definitely looks more like designed to me than "elementary".

I think we currently have two distinguishable technologies to "find" ships. One technology is helping us to find very artificial and small ships, the other uses natural reaction to generate "big" ships. This is just current state, we could get into some "grey" area where medium size somewhat artificial ships are being built, using simple components (like we have in case of corderships).

I don't like this terminology - or some assumption that somehow designed ships are somehow worse. They're big yes, and because they're big they're less usable and less elegant, yes - but I do think all the current ships are "designed" and artificial in some way, except maybe the *WSS the glider and the SE puffers.

To make my point more clear: what is more probable, to find Gemini in random soup, or the spaghetti monster? If someone could show spaghetti monster is more probable than Gemini - I would agree to the distinction between designed and "elementary".
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby muzik » July 4th, 2016, 2:42 pm

I take it that corderships are now officially classed as engineered spaceships then?



Also, "elementary" spaceships are spaceships which cannot be broken down into any smaller spaceships, that actually take place on certain ship-driving reactions (like blinker syntheses as in the caterpillar). So the gliders in the c/7 diagonal lobster do not make the lobster an engineered spaceship. The spaghetti monster therefore is not engineered but elementary, despite its size.


Engineered spaceships don't have adjustable slopes or speeds; they are engineered by their own design.

Engineerable spaceships can have either controllable speeds or directions; their components are engineerable.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby dvgrn » July 4th, 2016, 3:52 pm

muzik wrote:I take it that corderships are now officially classed as engineered spaceships then?

Well, I'm not actually official enough to say for sure. I wouldn't mind throwing them into that category, but then again I wouldn't mind if they got their own category, along with pufferfish spaceships, and puffer-based spaceships in other rules. If they were just "puffer-based spaceships", would that make everyone happy?

Sticking a few puffers together to suppress each other's exhaust, and maybe adding an extra tagalong or so, is certainly a kind of engineering. But it's much simpler engineering, because the component pieces are capable of traveling at that speed without any external support.

muzik wrote:Engineered spaceships don't have adjustable slopes or speeds; they are engineered by their own design.
Engineerable spaceships can have either controllable speeds or directions; their components are engineerable.

Like Sphenocorona, I do understand the distinction -- but the two terms are so similar, and the underlying concepts are actually different enough, that I have to think about it every time.

When it comes right down to it, I'm unlikely to ever use "engineerable" as a category, just because "adjustable" seems so much clearer. Subcategories seem easier with "adjustable", too: HBKs and Demonoids (and eventually Orthogonoids) are adjustable-speed but fixed-slope. With Geminis the speed and direction are independently adjustable.

Maybe you could say something like "fixed-vector" for spaceships where both speed and direction are fixed. But that sounds kind of contrived. Maybe there's a better new term out there to be found... but usually this kind of classification causes fewer terminology wars, when all the terms have already come into common use.

[I've been trying to get the "self-supporting" vs. "self-constructing" distinction into common use for several years now, but I'm not sure that I've actually succeeded yet...!]
User avatar
dvgrn
Moderator
 
Posts: 5718
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

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

Postby muzik » July 4th, 2016, 3:54 pm

Elementary, engineered and adjustable it is then, if everyone else agrees!


I think that puffer-based should come under "engineered" though
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby A for awesome » July 4th, 2016, 3:56 pm

simsim314 wrote:To make my point more clear: what is more probable, to find Gemini in random soup, or the spaghetti monster? If someone could show spaghetti monster is more probable than Gemini - I would agree to the distinction between designed and "elementary".

I would say the spaghetti monster, unless there's some precursor to an entire Gemini that fits inside a 27x137 bounding box.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1822
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

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

Postby simsim314 » July 4th, 2016, 3:56 pm

I've done some analysis on the size of caterloopillar, and it turns out I'm very close to optimum.

For starters I should say the smallest caterloopillar is of the size of ~54K and speed c/92.

1. First of all the critique of the long front - the front costs only ~2K (less than 4%).

2. The recipe consists of ~20 *WSS recipes (or 40 in both directions), so we get ~ 1.35K per *WSS recipe.

3. Out of the 1.35K:
~500 is only the reading heads (front and back).
~650 is the recipe "unfolded", SLs for the recipe + slow salvo in progress.
~200 is the skip operation "vanil blocks".

Obviously it's pretty rough estimates on average. But looking where we can cut here:

1. The front ~4%
2. The movement recipes ~ 5%-10% (they're close to optimal)
3. Balancing SKIP operations and movement recipes ~ 5% as well.

All the estimates are somewhat optimistic, as some work has been done already to optimize all these aspects (except the front). So all in all I can max cut by 20% even in the best scenario, and after a lot of hard work. So I still don't get to 25K range as I hoped. But I think it's cool caterloopillar got so close to the optimal. 54K is definitely well below any other constructible ship except the most tiny of them all - the demonoid. I probably can optimize it to beat the 10-hd demonoid, but not the 0-hd.
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby simsim314 » July 4th, 2016, 4:02 pm

A for awesome wrote:I would say the spaghetti monster, unless there's some precursor to an entire Gemini that fits inside a 27x137 bounding box.


I see no reason to limit the bounding box.

In other words I can formulate my question: how big the universe should, be filled with random stuff, so that the probability of appearing of spaghetti monster in it would be > 0.5. Using this formulation we start from extremely large universe, where every known pattern could fit.

Can you prove spaghetti monster universe is smaller than gemini in such formulation?
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby muzik » July 4th, 2016, 4:17 pm

Challenge: find a predecessor for a Geminoid-type spaceship that fits in an smaller bounding box than the spaghetti monster itself.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby simsim314 » July 4th, 2016, 4:19 pm

@muzik - I've added few speeds and min. count to your page. I must admit this is very tedious and boring for me... I would say that everyone should build some caterloopillar using the script, and say they were the first that built a ship of this particular speed :) And post it to your page.
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby muzik » July 4th, 2016, 4:21 pm

I actually started a page in my user page to list purely caterloopillars, but gave up on it.

Yes, I'm kinda lazy. I just want to know where the 2c/x and such would fit in, adding them is the easy part
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby BlinkerSpawn » July 4th, 2016, 4:56 pm

Would it be possible for someone to convert the script for generating caterloopillars into Lua?
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image
User avatar
BlinkerSpawn
 
Posts: 1877
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

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

Postby simsim314 » July 4th, 2016, 5:05 pm

Well yes it should be possible with some effort, but for what purpose? Python is working for most OS...
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby Scorbie » July 4th, 2016, 7:49 pm

simsim314 wrote:Well yes it should be possible with some effort, but for what purpose? Python is working for most OS...
One reason I can think of is speed. (Not for this case) There are situations where a for loop in python is the bottleneck and you can't really do anything about it... Then I guess you would have to rewrite the whole thing in Lua. I would rather write in Lua in the first place.
Of course I don't think there is any need to port a already working python script to Lua.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1380
Joined: December 7th, 2013, 1:05 am

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

Postby muzik » July 5th, 2016, 10:11 am

I have listed all of the caterloopillar speeds posted on this thread, although knowing on my luck there's probably a bunch more of them somewhere that I don't know about. (Also, come to think of it, are there any more Gemini/Demonoid ships that have been posted on this forum?)

Anyway, can the c/8 or 31c/240 be shrunk anymore simply by running the script again? I can't test this myself due to not having access to a computer.
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby Apple Bottom » July 5th, 2016, 2:31 pm

simsim314 wrote:I think copperhead had appeared in some soup (although it might be symmetric, yet it's still soup friendly).


Aye, It's appeared twice in D2_+2 so far.
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!
User avatar
Apple Bottom
 
Posts: 1025
Joined: July 27th, 2015, 2:06 pm

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

Postby simsim314 » July 5th, 2016, 3:09 pm

@muzik - great (on adding all the existing pillars)! I'll try to fill the missing squares, and add some additional pillars later on...
User avatar
simsim314
 
Posts: 1686
Joined: February 10th, 2014, 1:27 pm

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

Postby muzik » July 5th, 2016, 3:23 pm

'Twas a tedious job (English translation: prisons of the world, please use this as your form of execution).

Back when I ran drc's "smaller c/8", I got what didn't look like a caterloopillar at all...

Also, why can't speeds like c/14, c/18 and c/26 exist?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby drc » July 5th, 2016, 3:52 pm

muzik wrote:'Back when I ran drc's "smaller c/8", I got what didn't look like a caterloopillar at all...

The script was giving errors at that time
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

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

Postby muzik » July 5th, 2016, 4:01 pm

drc wrote:
muzik wrote:'Back when I ran drc's "smaller c/8", I got what didn't look like a caterloopillar at all...

The script was giving errors at that time

so you didn't actually get a new c/8... sad
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3310
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Postby gameoflifemaniac » June 7th, 2017, 11:03 am

What's up with the c/92 caterloopillar? You didn't upload it.
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...
User avatar
gameoflifemaniac
 
Posts: 752
Joined: January 22nd, 2017, 11:17 am
Location: There too

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

Postby calcyman » July 18th, 2018, 9:03 am

dvgrn wrote:
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 seems you were correct after all: according to the LifeWiki, the Orthogonoid is 707-by-868856 and the c/8 Caterloopillar is 734-by-514927. I suspect your boustrophedonic design could bring the Orthogonoid down below the Caterloopillar, however.

(What is the contest, exactly? To find the smallest-bounding-box spaceship that's slower than c/12?)
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 2060
Joined: June 1st, 2009, 4:32 pm

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

Postby gameoflifemaniac » July 18th, 2018, 10:14 am

I was waiting for an answer for over a year, and nobody noticed my post. When nobody was answering my question, I deleted my post, and still nobody answered! THAT ISN'T FAIR!!!
Also, why didn't anyone answer?
I wrote:What's up with the c/92 caterloopillar? You didn't upload it.
Last edited by gameoflifemaniac on July 18th, 2018, 11:24 am, edited 1 time in total.
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...
User avatar
gameoflifemaniac
 
Posts: 752
Joined: January 22nd, 2017, 11:17 am
Location: There too

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

Postby dvgrn » July 18th, 2018, 10:35 am

calcyman wrote:It seems you were correct after all: according to the LifeWiki, the Orthogonoid is 707-by-868856 and the c/8 Caterloopillar is 734-by-514927. I suspect your boustrophedonic design could bring the Orthogonoid down below the Caterloopillar, however.

Not sure why it would -- the length of the MWSS recipe would stay about the same, and every time you fold it over and reduce the width, you'll increase the height proportionally. Not much change to the bounding box, except that an additional width has to be added, a fair fraction of the height of the square Orthogonoid (because the elbows stick out so much farther).

There are various optimizations that could be applied to the Orthogonoid that would probably make it competitive with the Caterloopillar. But then there are optimizations that could be applied to the Caterloopillar that would make it a good bit smaller, too! No idea who would win that race in the end.

calcyman wrote:(What is the contest, exactly? To find the smallest-bounding-box spaceship that's slower than c/12?)

Don't know for sure, it's not really my contest... these days I'm trying to avoid getting fixated on metrics and new-record-smallest things as much as possible. However, there's some documentary evidence that the current target to beat is the waterbear. 13295×28010 is 372392950, with about 198K cells, where the c/8 Caterloopillar is 734×514927 = 377956418 with 233K cells.

gameoflifemaniac wrote:Also, why didn't you (that 'you' is in the plural form) answer?
I wrote:What's up with the c/92 caterloopillar? You didn't upload it.

I can't answer in the plural. But just speaking for myself, I didn't answer because I couldn't find anything useful anywhere about a c/92 Caterloopillar.

EDIT: The two mentions of the c/92 in this thread are here and here.
The second of these links gives the current state of the art for smallest Caterloopillars.

However, this isn't entirely relevant to calcyman's contest question -- simsim314 seems to have been talking about "smallest" in terms of population, where the 0hd Demonoid wins hands down (27250 cells, almost an order of magnitude smaller) rather than bounding box (where it definitely doesn't -- 55010×54964 = 3023569640, almost an order of magnitude larger.)
User avatar
dvgrn
Moderator
 
Posts: 5718
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Previous

Return to Patterns

Who is online

Users browsing this forum: No registered users and 3 guests