A Challenge: Steerable Spaceship

[Eylrid]

I will pay $50 to the first person who creates an internally steerable spaceship. It must meet these requirements:

-Contains one or more memory loops
-Uses the information in the loop(s) to turn the spaceship
-Does not require anything external to operate (I.e. no still lives, oscillators, gliders, or other reactions not created by the spaceship)

A couple of things that are not necessary, but would be nice:
-Adjustable length memory loop(s)
-Inversions in the memory loop(s) for setting and resetting
-The ability to go diagonally and orthogonally

[calcyman]

Such devices are indeed possible, but I estimate that such a spaceship would be much larger than the Caterpillar.


Do you want me to add it to my comprehensive list of open problems, at:

http://calcyman.co.uk/life/problems.htm

[Eylrid]

Yes please.

I'll send you a PM with my name and email address.

[calcyman]

Andrew Wade's Gemini satisfies all of these conditions. You now officially owe him $50.

[dvgrn]

Andrew Wade's Gemini satisfies all of these conditions.

Are you sure? I think there's some room for interpretation here:

1) Technically there are no loops in a Gemini spaceship. (This is a lousy objection, I admit, and has an equally weaselly workaround: one could add a useless empty pair of 180-degree reflectors somewhere in the unused space in the middle of the replicator units and recompile the recipe, claiming that the loop always contains a "0"...)
2) Currently all Geminis move in a straight line.

Also, the program that tells a given Gemini variant how to move is very difficult to locate and modify. For example, I tried deleting one of the west construction arm's INC instructions to make a (1023, 5119)c/33699586 variant. I think that's what it would have been, anyway -- but it blew up, because the construction gliders were trying to cross the 24 channels in the southwest, in a slightly different location relative to the gliders in the channels. It would have been necessary to recompile the entire recipe to get a working spaceship, and the speed might even have changed as a result.

Seems like an improbably big effort for a "steerable" spaceship -- kind of like a car with wheels bolted into position, where you have to take the whole front end apart and put it together differently, to get it to start turning, and do the same all over when you want it to go straight again.

I'm just a bit worried that the intention of the award might have been to encourage someone to build a spaceship that you could program to move in different directions -- e.g., orthogonally for 16 times the spaceship's period, then diagonally for 25 times the period (assuming a constant period) -- and ideally the information about which way to move would be stored in a memory loop in some reasonably comprehensible form, so the program could be changed without redesigning the whole spaceship.

The Gemini certainly deserves a prize, but I think it's still up to the originator of this particular prize as to whether to award it. However, ignoring my rather silly objection #1 above, adding a channel to the Gemini and some circuitry to interpret it, or re-using an existing channel (the four destructor-arm channels are empty half the time, after all) could maybe produce an unambiguous winner.

(?)

[calcyman]

orthogonally for 16 times the spaceship's period, then diagonally for 25 times the period

Technically, that would be orthogonally for 16/41 of the period, and diagonally for 25/41 of the period.

1) Technically there are no loops in a Gemini spaceship.

Oh yes, I temporarily forgot about that. It's now at Eylrid's discretion as to whether he decides to award the prize.

2) Currently all Geminis move in a straight line.

Any pattern that doesn't move in a straight line grows in diameter (by at least O(sqrt(log(t)))), and thus not a spaceship in the classical sense.

[dvgrn]

orthogonally for 16 times the spaceship's period, then diagonally for 25 times the period

Technically, that would be orthogonally for 16/41 of the period, and diagonally for 25/41 of the period.

Yeah, that word "period" was a placeholder, and I forgot to go back and change it to something more precise. Assuming the spaceship in question is a self-constructing "teleporter" like the Gemini, as opposed to a track-laying "crawler" like the Caterpillar, I'm looking for a concept like "self-construction cycle" -- which coincides with the period for all existing spaceships, but would be shorter than the period in a programmable steerable spaceship.

2) Currently all Geminis move in a straight line.

Any pattern that doesn't move in a straight line grows in diameter (by at least O(sqrt(log(t)))), and thus not a spaceship in the classical sense.

A pattern that moves orthogonally for 16 self-construction cycles, then diagonally for 25 self-construction cycles, doesn't move in a straight line in the sense that I'm trying to convey here. Obviously a plot of this hypothetical "steerable" spaceship's location will be a straight line if you take measurements only at multiples of the full period of the spaceship. But a plot of every construction cycle will show the spaceship changing direction... periodically.

[calcyman]

But a plot of every construction cycle will show the spaceship changing direction... periodically.

Equally, one could argue that the switch engine travels horizontally for 48 generations, then vertically for another 48, which is what it certainly appears to do.

[dvgrn]

But a plot of every construction cycle will show the spaceship changing direction... periodically.

Equally, one could argue that the switch engine travels horizontally for 48 generations, then vertically for another 48, which is what it certainly appears to do.

Well, yes, one could argue that, but then I'd have to argue the other way... If you want to take the observation to an extreme, gliders travel horizontally one tick, stand still, one tick, travel vertically for one tick, etc -- measuring by the center of the bounding box or whatever. And *WSS spaceships travel diagonally, I think -- talk about counterintuitive!

But that's not what I mean by "changing direction", either. You can tell the difference between the four phases of a glider, or the 96 phases of a switch engine, and you can wait until a pattern gets back to its original configuration, and then say, "Aha! It's moved one cell northwest in 4 ticks -- must be a c/4 diagonal spaceship" or "8 cells northwest in 96 ticks -- it's a c/12 diagonal puffer."

But this hypothetical steerable spaceship is another kettle of fish entirely! You could watch it until it gets back to (what looks like) its original configuration, and for 16 cycles it goes due north, so you'd confidently diagnose it as an orthogonal spaceship. Unless you compare every new glider position to every old glider position, you wouldn't notice that it hasn't really completed a full period yet. And then, of course, you'd be very surprised when it suddenly takes off in a new direction and travels diagonally for 25 more cycles.

This would be qualitatively different behavior from anything we've seen so far, and even though of course it's ultimately traveling "in a straight line", that would suddenly be a lousy way to describe its behavior. Very similar to calling the Gemini "just a really fancy glider" because it's technically in the same pattern class as a glider, if you only look at it once every full period -- even though the intermediate stages by which it accomplishes its movement are completely novel.

[p46beth]

That results in a very ambiguous definition of "steerable." Arguably, someone not familiar with life might think the glider was moving orthogonally. And someone very familiar with universal constructors could note immediately that a "steerable" spaceship is in a distinctly different phase when it appears to change directions.

A (slightly) better way to determine if something has changed directions is if it completely reproduces the computer and constructor, but with a different input. However, this is still somewhat ambiguous, as you could debate which cells are input and which are part of the computer itself.