31 ms·

Elementary Knightship found in Conway's Game of Life

733 points by vanderZwan 9y ago

deleted 9y ago
[deleted]
nneonneo 9y 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 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 9y 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.
  - OscarCunningham 9y 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 9y ago
    Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.
  - sevensor 9y 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.
    - awwaiid 9y ago
      A combination could be interesting - SAT to smooth the space for a GA search.
      - sevensor 9y ago
        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.
- paulgb 9y 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.
  - OscarCunningham 9y 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).
    - deleted 9y ago
      [deleted]
  - panic 9y ago
    The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master https://gitlab.com/apgoucher/metasat/tree/master
  - nneonneo 9y ago
    The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py 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.
    - ChickeNES 9y ago
      >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?
- jMyles 9y 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 9y 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 http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.
  - deleted 9y ago
    [deleted]
  - Someone 9y 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 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 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.
    - 9y ago
- big_al337 9y 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 http://www.conwaylife.com/wiki/Knightship I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h
  - nneonneo 9y 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-speed-in-conways-game-of-life/ 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.
    - LoSboccacc 9y ago
      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&step=512 https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...
    - vanderZwan 9y ago
      > 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
  - 9y ago
foota 9y ago
That was much larger than I was expecting.
- dvgrn 9y 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 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 9y ago
Here it is for anyone interested (click the image) http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a38bac2qq73uszyjo4w8y0e4mo0vu0o606s6444u08clav0h03g440qq1333333x11zy9ecec2ik032i210sw3f0hy011w70401011033547442zy0emj896he1e1kif6q2gc50ew9qb30dzgo403gg066m32w11z34407q441n6zy311/b3s23 http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a3...
- CGamesPlay 9y ago
  Click the text "Show In Viewer" above to code snippet in the OP to watch it working.
  - coryfklein 9y 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 http://conwaylife.com/wiki/282P6H2V1
    - CGamesPlay 9y ago
      Perhaps you have JS disabled? It opens an interactive widget.
  - ColinDabritz 9y 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 9y ago
  And to play around with: https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873 https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873
gort 9y 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?)
- samfriedman 9y ago
  Well perhaps - like many other seemingly impractical discoveries - the methods used and invented to achieve the breakthrough will themselves find application elsewhere.
- nneonneo 9y ago
  Maybe people are just too used to building with the non-oblique ships. Give Sir Robin a little time :)
  - dvgrn 9y 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.
vanderZwan 9y 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 http://conwaylife.com/wiki/282P6H2V1
- SeanLuke 9y ago
  What does "elementary" mean in this context?
  - vanderZwan 9y 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 http://conwaylife.com/wiki/Knightship [1] http://conwaylife.com/wiki/Waterbear http://conwaylife.com/wiki/Waterbear [2] https://www.youtube.com/watch?v=on3ZLLKQp-4 https://www.youtube.com/watch?v=on3ZLLKQp-4
    - bringtheaction 9y ago
      That waterbear looks very complex. How did they ever manage to find it?
      - vanderZwan 9y ago
        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.
      - Maybestring 9y ago
        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.
YeGoblynQueenne 9y 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?
- ultimoo 9y 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 https://imgur.com/a/yNF5a
- stuntkite 9y 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 http://www.conwaylife.com/wiki/Knightship
  - pasabagi 9y 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.
carlob 9y 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 http://www.conwaylife.com/wiki/Knightship
lamarpye 9y ago
Don't take this the wrong way, but is there any point to this? Or is it mindless masturbation like SETI?
thearn4 9y 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 9y 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 9y ago
  The names they give these things are so cool. Frothing spaceship, oblique glider waterbear, 10hd demonoid, weekender, loafer.
- DonHopkins 9y 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 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 9y 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 9y 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_automaton) https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom...
  - function_seven 9y ago
    It remains a limit. This knightship requires 6 generations to move by 2 units (1 up and 1 diagonal)
  - vokep 9y 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?
    - OscarCunningham 9y ago
      >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-life-like-cellular-automata/ 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.
    - FeepingCreature 9y ago
      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.
pkrumins 9y 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 9y 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 9y ago
    Many gliders move at the theoretical maximum rate on the Life board, so it won’t be possible to catch them.
    - darkmighty 9y ago
      I believe c/4 is indeed the fastest possible diagonal speed for a spaceship, does anyone know if a proof exists?
      - dvgrn 9y ago
        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.
      - OscarCunningham 9y ago
        This blog post has a explanation of the proof. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/ http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...
RustGirl 9y 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 9y ago
  https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
