Elementary Knightship found in Conway's Game of Life | Hacker News Reader

Elementary Knightship found in Conway's Game of Life

conwaylife.com

733 pointsvanderZwan143 comments

Context: a knightship is a glider (a structure that translates itself across the Life grid periodically) which moves 2 horizontal units for each 1 vertical unit (or vice-versa if rotated). This is in contrast to e.g. the most popular 3x3 glider which moves diagonally (1 for 1). A knightship is a type of oblique glider - one that doesn't move orthogonally (only horizontal/vertical) or 45º diagonally.

What makes this an elementary knightship is that it isn't built out of smaller discrete components, unlike (for example) the oblique glider Waterbear (http://conwaylife.com/wiki/Waterbear). It's the first elementary oblique glider discovered.

It also happens to move exactly 2 vertical units for each 1 horizontal unit of motion, and carries this out in 6 time-steps (the theoretical minimum). Thus, in some sense it has the simplest movement of any possible knightship.

If a genetic algorithm were used to search it seems like the fitness function is obvious (it moves across for ever two moves up using a minimum number of iterations), but the mating function is not obvious. So I'm wondering if it's a brute force sort of search.

People have tried to use genetic algorithms to search for patterns in Life, but have been unsuccessful because the evolution of a pattern is very sensitive to initial conditions.

Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.

I've done a lot of work with GAs, and they've got a place, but ironically Life is not where they belong. Apparently they're using SAT solvers for the search, which is a lot more reasonable. The problem is exactly as you state it -- there's no fitness function that can take you from infeasibility to feasibility.

A combination could be interesting - SAT to smooth the space for a GA search.

Yeah, a lot of the original work on how GAs would optimize NP-complete problems is pure hand-waving and wishful thinking. Building-block theory, schema processing, it all sounds nice, but tends to result in disappointment. The thing GAs are actually good at is population-based search -- maintaining a bunch of alternative ideas at once. Either your suggestion of using GAs as a local optimizer for the non-satisfiability part of a mixed problem, or the inverse, using the GA to suggest starting points and using a SAT solver for the local search, is much more likely to produce interesting results. It's an idea I keep coming back to, although I still haven't struck gold with it.

Thanks for the explanation!

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.

The ship definitely wasn't "designed", but a SAT solver was used rather than direct brute force and constraints were used to cut down the search space (for example looking for a long-and-thin ship rather than one of arbitrary shape).

The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master

The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py), part of his larger "MetaSAT" project, which poses the problem of finding an oblique glider as a set of SAT constraints. Additional heuristic constraints were added to limit the search space. ikpx passes the resulting ball of constraints to a SAT solver, which does the computational work of attempting to find a satisfying solution.

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.

>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?

