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.
> 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).
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.
This idea comes up a little bit differently in Max Tegmark's book "Our Mathematical Universe" which I liked 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
Edit: Not the same page, but you can find an animation of it here: http://conwaylife.com/wiki/282P6H2V1
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!
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...
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.
It won't help you understand the mathematics of the game, but it might help you appreciate the beauty.
Small (as of now) summary on the Life wiki:
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 .
So my best guess is: a mixture of mathematics, brute force searching, and lots of passionate on-line discussion with fellow nerds.
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.
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.
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
I still don't get it, but at least I got visuals now :)
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. I still feel like my questions stand and could be elaborated on.
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.
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.
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 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.
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.
if (someveryhardproblem()) infiniteloop();
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.
I could imagine it being trivially easy or mind-blowingly hard and have no intuition on what's more likely :)
To build some intuition on the difficulty, check out the list of spaceships for which a glider synthesis is known:
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... )
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 .
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.
>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.
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
>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.)
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.
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.
>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!
>The Movable Feast Machine is a robust, indefinitely scalable, computing architecture.
>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!
>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!
>Robust-first Computing playlist. Videos introducing and exploring inherently robust computational systems.
>Movable Feast Machine v2 demos. Presentations and demos of research projects built on the MFMv2 simulator.
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:
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.
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.
Also, "New results: God's Number is 26 in the quarter turn metric!"
There is already a wikipedia page: http://www.conwaylife.com/wiki/Knightship on Sir Robin.
the original link (via the Show in Viewer option), or the Catagolue page
(click on the knightship in the upper left -- the word "Launch" should appear when you hover over the image).
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.
Is that ok from a copyright perspective and stuff?
Here's what I've found so far -- it's by Chris Rowett:
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).
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 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.
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,:
If not, well, Golly is open-source, cross-platform, supports custom rules via rule tables, and would welcome contributions to its editing-tool department:
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.