jonshariat 9y 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 9y 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 9y 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.
- tchaffee 9y 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.
  - ouid 9y ago
    Quantifying the complexity of the GoL ruleset is slightly more complicated than enumerating the rules, I would imagine.
    - 9y ago
everyone 9y 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?
- OscarCunningham 9y ago
  No one in the Game of Life community cares at all about copyright. The point of discovering patterns is to share them.
zeptomu 9y 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).
- oneeyedpigeon 9y 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?
  - taylorexpander 9y ago
    That example is two moves. Come on, it’s not that hard.
    - oneeyedpigeon 9y ago
      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'.
      - dvgrn 9y ago
        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!"
creatonez 9y ago
Is someone gonna make an x86 simulator on Conway's game of life?
- sclangdon 9y ago
  Something like this you mean? https://youtu.be/8unMqSp0bFY https://youtu.be/8unMqSp0bFY
- skykooler 9y ago
  Well, it's an RISC emulator rather than x86, but take a look at this: https://codegolf.stackexchange.com/a/142673/45727 https://codegolf.stackexchange.com/a/142673/45727
dluan 9y ago
Perhaps a dumb question: how hard is it to do a "3D" game of life?
- SaturateDK 9y 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_ 9y 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.
  - oneeyedpigeon 9y 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?
    - dvgrn 9y ago
      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 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.
- taylorexpander 9y ago
ardillaroja 9y 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 :)
- dvgrn 9y 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_syntheses 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#p55205 http://www.conwaylife.com/forums/viewtopic.php?f=&p=55205#p5... )
  - DonHopkins 9y 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_constructor 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 https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton [3] http://uncomp.uwe.ac.uk/free-books/automata2008reducedsize.pdf 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 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.)
teekert 9y 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 http://www.conwaylife.com/wiki/Knightship on Sir Robin.
- dvgrn 9y 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 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_yyocxukcy6gocs20h0a38bac2qq73uszyjo4w8y0e4mo0vu0o606s6444u08clav0h03g440qq1333333x11zy9ecec2ik032i210sw3f0hy011w70401011033547442zy0emj896he1e1kif6q2gc50ew9qb30dzgo403gg066m32w11z34407q441n6zy311/b3s23 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.
  - teekert 9y ago
    Thanx, very nice!
DonHopkins 9y 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://conwaylife.com/forums/viewtopic.php?f=7&t=1026 http://lazyslug.com/lifeview/ 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 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 http://donhopkins.com/home/CAM6 https://github.com/SimHacker/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?
- dvgrn 9y 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 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#p35511 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.

733 points by vanderZwan 9y ago

deleted 9y ago

[deleted]

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 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 9y 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.
- OscarCunningham 9y 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 9y ago
  Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.
- sevensor 9y 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.
  - awwaiid 9y ago
    A combination could be interesting - SAT to smooth the space for a GA search.
    - sevensor 9y ago
      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.
paulgb 9y 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.
- OscarCunningham 9y 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).
  - deleted 9y ago
    [deleted]
- panic 9y ago
  The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master https://gitlab.com/apgoucher/metasat/tree/master
- nneonneo 9y ago
  The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py 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.
  - ChickeNES 9y ago
    >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?
jMyles 9y 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 9y 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 http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.
- deleted 9y ago
  [deleted]
- Someone 9y 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 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 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.
  - 9y ago
big_al337 9y 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 http://www.conwaylife.com/wiki/Knightship I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h
- nneonneo 9y 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-speed-in-conways-game-of-life/ 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.
  - LoSboccacc 9y ago
    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&step=512 https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...
  - vanderZwan 9y ago
    > 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
- 9y ago

foota 9y ago

That was much larger than I was expecting.

dvgrn 9y 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 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 9y ago

Here it is for anyone interested (click the image) http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a38bac2qq73uszyjo4w8y0e4mo0vu0o606s6444u08clav0h03g440qq1333333x11zy9ecec2ik032i210sw3f0hy011w70401011033547442zy0emj896he1e1kif6q2gc50ew9qb30dzgo403gg066m32w11z34407q441n6zy311/b3s23 http://catagolue.appspot.com/object/xq6_yyocxukcy6gocs20h0a3...

CGamesPlay 9y ago
Click the text "Show In Viewer" above to code snippet in the OP to watch it working.
- coryfklein 9y 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 http://conwaylife.com/wiki/282P6H2V1
  - CGamesPlay 9y ago
    Perhaps you have JS disabled? It opens an interactive widget.
- ColinDabritz 9y 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 9y ago
And to play around with: https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873 https://copy.sh/life/?gist=31aa52b9430970a28e4c199444e5a873

gort 9y 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?)