Take a look at Angr (http://angr.io/), which implements symbolic execution + SMT solving to analyze program execution (not my work, although I know a number of the authors).

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 find Game of Life utterly fascinating. Every time I read about it, I find myself wanting to understand more of the memephere surrounding it. One question that arises in me here:

> 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?

It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.

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

I haven't read it yet, but you'd probably find Stephen Wolfram's "A New Kind of Science" pretty interesting.

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.

If you want to experiment some more, I made this little webgl app [0] that makes it easy to mess with Conway's GoL while it's executing (you hold shift, which pauses the simulation, and click on cells to toggle them on or off). It's easy to 'paint' some basic gliders (e.g. http://images.slideplayer.com/25/8056158/slides/slide_3.jpg), then un-pause and watch them go off for instance. Or just try drawing a vertical or horizontal line of three cells (you get a simple oscillator), then try adding or removing things to it.

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

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

It's actually easily provable, and simply by observation, because "smaller things combining" has a much simpler definition than what you're assuming! What it actually refers to is how some spaceships, such as the Waterbear -- https://www.youtube.com/watch?v=on3ZLLKQp-4 -- are constructed explicitly as a circuit of building blocks (as you can see in the video), whereas elementary spaceships like this knightship consist of "space dust" that isn't separable into independently-functioning components.

Also remember Conways compression- any series of bytes, could be interpreted as the endresult of several conway games, layed over one another with relational operations.

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.

Are there non-elementary knightships that move 2v1h?

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 principle, one could construct a non-elementary knightship (the Geminoid construction is said to be capable of this - essentially it's a giant universal constructor that can be "programmed" to reconstruct itself an arbitrary distance from its initial position), but they're rather less interesting since they tend to be very large and not useful as building blocks.

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.

also self-contained glider that leave no structures behind and don't require structure to move are essential in repeating mechanism, since they leave the path in a known state, i.e.

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

> This table does not include oblique speeds, which causes little inconvenience because no elementary oblique ships are known.

Well, guess that needs to be updated :D

Another key point about this knightship, ignoring that it's elementary, is that it also moves at the fastest possible speed of 1/6 in an oblique direction. This had never been done before. The pre-existing non-elementary ships are all quite slow and it's hard to imagine them hitting the maximum possible speed.

Here it is for anyone interested (click the image)

http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a3...

Click the text "Show In Viewer" above to code snippet in the OP to watch it working.

I don't see "Show In Viewer", do I need an account?

Edit: Not the same page, but you can find an animation of it here: http://conwaylife.com/wiki/282P6H2V1

Perhaps you have JS disabled? It opens an interactive widget.

For me, in Chrome, I could not find "Show In Viewer", but the static preview image on the left side has a "launch" text splash when hovering. Clicking it opens a player with play/pause/step and other functionality.

And to play around with: https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873

From the comments in the link:

  FlameandFury » March 6th, 2018, 11:52 pm
  
  I don't know when people started seriously searching for 
  knightships, but this is the first elementary spaceship to 
  have a new slope in 48 years. As well, it's been 14 years 
  since the almost-knightship was discovered. Congrats!

Its a long time coming! Congrats!

It's not often that I find a post that, after reading it, I have absolutely no understanding of what I just read.

Usually I have at least some very basic knowledge of the topic at hand.

I guess I should start by reading up on Conway's Game of Life...

You might enjoy reading Glory Season by David Brin. It's a scifi novel with pirates and a competitive version of Conway's Game of Life- it's not central to the plot, but I've forgotten the plot and still remember Life. I read it several years ago and it piqued my interest the way Brin describes the time spent searching for new patterns.

It won't help you understand the mathematics of the game, but it might help you appreciate the beauty.

Conway's Game of Life is probably interesting to most people here because it's a programming / mathy thing. And it's very worth exploring that angle.

However it's also worth noting what it is in far more general terms. It's a system with very simple rules (only 4) that can produce very complex looking behavior. And then you could ask yourself where else you might find similar systems.

The highly influential composer Steve Reich experimented with this idea in some of his earlist compositions. "It's Gonna Rain" was simply two tape recorders "perfectly" synced to play the same recorded loop. Of course they fell out of time and the resulting piece is pretty complex when you consider the source system is so simple.

Brian Eno in turn was influenced by this, is also a fan of Life, and has used and spoken often about very simple musical systems that produce very complex sounds or songs.

The idea in general is more far reaching than one might guess by looking at the game, and is worth becoming familiar with.

Quantifying the complexity of the GoL ruleset is slightly more complicated than enumerating the rules, I would imagine.

Certainly more complicated, but we do know the answer. It's Turing-complete.

http://rendell-attic.org/gol/tm.htm

Isn't that the same as the point I was making? Systems with extremely simply rules can be complex. Am I missing something subtler that you're trying to say? A child can understand the rules of GoL and "play" it with pencil and paper. That's what is simple about it. The resulting behavior of the system is complex.

Rutherford Chang made a composition of 100 White Albums played at once!

https://gizmodo.com/listen-to-100-white-albums-played-at-onc...

Very cool. What was very surprising to me though was just how little the resulting complexity changes when you increase the source complexity from 2 sources (Reich) to 100 sources. And Reich was just a voice. Not an entire band. Although I think all these experiments are interesting, I am most fascinated by the simplest systems that result in the most complex behavior.

The first elementary non-orthogonal, non-diagonal glider has been found.

Small (as of now) summary on the Life wiki:

http://conwaylife.com/wiki/282P6H2V1

What does "elementary" mean in this context?

I think it means self-contained, that is, not "built up" from other things colliding and interacting.

http://conwaylife.com/wiki/Elementary

tantalor is correct. If you look on the knightship[0] page links a non-elementary ship: the Waterbear[1][2]. It is essentially a circuit built out of gliders, rather than a compact mass.

[0] http://conwaylife.com/wiki/Knightship

[1] http://conwaylife.com/wiki/Waterbear

[2] https://www.youtube.com/watch?v=on3ZLLKQp-4

That waterbear looks very complex. How did they ever manage to find it?

I'm not a part of the subculture, but every time I go down the rabbit hole of the discussion boards I get the impression it's one with crazy levels of dedication, and one that draws very particular kind of mathematics & programmer types of minds (honestly, it's a lot of fun to see them geek out over it every time I do, even if I can't follow 90% of what they're saying).

So my best guess is: a mixture of mathematics, brute force searching, and lots of passionate on-line discussion with fellow nerds.

Its software built up from useful abstract blocks. Small parts like generators, gliders and eaters are used to build an information storage tape, and a tape fed universal constructor.

From there it's the "simple" process of designing a tape and constructor setup that will build a copy of itself at a certain offset, and delete itself upon completion.

The part above about "tape and constructor" is exactly right for the self-constructing Gemini spaceship and its descendants. But it's not quite right for the waterbear. There's no universal constructor in the waterbear, or in its relatives the Centipede and the original Caterpillar.

Large parts of these macro-spaceships never get constructed or destroyed, they just travel along a support structure. That support structure is the only thing that gets constructed, and the construction recipe is encoded not in a simple "tape" glider stream but in the entire body of the spaceship.

Self-supporting spaceships like the waterbear are built with a very limited "toolkit" that only works at one particular speed. In general they're harder to put together successfully, and thus in a way are more impressive than self-constructing spaceships. Once you have a universal constructor, after all, you can build anything that's buildable. The trick is figuring out how to get along without that much power.

It wasn't "found", rather built from smaller components (that were found, of course, and by various computer-aided search techniques plus manual finagling). Its final assembler released a decently-quick rundown in the form of a video recording: https://www.youtube.com/watch?v=on3ZLLKQp-4

Is there a more compact or well-defined way to phrase this? Does "elementary" mean that by removing any arbitrary n cells, this structure won't exhibit the intended behavior? Or it won't exhibit any "interesting" behavior at all? Or does it mean that no subset of the cells exhibit any interesting behavior on their own?

From the looks of it, no actual subset of it would form a functional system, so it is itself a fundamental unit?

That's basically right. Remove any one cell or any subgroup from the knightship, and it's no longer a working spaceship -- at least not one that moves the same speed!

There are "optional extras" that can be added or removed from some spaceships. These are called "tagalongs", and aren't considered to be part of the ship. That can get a little complicated, too, though, like with another recent-ish discovery: http://conwaylife.com/wiki/Fireship .

from what I can gather from the answers given here, it means "doesn't contain any gliders"

That is a pretty amazing result. I enjoy reading the life forum as it has an entire set of nomenclature and vernacular that allow experienced users/explorers/researchers communicate really complex interactions in a concise an unambiguous way. It really drives home the depth of the rabbit hole from something that started so simply and elegantly in the 70's.

The names they give these things are so cool. Frothing spaceship, oblique glider waterbear, 10hd demonoid, weekender, loafer.

So it's deep rabbit holes full of precise arcane nomenclature and vernacular that you like huh? ;) Are you ready to have your mind blown? Don't click this link unless you're sitting down and have a lot of time:

http://lazyslug.no-ip.biz/lifeview/plugin/lexicon/lexlv.html

Marvin the Paranoid Android: "Life! Don't talk to me about life!" ... "Making it up?" said Marvin, swiveling his head in a parody of astonishment, "Why should I want to make anything up? Life's bad enough as it is without wanting to invent any more of it."

  x = 31, y = 79, rule = B3/S23
  4b2o$4bo2bo$4bo3bo$6b3o$2b2o6b4o$2bob2o4b4o$bo4bo6b3o$2b4o4b2o3bo$o9b
  2o$bo3bo$6b3o2b2o2bo$2b2o7bo4bo$13bob2o$10b2o6bo$11b2ob3obo$10b2o3bo2b
  o$10bobo2b2o$10bo2bobobo$10b3o6bo$11bobobo3bo$14b2obobo$11bo6b3o2$11bo
  9bo$11bo3bo6bo$12bo5b5o$12b3o$16b2o$13b3o2bo$11bob3obo$10bo3bo2bo$11bo
  4b2ob3o$13b4obo4b2o$13bob4o4b2o$19bo$20bo2b2o$20b2o$21b5o$25b2o$19b3o
  6bo$20bobo3bobo$19bo3bo3bo$19bo3b2o$18bo6bob3o$19b2o3bo3b2o$20b4o2bo2b
  o$22b2o3bo$21bo$21b2obo$20bo$19b5o$19bo4bo$18b3ob3o$18bob5o$18bo$20bo$
  16bo4b4o$20b4ob2o$17b3o4bo$24bobo$28bo$24bo2b2o$25b3o$22b2o$21b3o5bo$
  24b2o2bobo$21bo2b3obobo$22b2obo2bo$24bobo2b2o$26b2o$22b3o4bo$22b3o4bo$
  23b2o3b3o$24b2ob2o$25b2o$25bo2$24b2o$26bo!

Could someone please kindly explain what all this means?

Right above the code, click "Show in Viewer". It'll bring up a player. Click the play button and adjust speed to your liking.

FYI, it looks like the "Show in Viewer" button is not displayed if JavaScript is disabled.

Cheers.

I still don't get it, but at least I got visuals now :)

It's a run length encoded version of that pattern:

http://www.conwaylife.com/wiki/RLE

There is a LifeViewer link up top, I captured it on Imgur just in case it isn't loading for you. https://imgur.com/a/yNF5a

I don't formally understand what knightship means in this context. I'd really love an ELI5. I've always been interested in Conway's game, and I'm excited to find this forum but I feel like I'm missing something big here.

I have run the things in the viewer and this looks to be a collective that is extremely strong in one direction. The follow up posts are throwing other gliders at it and them being destroyed. Knightship maybe is just being impervious to disruption? What is the elementary context? That it is huge and the pattern can now be reduced?

EDIT: carlob's post below pointed me to the wiki[1]. I still feel like my questions stand and could be elaborated on.

[1] http://www.conwaylife.com/wiki/Knightship

A knightship is any spaceship that moves like a knight in chess - i.e. neither orthogonally, nor diagonally but rather at a slant.

A spaceship is any cyclical pattern that ends in a different position to where it started.

Elementary means it's not composed from other, smaller entitiies. You can compose a lot of stuff from gliders and other elements.

Thank you! Very informative. I'm excited to play with GoL this weekend and experiment with it.

I can reccomend Golly - one of the algorithms it uses (Hashlife) is interesting in itself. Also, the lifeWiki is fascinating.

There's a good Dr Dobbs article about Hashlife, 'An algorithm for compressing space and time'

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...

Wow, the Elementary constraint really blows my mind. I've seen all sorts of crazy machinery built up out of gliders and reactions and such, but the fact that this new entity is "purpose-built" without any sub-elements is what I find to be the most impressive.

Here's an idea that I once had about how to visually determine if a program terminates or not:

Convert a program to a Game of Life equivalent program. Observe if there are any run-away gliders. If there are, the original program doesn't terminate.

as long as execution is proceeding without generating any gliders, then you don't know whether gliders will be generated in the future. in addition, if you have gliders, you have no guarantees that another structure won't catch up to it and end its gliding.

Many gliders move at the theoretical maximum rate on the Life board, so it won’t be possible to catch them.

I believe c/4 is indeed the fastest possible diagonal speed for a spaceship, does anyone know if a proof exists?

Yes, there's a fairly simple proof, specific to the B3/S23 Life rule, not true for all similar CA rules. Unfortunately this comment box is too small to contain it... and the proof only applies to structures traveling through empty space. If you're allowed to have pre-existing live cells ahead of the glider, there are known "wires" that transmit information diagonally at 2c/3, easily fast enough to get ahead of a glider and stop it.

This blog post has a explanation of the proof. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...

This doesn't seem to account for internally contained gliders. I.e. ones that are produced and consumed continuously.

This may be a more general form of what you're describing: look for small parts of programs (which re-appear often in many programs) which are proven to never terminate; if any of those simple non-executing subprograms are found, the larger program also will never terminate.

This is a valid method of deciding whether a program hangs. Another very simple approach is searching for global state recurrences (if your program goes back to exact same state at least once, and it is deterministic, then it never halts).

Note this has no bearing on the Halting problem though (famously proven impossible). You cannot decide whether an arbitrary very complicated program halts -- it may do all sorts of weird stuff that doesn't involve any of the previous behavior (having necessary subfunctions never terminate or global recurrence) -- it could try counting up to infinity until a certain complicated binary function of the number is true, then you have to decide the truthiness of this arbitrary function. In general you face a self-referential problem: imagine you try deciding whether a program of size N halts if it runs for too long. You'd need a program (say of size K) that produces a function f(N) of maximum running time for programs of size up to N -- then you could just check whether a program runs for more than f(N) steps. But by definition your program cannot run for more than f(K) steps, thus it cannot output a number greater than 2^(f(K)). Thus your program can only decide finitely many instances, and is not an algorithm (instead it is a sort of compressed look up table).

The proof of the Halting problem undecidability is more general, but uses similar self-referential arguments.

I like to think of it this way: an algorithm is really a compressor function. It compressed an infinite set of (input->output) relations into a finite program. But some infinite sets are inherently incompressible -- think a string of random numbers -- and in particular the set of all programs. Incompressible (actually finitely compressible) sets must exist because otherwise you would have infinitely many different sets that are output of finitely many programs, which is obviously impossible (this is the pigeonhole principle).

I like the idea behind your compression analogy, but it doesn't quite work. In particular, you assume the solution when saying that the set of all programs is incompressible. Indeed, there are programs which operate on the set of all programs, e.g. trivially "is the first bit of the program a 1".

I think you're correctly proving that non-computable functions exist (though the proof needs to mention countable vs uncountable infinities I think, based on a power set over the input/output set), but you still need some sort of self referential statement to prove the halting problem.

Oh yea my bad, I meant the set of all halting functions (which is (program->halts)) -- those are incompressible (again actually finitely compressible). The set of all programs can be trivially enumerated depending on the Turing machine (it's usually just a form of the set of binary natural numbers).

Note I did not prove incompressibility, only that there exist some incompressible functions; indeed there are as many functions as there are real numbers (in cardinality), so almost every function is incompressible! (imagine all different strings of random bits) For the halting function I believe the proof is a little involved and can be found on the book "Elements of Information Theory".

I find wikipedia's proof (https://en.wikipedia.org/wiki/Halting_problem#Proof_concept) not quite illuminating though, since it is a basic proof by contradiction. Those tend to leave you wondering if you cannot replace the halting function halt(x) with a self-reference-free function halt_noself(x). Compressibility give a wider intuition that sure, there are special subsets of the halting function (program->halts) that are compressible, but in general it will be incompressible, and therefore a program will only be able to decide finitely many sequential programs -- and this table can only be done by a "luck-based" search: you test the programs to see if they halt. The ones that do not halt in any reasonable amount of time, you may try searching the space of proofs that it doesn't halt. This search is again undecidable, because at some point there will be a program which doesn't halt but that you cannot prove.

So in some ways the best you can do is grow the list with holes such as "program 1 halts, program 2 does not halt (proof), ...., program k-1 halts, program k ???, program k+1 halts, ..." -- you may never be able to fill any particular hole. You can also build a set of heuristics to accelerate both the simulation of the programs (to show they halt) and the evaluation of proofs (to show they do not halt).

This is essentially the process by which we do mathematics, or even computer science :) We use a growing set of heuristics to prove statements we deem "interesting" or "useful", and sometimes simple statements will come up (such as Collatz conjecture, Goldbach's, Twin primes, Riemman hypothesis, ...) that we cannot prove and we do not know if we will ever be able to.

Most (non-trivial) well-behaved programs contain at least a single `while true`which is then broken by another piece of logic, so your method doesn't sound very useful to me.

If they are broken by another piece of logic then they can't be proven to not terminate.

Well, this is part of the fun the halting problem - this can be proven to terminate in some cases but not in general

It's not sufficient to find a small part that is proven to never terminate - you still need to prove if that small part will ever be reached, which is impossible in the general case.

  if (someveryhardproblem()) infiniteloop();

can't be verified to halt or not without solving the very hard (and potentially impossible) problem first, even though the program contains a potentially non-dead subprogram that can be proven to never terminate.

This is, I think, the moral equivalent of checking to see if the program has started executing a “while(1) ;” loop (e.g. by finding that the current instruction is a “jump $pc”, ignoring multithreading). Although it definitely proves that a program doesn’t terminate, the converse is not true - most “interesting” non-terminating programs aren’t just busy-looping infinitely, they’re just performing computations that happen to have no way of ending. Similarly, a Life machine might just sit there and push gliders around in a circle forever, without sending out an infinite stream.

I suppose that this depends on the formulation of the problem, but these gliders might make sense as outputs (side effects) independent of the main program, which itself would be expected to terminate.

you would have to prove to that the Turing complete part of your simulation doesn't construct a glider that has never been seen before and moves so fast that it catches and terminates the run away gliders.

It only makes sense if a program encoding in game of life is reasonably efficient. I highly doubt that's the case. But sure, ideas could be adopted.

Also having no runaway gliders is not proof of termination.

No, we have mathematical proof that in game of life the known gliders (c/4 diagonally or c/2 orthogonally) are as fast as possible, there cannot be faster gliders.

But what about this new non-orthogonal glider that we're discussing?

A glider that moves n cells horizontally and m cells vertically can do so only every 2*(n+m) generations. So this glider is optimal, it moves (2,1) every 6 generations.

Sir Robin moves at (2,1)c/6, meaning 2c/6 (or c/3) in one direction and c/6 in the other. This is apparently the maximum speed possible at this slope.

It's not faster, so it can't ever catch the "default" gliders if it's sent out afterwards. If a glider is moving at the provably optimal speed, then nothing can be faster.

I love the name Sir Robin, but to me it looks like there is the profile of a cat at the top:

http://www.conwaylife.com/wiki/Knightship

Sort of a tangent, but I'd be curious to know what sort of recent advances there have been in the study or applications of cellular automata. It's been awhile since I picked up Wolfram's "A new kind of science"

How hard would it be to create a gun that produced this new knightship and is that something the community would be interested in doing?

I could imagine it being trivially easy or mind-blowingly hard and have no intuition on what's more likely :)

Everyone would be completely floored if someone built a gun for the new knightship. It's likely to be several orders of magnitude harder to find a glider synthesis for the knightship, than it was to find the knightship itself.

To build some intuition on the difficulty, check out the list of spaceships for which a glider synthesis is known: http://conwaylife.com/wiki/Glider_synthesis#Spaceship_synthe... .

Except for the macro-spaceships (some of which are pretty trivial to construct because they're self-constructing anyway!) and the Corderships, which aren't elementary and are made out of easily constructible pieces, the biggest spaceships with known constructions are all far smaller than Sir Robin, and most of them are lower period.

Every time you add a few cells to the size of an active pattern like this, you probably double the total difficulty.

"The task of constructing such a spaceship has been likened to building a Formula-1 race car whilst it's on the track and travelling at 200mph." ( http://www.conwaylife.com/forums/viewtopic.php?f=&p=55205#p5... )

The Universal Constructor [1] running in John von Neumann's 29 state cellular automata [2] is able to construct passive configurations that aren't "powered up" with excited states in them (encoding information and synchronizing activities).

Once it's done building a machine (like a copy of itself, or anything else), it can connect its construction arm up to the "umbilical" plug of the child (like a usb port for downloading data into its storage loop), switch from "execute instructions" mode to "copy instructions" mode, and loop through its own instructions again, injecting a copy of its program into the child's storage loop, which the child can then start executing and eventually pass on to its own child.

It would be impossible to construct a "powered up" machine -- the signals would leak out into the world from the partially constructed machine and cause havoc. So you have to build a passive machine in the "powered down" state, then activate it by injecting a signal and (possibly) downloading instructions.

There are certain unconstructible "garden of eden" configurations (like a real-time crossing gate that looks and acts like an intersection with synchronized stop lights [3, p. 468, fig 3]) that are possible for God to build with a cell editor, but are impossible for a universal constructor to construct, because there is no practical way to inject and synchronize the signals into the machine after it's constructed [4].

But there are constructible "auto initializing" machines [3, p. 474, fig. 17] with one-time initialization circuits that trigger once then deactivate by firing "explosive bolts" when you power them up, bootstrapping all the internal synchronized signals necessary for the machine to operate. But of course they tend to be larger and more complicated than equivalent unconstructible machines.

[1] https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...

>As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.

[2] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton

[3] http://uncomp.uwe.ac.uk/free-books/automata2008reducedsize.p...

Buckley, William R. (2008), "Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata", in Andrew Adamatzky; Ramon Alonso-Sanz; Anna Lawniczak; Genaro Juarez Martinez; Kenichi Morita; Thomas Worsch, Proc. Automata 2008 (PDF), Luniver Press, pp. 453–503

[4] http://www.molecularassembler.com/KSRM/2.1.4.htm

>2.1.4 Limitations of von Neumann's Cellular Automaton Model

>For instance, one might wish to introduce a new primitive cell state in the system to permit signals to cross without interference. A “wire-crossing” organ can be devised using only the original von Neumann primitive cell types, but this introduces an unnecessary complexity into the machine design process since the organ contains initially active cell states whose creation involves considerable extra care to avoid the propagation of spurious signals. This extra care is especially critical because the cell system, as von Neumann originally constituted it, is highly susceptible to signal errors. (He undoubtedly intended his probabilistic machine model to mitigate this sensitivity and fragility.)

Here's another cool self replicating machine with moveable parts that uses some of the same principles:

https://www.youtube.com/watch?v=09Q5l47jTy8

Self Replication #2

>A simulation of a self replicating programmable constructor in a two dimensional discrete space supporting about two dozen different types of component part. The machine can create new parts out of nothing as it needs them. See www.srm.org.uk for more details.

https://www.youtube.com/watch?v=PBXO_6Jn1fs

Self Replication #3

>A simulation of a self-replicating programmable constructing machine in a simulation environment that supports moveable parts. The machine obtains parts from its environment and uses them to make a duplicate machine. Visit www.srm.org.uk for more information.

http://www.srm.org.uk

>Self-Replicating Machines: Will Stevens. This site is about work related to self-replicating machines that I carried out for my PhD thesis with the Department of Physics and Astronomy at the Open University in the UK between 2004 and 2009. I am interested in physically realistic simulations of self-replicating machines made from simple component parts. On this website you will find an introduction to self-replicating machines, published papers about my research, animations from simulations of self-replicating machines, simulation software that you can download, and links to other work related to self-replication.

For a wildly bold approach to robust computing, with moveable damage-resistant self-repairing parts, check out Dave Ackley's Movable Feast Machine!

http://movablefeastmachine.org/

>The Movable Feast Machine is a robust, indefinitely scalable, computing architecture.

https://news.ycombinator.com/item?id=14236898

>The video "Distributed City Generation" demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters!

https://www.youtube.com/watch?v=XkSXERxucPc

>A rough video demo of Trent R. Small's procedural city generation dynamics in the Movable Feast Machine simulator. See http://nm8.us/q for more information. Apologies for the poor audio!

https://www.youtube.com/playlist?list=PLm5k2NUmpIP-4ekppm6Jo...

>Robust-first Computing playlist. Videos introducing and exploring inherently robust computational systems.

https://www.youtube.com/playlist?list=PLm5k2NUmpIP8qwttAS5Ba...

>Movable Feast Machine v2 demos. Presentations and demos of research projects built on the MFMv2 simulator.

Von Neumann's 29 states were custom designed to make it easy to construct passive configurations, similar to the way a 3D printer builds things -- one layer at a time.

You can't do that in Conway's Life, because stable patterns in Life aren't necessarily stable when you add one cell at a time. But you can do the next best thing, which is to design circuitry that's made out of small stable "Spartan" pieces -- and then build the pieces one at a time.

Related to this, there's an equivalent for building passive structures and then activating them. In Life you can build a static "one-glider seed constellation". Hit the stable constellation with a single glider, and a few ticks later you have a working spaceship. Example:

http://www.conwaylife.com/forums/viewtopic.php?f=&p=57674#p5...

However, there's no reasonable expectation of figuring out how to build a one-glider seed for the Sir Robin knightship any time soon -- the knightship is way too fast, active, and complex. With current techniques a search for such a thing would likely take millions of years.

Given the fact that, often, in mathematics "things" are elegant, I'm rather curious why achieving a "simple" 2x1 move requires such a complex structure. Is there an explanation ?

My understanding is that up til now the existence of a pattern that moves >1 square per generation was only theoretical.

https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom...

It remains a limit. This knightship requires 6 generations to move by 2 units (1 up and 1 diagonal)

This moves 2x1 over 6 generations, which is apparently the theoretical minimum, so it does not violate game of life's c. I'm not sure why that is true however, my naive guess is that for any movement forward, some 'reset' action must be taken, so 3 cells forward, 3 reset steps. Otherwise a period 3 knightship should be possible...right?

>3 cells forward, 3 reset steps

Yes, you've got the right idea. It's actually more like "3 preperation steps, 3 steps forward"

There's a proof (http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...) that a spaceship that travels n cells vertically and m cells horizontally must take at least 2*(n+m) generations to do so.

Intuitively, I believe that you can't push out more than one adjacent "feeler" per turn, because otherwise the cells behind it would be so dense they'd kill themselves in the next round. So you simply can't get enough density to move more than one step in any given direction per two cycles.

Not a simple explanation, I don't think. The size of the smallest spaceship with a given speed and direction is an emergent consequence of iterative rules, so explaining "why" for a Life spaceship is like trying to explain the Seahorse Valley in the Mandelbrot set. In both cases, the iteration rule is simple, but the consequences are complex -- no pun intended.

Wow. I briefly played with searching for these, but was skeptical if there was such a thing. This is one of the greatest discoveries in Life ever. (Though perhaps of little "practical" importance in building other things?)

Well perhaps - like many other seemingly impractical discoveries - the methods used and invented to achieve the breakthrough will themselves find application elsewhere.

Maybe people are just too used to building with the non-oblique ships. Give Sir Robin a little time :)

It's easy to stop one of these knightships -- an eater has been built already -- and just as easy to make a knightship detector. However, a gun to make new "Sir Robin"s is not likely to appear any time soon: there are construction problems that are thousands of times easier, that are not anywhere near being solved yet.

That was much larger than I was expecting.

In B3/S23 Life, there just happened to be small c/4 diagonal, c/2 orthogonal, and c/7 orthogonal spaceships. The c/7 "loafer" ( http://conwaylife.com/wiki/Loafer ) was only found a few years ago, and was a huge surprise. Seems to be more or less the luck of the draw which velocity vectors happen to have smaller spaceships. There probably _is_ a knightship somewhat smaller than Sir Robin, but it's harder to find because it's a little wider, so it's still hiding somewhere in a much larger search space.

Fun fact: Apparently this is based on a discovery by Tom Rokicki who was also able to prove God's number to be 20 (the maximum number of moves to solve the Rubik cube).

How is a move defined? Is it rotating a single side by any amount? If I hold the central 'column' of one face and rotate both outside columns simultaneously, is that one move or two?

That example is two moves. Come on, it’s not that hard.

Well, it's two moves relative to the centre column, but it's a single move relative to each of the outside columns. I was just interested in whether the rules are 'physical' or 'theoretical'.

Certainly with a good cube you _could_ hold the outside and push to twist a center slice. From www.cube20.org -- "We consider any twist of any face to be one move (this is known as the half-turn metric.)"

Also, "New results: God's Number is 26 in the quarter turn metric!"

Please, someone, post a video or a way to turn that posted code into an animation...

There is already a wikipedia page: http://www.conwaylife.com/wiki/Knightship on Sir Robin.

If you have Javascript enabled, then there are several places that should work: the Sir Robin LifeWiki article

http://conwaylife.com/wiki/Sir_Robin

the original link (via the Show in Viewer option), or the Catagolue page

http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a3...

(click on the knightship in the upper left -- the word "Launch" should appear when you hover over the image).

They all use the same LifeViewer to do the animation, though, so you're out of luck if Javascript isn't available.

Thanx, very nice!

Perhaps a dumb question: how hard is it to do a "3D" game of life?

It's hard to answer, it depends on the person I guess... But for my point of view it's easy. You can find 3D versions online that work in the browser.

Not very; you just change the grid to a 3d space instead of 2d and change the basic algorithm a bit to count neighbours in 3d space.

Do we know whether or not there is an equivalent set of 3d rules that behave anything like 2d GoL? The same sort of algorithm (count neighbours, update state) can be applied, but it doesn't necessarily mean an extra dimension will result in similar behaviour, does it?

There are in fact various 3D rules that can be made to behave exactly like Conway's Life -- starting with some discoveries by Carter Bays involving a two-cell-thick "sandwich" of Life cells that emulated standard Conway's Life. Without the sandwich trick it can do other interesting things:

http://www.complex-systems.com/pdf/04-6-2.pdf

The two problems with 3D life have always been

1) 3D is computationally very expensive compared to 2D, so you tend to get stuck working with much smaller grids; and

2) you need a really good visualization system, otherwise interesting patterns and uninteresting patterns both look like ugly random blobs of cells and you can't tell what's going on.

That said -- not promising anything, and especially not on any definite timeline, but the next version of Golly might have a Lua-based system for experimenting with 3D CAs.

You might be interested in lattice Boltzmann methods. They solve complex equations (navier stokes for example) using similar rules like Life. They can also be coded in 3D.

Here's a 3D programmable universal constructor -- with physical kinematic block cells that can slide around, rotate, attach and detach with each other, that has to collect, sort, store and assemble the parts it needs from the environment.

http://www.srm.org.uk/papers/CBlocks3D_programmable_construc...

Here's a 3D programmable universal constructor -- with physical kinematic cell blocks that can slide around, rotate, attach and detach with each other, to build machines that can collect, sort, store and assemble the parts they need from the environment to reproduce themselves.

http://www.srm.org.uk/papers/CBlocks3D_programmable_construc...

https://www.youtube.com/watch?v=PBXO_6Jn1fs

Hey I took a video of this and put it on youtube, just so I can show my friends (who I know are too lazy to click on a link, and then click additional buttons)

Is that ok from a copyright perspective and stuff?

No one in the Game of Life community cares at all about copyright. The point of discovering patterns is to share them.

It's always nice to see how such a simple set of rules can lead to such complex items. An entire Universe that runs on these rules can probably exist.

https://www.youtube.com/watch?v=xP5-iIeKXE8

Is someone gonna make an x86 simulator on Conway's game of life?

Something like this you mean?

https://youtu.be/8unMqSp0bFY

Well, it's an RISC emulator rather than x86, but take a look at this: https://codegolf.stackexchange.com/a/142673/45727

I'd love to know more about the LifeViewer component -- it's wonderful! Is the source code available, and what is the license?

Here's what I've found so far -- it's by Chris Rowett:

http://conwaylife.com/forums/viewtopic.php?f=7&t=1026

http://lazyslug.com/lifeview/

Years ago I made a cellular automata AfterEffects plug-in that let you zoom in and pan to follow gliders around. It also had a colorization feature (since the cells were 8 bits and AfterEffects deals with RGBA) that let you sample a colormap of 256 colors from another layer along a line between two animatable points (so you could easily animate natural color gradients from images and video). You could initialize and draw into the cells by overlaying or combining channels of other layers, so you could use the full power of AE to precisely control and visualize the simulation.

It wasn't particularly "interactive" (beyond tweaking control points on the timeline then running it in AfterEffect's preview mode), but you could control all the rule parameters and animate them with the timeline, and apply any AfterEffect transformations and filters to the drawing overlay input or the colorized output.

This video shows the CA AfterEffects plugin, and also the same CA code running in a couple of live interactive editing tools (including SimCity).

https://www.youtube.com/watch?v=eCVJ08gK2o8

I've rewritten the CA code in JavaScript, but the current user interface is arcane, and I would like to rewrite it in TypeScript as a module that can plug into some nice interactive playing and editing tool like LifeView.

http://donhopkins.com/home/CAM6

https://github.com/SimHacker/CAM6

It's really hard to make one user interface or visualization that works well for all rules. A cellular automata viewing and editing tool that supports different rules needs to be deeply customizable.

It turns out that each CA rule needs its own specialized user interface with rule-specific drawing tools, effects, controls and presets for visualizing, playing, painting, explaining, etc.

I wonder if anybody working on a free successor to AfterEffects that runs in a web browser?

LifeViewer has evolved in a somewhat different direction from the original LifeView, and is still a work in progress -- Chris has been contributing a lot of useful LifeViewer functionality to http://golly.sf.net , and vice versa.

LifeViewer is currently used primarily on the conwaylife forums and the LifeWiki, but it's easy to borrow it to embed in independent Web pages.

The source code is not currently available -- see http://www.conwaylife.com/forums/viewtopic.php?f=&p=35511#p3... . That's also probably the best place to ask any further questions about LifeViewer -- I'm just a beta tester.

Thank you for that!

LifeViewer and Golly have a lot of great ideas in them, and a huge library of rules, patterns, and configurations. I'd love to have access to the source code for LifeViewer, so I can integrate my own cellular automata rules, editing tools and visualizations with it.

Here's a great video of Will Wright and Brian Eno discussing generative systems and demonstrating cellular automata with Mirek's Cellebration to Brian Eno's generative music, at a talk at the Long Now Foundation,:

https://www.youtube.com/watch?v=UqzVSvqXJYg

https://en.wikipedia.org/wiki/Mirek%27s_Cellebration

Does the starting point have to be Javascript?

If so, a good bet might be this HashLife Javascript implementation:

https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873

If not, well, Golly is open-source, cross-platform, supports custom rules via rule tables, and would welcome contributions to its editing-tool department:

http://sf.net/projects/golly

There's even a lifeviewer.lua in the Scripts/Lua folder that duplicates some of LifeViewer's functionality, and is also obviously open source, though it's definitely also a work in progress.

Reply on news.ycombinator.com