> What makes this an elementary knightship is that it isn't built out of smaller discrete components

How is that determined?

In other words, can't you take small components, smash them together to get a bigger thing, and then pass it off as elementary?

Don't we need to "reverse the hash function" to determine if it's possible to make Sir Robin (that's what thing thing is going to be called) out of smaller things?

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.

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.

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?

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).

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.

There's also a dropdown full of interesting patterns you can load up (with descriptions from mathematicians).

[0] http://symbolflux.com/conwayz/

From the talks I've seen a lot of it seems to stem from the idea of simple rules allowing a lot of complexity. He talks about other cellular automata other than Conway's Game of Life, but the ideas are similar.

http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere...

This idea comes up a little bit differently in Max Tegmark's book "Our Mathematical Universe" which I liked too.

So it compresses titanic data down to some Booleans and chess expressions.

Size: 4096 x 4096 Offset: (0,0) Def: GameA Opening Lib:C3 Turns: 2567

[&] Size: 512x 512 Offset: (12,0) Def: GameB Opening Lib:G42 Turns: 12

[!] Size: 4096 x 4096 Offset: (0,0) Def: GameD Opening Lib: FULL_HOUSE Turns: 0

Its a pretty nifty way to compress files beyond the point of no return, knowing that the deterministic knowledge of the game- allows for a full recreation of any file, given enough processing power and time.

There are of course some attempts to optimize the whole process- having often used game snapshots to fast-forward from and re-wind back too.

Do people searching for these rely on brute force to find interesting ships, or are there other techniques to designing them? It certainly doesn't look "designed", but almost organic.

It's a clever approach as modern SAT solvers are surprisingly powerful. I actually use this approach myself in some of my (personal) work, e.g. to automatically find execution paths through a target binary for reverse-engineering purposes.

I'm interested in the latter, do you have any readings/blogposts/books you would recommend?

SAT/SMT solving can be quite handy for assisting fuzzers in selecting good paths, which is something I've investigated in the past. Angr can help with that too, although the most recent developments in practical fuzzing have been in coverage-testing approaches (like afl) rather than in symbolic execution approaches.

I also play CTFs a fair bit, and in those we sometimes use Z3 and Boolector (two numerically-oriented SMT solvers) to solve challenges. As an example: https://github.com/pwning/public-writeup/tree/master/9447ctf...

I'm not really well versed in GOL, but from ths: http://www.conwaylife.com/wiki/Knightship

I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h

In contrast an elementary object, like a knightship, tends to be nice and small, and therefore highly valued as a building block for more powerful systems. Orthogonal and diagonal gliders see a ton of use in complex Life systems, and it's probable that the new knightship will see good use too (once people start building and exploring the requisite tooling - guns, eaters, and other reactions).

See https://niginsblog.wordpress.com/2016/03/07/new-spaceship-sp... for a rundown of the difference.

It is definitely possible, and extremely probable, that extremely large "elementary" structures exist - but we lack the computational power to find such things.

Well, guess that needs to be updated :D

https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...