Comment by Someone | Hacker News Reader

Comment by Someone | Hacker News Reader

Parent Full thread

”Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?”

For some, that is possible. Trivial examples are objects of zero, one, or two pixels; less trivial are gardens of Eden (http://conwaylife.com/w/index.php?title=Garden_of_eden)

However, I don’t think “elementary” is synonymous with “can’t possibly be the result of smaller things combining”. http://conwaylife.com/wiki/Elementary defines it as

”A pattern is said to be elementary if it is not reducible to a combination of smaller parts.”

If one takes two gardens of eden and place them far enough apart, the result is a new garden of Eden that ”can’t possibly be the result of smaller things combining” (even stronger: it can’t possibly be the result of anything), but it is reducible to smaller parts.

I don’t think there is a formal definition of ‘elementary’ that everybody can agree on. In the limit, only patterns of a single cell are elementary.

The "elementary" vs. "engineered" distinction might be clearer with an example of an engineered spaceship, like one of the Corderships: http://conwaylife.com/wiki/13-engine_Cordership .

Inside the 13-engine Cordership are thirteen switch engines, each of which moves at a twelfth of the speed of light, but leaves junk behind. The thirteen pieces basically collaborate on cleaning up each other's junk to make a clean spaceship.

It's very difficult to prove that a large elementary spaceship can't possibly be created by crashing gliders together (for example). Several elementary spaceships do in fact have known glider constructions, but that doesn't stop them from being elementary -- you can't pick those spaceships back apart into their constitutent gliders once they're constructed, and often they're traveling a totally different speed and direction than a glider anyway.

I understand that, but those are the easy ones, and I think they are the exception, when looking at all possible spaceships, rather than the spaceships we know of.

A definition for ‘elementary’ that I think is closest to intuition is that ‘elements’ are connected (for some definition of connected) subsets of a pattern do not touch other parts of the pattern and that would survive individually in isolation.

Problems with that definition are that, after cutting of the obvious elements, you may be left with stuff. Using the term ‘elementary’ implies that that stuff either must be elementary, or be built of other elements. The former is the easiest way out, but (as an extreme example) the resulting element might be a garden of Eden with a billion cells that, in isolation, would die out. Would you really want to call such a monster an element?

Also, if a pattern of <50 cells can be constructed from a few dozen carefully placed small ‘obvious elementary’ parts, less than 100 or so time units in the past, I think many would agree the pattern’s elements are those parts.

Problem 1: AFAIK, it is an open problem to decide whether such a set of items exists for a given pattern.

Problem 2: that set may not be unique, and there may not even be a unique smallest (for whatever definition chosen) one in the set of solutions.

Problem 3: if the smallest such set is way, way larger than the pattern it constructs, and must be constructed way, way in the past, do you still consider the pattern to be constructed from those many, many elementary parts?

Yeah, Problem 1 definitely is a (very difficult) open problem, not likely to be solved any time soon.

Problem 2 just looks to me like a known fact, not really a problem... and Problem 3 is only a problem if you don't accept the standard definition of "elementary", and/or if you worry too much about leftover pieces.

As soon as you can see two separate pieces inside a larger spaceship, and each of the pieces in isolation would travel at the same speed as that larger spaceship, then that larger spaceship is not an elementary spaceship.

Once you take out the recognizable pieces, there may well be sparks and other junk left over. But they might just be side effects of the interaction of the recognizable pieces, not anything that can function independently. There are way too many such fading sparks and such for each one to deserve its own name.

Minor side note -- no spaceship of any size will ever contain a Garden of Eden, because every spaceship by definition has at least one predecessor (itself).

> each of which moves at a twelfth of the speed of light

I presume this is cellular-automata jargon for moving one cell per cycle?

edit: btw, I just saw the discussion about not posting to HN yet on the boards. My apologies, had I seen it I would have waited. I only posted this because (to my surprise) it looked like nobody else had and GoL posts are usually pretty popular around here.

Yup, the "c" in spaceship speeds, like "(2,1)c/6", is the same c as in "E=mc^2". It's a good analogy -- one cell per cycle is the maximum possible speed that information can travel in the Life universe.

Reply on news.ycombinator.com