samfriedman 9y ago
Well perhaps - like many other seemingly impractical discoveries - the methods used and invented to achieve the breakthrough will themselves find application elsewhere.
nneonneo 9y ago
Maybe people are just too used to building with the non-oblique ships. Give Sir Robin a little time :)
- dvgrn 9y 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.

vanderZwan 9y 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 http://conwaylife.com/wiki/282P6H2V1

SeanLuke 9y ago
What does "elementary" mean in this context?
- vanderZwan 9y 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 http://conwaylife.com/wiki/Knightship [1] http://conwaylife.com/wiki/Waterbear http://conwaylife.com/wiki/Waterbear [2] https://www.youtube.com/watch?v=on3ZLLKQp-4 https://www.youtube.com/watch?v=on3ZLLKQp-4
  - bringtheaction 9y ago
    That waterbear looks very complex. How did they ever manage to find it?
    - vanderZwan 9y ago
      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.
    - Maybestring 9y ago
      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.

YeGoblynQueenne 9y 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?

ultimoo 9y 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 https://imgur.com/a/yNF5a
stuntkite 9y 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 http://www.conwaylife.com/wiki/Knightship
- pasabagi 9y 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.

carlob 9y 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 http://www.conwaylife.com/wiki/Knightship

lamarpye 9y ago

Don't take this the wrong way, but is there any point to this? Or is it mindless masturbation like SETI?

thearn4 9y 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 9y 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 9y ago
The names they give these things are so cool. Frothing spaceship, oblique glider waterbear, 10hd demonoid, weekender, loafer.
DonHopkins 9y 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 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 9y 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 9y 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_automaton) https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom...
- function_seven 9y ago
  It remains a limit. This knightship requires 6 generations to move by 2 units (1 up and 1 diagonal)
- vokep 9y 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?
  - OscarCunningham 9y ago
    >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-life-like-cellular-automata/ 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.
  - FeepingCreature 9y ago
    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.

pkrumins 9y 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 9y 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 9y ago
  Many gliders move at the theoretical maximum rate on the Life board, so it won’t be possible to catch them.
  - darkmighty 9y ago
    I believe c/4 is indeed the fastest possible diagonal speed for a spaceship, does anyone know if a proof exists?
    - dvgrn 9y ago
      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.
    - OscarCunningham 9y ago
      This blog post has a explanation of the proof. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/ http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...

RustGirl 9y 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 9y ago
https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8

jonshariat 9y 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 9y 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 9y 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.
tchaffee 9y 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.
- ouid 9y ago
  Quantifying the complexity of the GoL ruleset is slightly more complicated than enumerating the rules, I would imagine.
  - 9y ago

everyone 9y 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?

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

zeptomu 9y 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).

oneeyedpigeon 9y 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?
- taylorexpander 9y ago
  That example is two moves. Come on, it’s not that hard.
  - oneeyedpigeon 9y ago
    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'.
    - dvgrn 9y ago
      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!"

creatonez 9y ago

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

sclangdon 9y ago
Something like this you mean? https://youtu.be/8unMqSp0bFY https://youtu.be/8unMqSp0bFY
skykooler 9y ago
Well, it's an RISC emulator rather than x86, but take a look at this: https://codegolf.stackexchange.com/a/142673/45727 https://codegolf.stackexchange.com/a/142673/45727

dluan 9y ago

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

SaturateDK 9y 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_ 9y 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.
- oneeyedpigeon 9y 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?
  - dvgrn 9y ago
    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 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.
taylorexpander 9y ago

ardillaroja 9y 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 :)

dvgrn 9y 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_syntheses 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#p55205 http://www.conwaylife.com/forums/viewtopic.php?f=&p=55205#p5... )
- DonHopkins 9y 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_constructor 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 https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton [3] http://uncomp.uwe.ac.uk/free-books/automata2008reducedsize.pdf 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 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.)

teekert 9y 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 http://www.conwaylife.com/wiki/Knightship on Sir Robin.

dvgrn 9y 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 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_yyocxukcy6gocs20h0a38bac2qq73uszyjo4w8y0e4mo0vu0o606s6444u08clav0h03g440qq1333333x11zy9ecec2ik032i210sw3f0hy011w70401011033547442zy0emj896he1e1kif6q2gc50ew9qb30dzgo403gg066m32w11z34407q441n6zy311/b3s23 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.
- teekert 9y ago
  Thanx, very nice!

DonHopkins 9y 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://conwaylife.com/forums/viewtopic.php?f=7&t=1026 http://lazyslug.com/lifeview/ 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 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 http://donhopkins.com/home/CAM6 https://github.com/SimHacker/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?

dvgrn 9y 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 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#p35511 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.