Elementary Knightship found in Conway's Game of Life

http://www.conwaylife.com/forums/viewtopic.php?t=3303

by vanderZwan • 8 years ago

733 143 8 years ago

conwaylife.com

vanderZwan5• 8 years ago

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

SeanLuke• 8 years ago

What does "elementary" mean in this context?

tantalor• 8 years ago

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

http://conwaylife.com/wiki/Elementary

vanderZwan5• 8 years ago

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

ouid2• 8 years ago

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

YeGoblynQueenne2• 8 years ago

  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?

noxToken• 8 years ago

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

PhasmaFelis• 8 years ago

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

YeGoblynQueenne2• 8 years ago

Cheers.

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

carlob2• 8 years ago

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

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

ultimoo• 8 years ago

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

stuntkite2• 8 years ago

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

pasabagi2• 8 years ago

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.

carlob2• 8 years ago

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

nneonneo6• 8 years ago

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.

0xdeadbeefbabe• 8 years ago

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.

OscarCunningham6• 8 years ago

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.

teraflop• 8 years ago

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

sevensor2• 8 years ago

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.

paulgb• 8 years ago

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.

OscarCunningham6• 8 years ago

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

panic• 8 years ago

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

nneonneo6• 8 years ago

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.

jMyles• 8 years ago

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?

dazmax• 8 years ago

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.

Someone2• 8 years ago

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

gonehome• 8 years ago

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.

westoncb2• 8 years ago

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/

invisibowl2• 8 years ago

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.

Parcissons• 8 years ago

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.

big_al337• 8 years ago

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

nneonneo6• 8 years ago

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.

CydeWeys• 8 years ago

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.

foota• 8 years ago

That was much larger than I was expecting.

dvgrn16• 8 years ago

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.

mikkom• 8 years ago

Here it is for anyone interested (click the image)

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

CGamesPlay2• 8 years ago

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

coryfklein• 8 years ago

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

ColinDabritz• 8 years ago

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.

3648• 8 years ago

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

gort• 8 years ago

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

samfriedman2• 8 years ago

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

nneonneo6• 8 years ago

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

dvgrn16• 8 years ago

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.

thearn4• 8 years ago

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"

ChuckMcM• 8 years ago

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.

twfarland• 8 years ago

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

DonHopkins8• 8 years ago

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

wiz21c• 8 years ago

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 ?

charonn0• 8 years ago

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

function_seven• 8 years ago

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

vokep• 8 years ago

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?

dvgrn16• 8 years ago

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.

pkrumins• 8 years ago

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.

tupshin• 8 years ago

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.

iainmerrick• 8 years ago

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

mankyd• 8 years ago

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

westoncb2• 8 years ago

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.

darkmighty3• 8 years ago

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

falcor843• 8 years ago

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.

PeterisP3• 8 years ago

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.

nneonneo6• 8 years ago

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.

falcor843• 8 years ago

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.

jopsen• 8 years ago

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.

PeterisP3• 8 years ago

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.

RustGirl• 8 years ago

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.

dnautics• 8 years ago

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

jonshariat• 8 years ago

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!

jedberg• 8 years ago

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

olympus• 8 years ago

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.

tchaffee3• 8 years ago

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.

ouid2• 8 years ago

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

DonHopkins8• 8 years ago

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

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

everyone• 8 years ago

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?

OscarCunningham6• 8 years ago

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

zeptomu• 8 years ago

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

oneeyedpigeon4• 8 years ago

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?

taylorexpander2• 8 years ago

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

creatonez• 8 years ago

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

sclangdon• 8 years ago

Something like this you mean?

https://youtu.be/8unMqSp0bFY

skykooler• 8 years ago

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

dluan• 8 years ago

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

SaturateDK• 8 years ago

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.

Cthulhu_• 8 years ago

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.

oneeyedpigeon4• 8 years ago

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?

taylorexpander2• 8 years ago

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.

DonHopkins8• 8 years ago

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

DonHopkins8• 8 years ago

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

ardillaroja• 8 years ago

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

dvgrn16• 8 years ago

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

DonHopkins8• 8 years ago

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

teekert2• 8 years ago

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.

dvgrn16• 8 years ago

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.

teekert2• 8 years ago

Thanx, very nice!

DonHopkins8• 8 years ago

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?

dvgrn16• 8 years ago

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.

DonHopkins8• 8 years ago

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

Elementary Knightship found in Conway's Game of Life

Related Stories