Be fruitful and iterate.

January 20, 2009 12:41 AM

Researchers discover gigantic "Caterpillar" spaceship that travels at (17/45)c.Just another exciting development in the Game of Life (previously).
posted by fatllama (51 comments total)

Jesus, that thing is huge! Awesome.
posted by equalpants at 1:02 AM on January 20

I think this might be supercool, but I wish there was a little glossary action for the uninitiated.
posted by stavrosthewonderchicken at 1:14 AM on January 20

Well, the wikipedia article is good. Thought about including it just for good measure.
posted by fatllama at 1:16 AM on January 20

For a moment I thought this was an actual spaceship which went at 17/45 the speed of light. This is still cool, though. The Game of Life is mesmerizing.
posted by Sticherbeast at 1:30 AM on January 20

Needs more Gayoneh.
posted by Rhaomi at 1:40 AM on January 20

That is pretty cool.
posted by delmoi at 1:56 AM on January 20

Has anyone messed around with 3-d games of life?
posted by delmoi at 1:59 AM on January 20

Apparently spaceships moving along any rational slope are known to exist, but only orthogonal and 45° ships have been constructed explicitly.
posted by metaplectic at 2:16 AM on January 20

All hail cellular automata!

The thing with Conway... he spent way too many hours trying to figure out rules that didn't peter out quickly. When he found a small set of rules that worked he shouted "Life!!" - but of course these rules have nothing to do with Life (in some biological sense). And the word "Game" is a complete misnomer. Conway loved playing games; he spent way too many hours studying what we now call combinatorial game theory. And he helped stick "Game" to "Life".

Conway is a great man, no doubt about it, but he did not invent life.
posted by twoleftfeet at 2:26 AM on January 20 [1 favorite has favorites]

I just favorited every comment that was adjacent to 0 favorites, and then unfavorited every comment that had a favorited neighbor.

This spaceship is awesome.
posted by dirty lies at 2:55 AM on January 20 [38 favorites has favorites]

In an alternate reality, the dude who wrote that article discovered faster-than-light travel and ushered in an era of space exploration and prosperity. In our reality, he made some cool cellular automata. Sucks to be us.
posted by jamstigator at 3:18 AM on January 20 [1 favorite has favorites]

So what makes this pattern so interesting? The light weight spaceship is faster at c/2 — the maximum possible spaceship speed. Does the 17/45 rate have some special properties? Or is this pattern only notable for its size?
posted by ryanrs at 3:30 AM on January 20

That thing is a beast. Running it in Golly on a 2.5Ghz Macbook Pro and I'm getting about 0.5 fps. Ouch.
posted by schwa at 3:44 AM on January 20

Caterpillar's sole mission is to destroy Stephen Wolfram's next pet project. A bumper sticker on its rear end says "We Brake For Nobody."
posted by XMLicious at 5:05 AM on January 20 [7 favorites has favorites]

but of course these rules have nothing to do with Life (in some biological sense).

Not really true. Conway's Life is a great metaphor for thinking about how emergence and complexity arise from simple rules. Arch-naturalist philosopher Daniel Dennett uses it as a centerpiece for his book Freedom Evolves.
posted by norabarnacl3 at 5:30 AM on January 20 [1 favorite has favorites]

When it runs, does a sound that could be classified as "Magma Displacement" come out of the speakers?
posted by ArgentCorvid at 5:36 AM on January 20 [2 favorites has favorites]

It seems like cheating nowadays, where you can try every possibility grid and see which patterns are interesting, and you are only limited by the processor power. Didn't they used to do this with graph paper and spare time on mainframes?
posted by smackfu at 5:36 AM on January 20

I have to second the sentiment that, what, exactly, is the point of this thing? I mean, as far as I can tell, they tried to create a really big pattern... and succeeded? Is it just the size of it? Because if that's it, then goddamn is it impressive. No argument.

Also, the lexicon.
posted by cthuljew at 5:49 AM on January 20

I have to second the sentiment that, what, exactly, is the point of this thing? I mean, as far as I can tell, they tried to create a really big pattern... and succeeded? Is it just the size of it?

No, it's the fact that it moves steadily in one direction in the grid and retains a basically coherent shape, rather than dissolving into other patterns like most bunches of Life cells do.
posted by letourneau at 6:08 AM on January 20

Ok all confusing lingo, weird charts, and scientific stuff aside from what I get all this is, is a computer program of a really really really long, coherent shape that could be designed into a really fast spaceship. Or am I missing something here?
posted by Mastercheddaar at 6:22 AM on January 20

Hah, I love this description of an "R-Pentomino"

A 5-cell methuselah which runs 1103 steps before settling down into 6 gliders, 8 blocks, 4 blinkers, 4 beehives, 1 boat, 1 ship, and 1 loaf. This is by far the most active polyomino with less than six cells; all the others stabilize in at most 10 generations.

--

It seems like cheating nowadays, where you can try every possibility grid and see which patterns are interesting, and you are only limited by the processor power.

Read up on Complexity Classes. Computers can't do everything you think they can. If you had a processor capable of calculating 10 billion steps per second (10¹⁰), and you wanted to track the evolution of something for 100 steps on a 100x100 grid, you would need (2¹⁰⁰⁰*100)/10¹⁰ =~ 10²⁹³ seconds to test all of them. That's equal to 10²⁸⁵ years.

What these people are doing is taking known 'parts' and using computers to build specific designs. Writing software to do that takes a lot of work.
posted by delmoi at 6:35 AM on January 20 [3 favorites has favorites]

As an athlete I can trade in 4 life tiles to get the yellow salary card.
posted by Smedleyman at 6:39 AM on January 20

Ok all confusing lingo, weird charts, and scientific stuff aside from what I get all this is, is a computer program of a really really really long, coherent shape that could be designed into a really fast spaceship. Or am I missing something here?

No it's just a game. You know how people who play chess sometimes set up "chess problems"? where the board has a specific setup? Imagine if 1) There were rules in chess that let you add a new piece to the board in certain circumstances and that 2) people had discovered chess problems that worked in a cycle or worked in a cycle and moved down the board.

The rules in this game are way, way simpler then chess, but that's a good way to imagine it. here are the rules:

<sub>1. Any live cell with fewer than two live neighbours dies, as if by needs caused by underpopulation.

2. Any live cell with more than three live neighbours dies, as if by overcrowding.

3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.

4. Any tile with exactly three live neighbours cells will be populated with a living cell.</sub>

So, based on those rules, you get all kinds of crazy patterns. This was really popular back in the 70s or whatever when computers were really slow.
posted by delmoi at 6:42 AM on January 20

Computers can't do everything you think they can.

Well, they can do it, just not very fast. Especially since I think the exponent should be 10000 (100x100) so it's even slower than you said.
posted by smackfu at 7:04 AM on January 20

Cool thank for explaining it to me. And this caterpillar shape is a random occurrence from their rules of the game right?
posted by Mastercheddaar at 7:24 AM on January 20

Holy goddam, that's great. See also.
posted by cortex at 7:50 AM on January 20

And this caterpillar shape is a random occurrence from their rules of the game right?

I think it's more like this: this caterpillar shape has a structure such that repeated applications of the rules of the game make it "move" at high speeds across the graph paper while retaining its basic structure. So it's a very large, highly-stable structure within the context of the game.

Can anyone who actually knows what they're talking about confirm my understanding?
posted by saulgoodman at 7:54 AM on January 20

Well, the caterpillar shape isn't a random occurance—the sucker was engineered, and it's a lovely, impressive piece of workmanship. But that you could build one is a happy accident of emergent behavior from Conway's incredibly simple ruleset, so in that sense, yes, it's crazy wonderful randomness that it can exist and work.
posted by cortex at 7:55 AM on January 20

cortex: cool, that's what i was trying to get at.
posted by saulgoodman at 7:58 AM on January 20

All I want is a website that can show me the lifecycles of the cellular automata catepillar, not just describe the lifecycles of it's components in words.
posted by garlic at 8:25 AM on January 20

Cortex, I can't think of any real-life examples that truly follow the four rules of Life. How would this actually exist?
posted by Citizen Premier at 9:27 AM on January 20

All I want is a website that can show me the lifecycles of the cellular automata catepillar....
posted by fatllama at 9:32 AM on January 20

Conway wasn't trying to create a model of the universe; the ship would never "actually" exist, because life doesn't obey Conway's rules.

The brilliant thing about his invention is that despite being so stunningly simple, it does produce very complicated behavior in a system. Don't look at Life as an explanation of any real systems but as an analogue to the emergent capacity of simple systems. Cellular automata as a strange, symbolic cousin to real systems, etc.

I feel like I've said this in every CA thread I've seen, but Wolfram's book is full of interesting explorations of these analogues if you can read around the wide-eyed OMG THIS IS EVERYTHING rhetoric that crops up throughout.
posted by cortex at 10:10 AM on January 20 [1 favorite has favorites]

Oh, for the days when Martin Gardner still wrote Mathematical Recreations for SciAm....
posted by JHarris at 10:25 AM on January 20

Oh, for the days when Martin Gardner still wrote Mathematical Recreations for SciAm....

Man, those were the days to be a preadolescent puzzle nerd!
posted by jonp72 at 10:51 AM on January 20 [3 favorites has favorites]

Where does the scale come from? How does "moving so many cells in each iteration" translate to (17 / 45)*c?
posted by grobstein at 10:57 AM on January 20

. . . I'm missing something, aren't I?
posted by grobstein at 10:58 AM on January 20

c is a unit of distance: one cell. c/2 is moving at an average speed of one cell every two ticks, c/4 is one every four, etc. 17c/45 thus means it takes the machine an average of 45 ticks to travel 17 cells.
posted by cortex at 11:01 AM on January 20

Ha, ok, that helps a ton. For some reason I assumed we were talking about the speed of light! =P Didn't help that it's called a "spaceship." Ahem. Okay. Off I go now.
posted by grobstein at 11:05 AM on January 20

A really cool thing about Game of Life is that one can take an intelligent kid who has never written a line of code and teach them enough that by the end of the afternoon they have built a small version in almost any language. They will spend hours playing with it, and most will understand what computers are all about. Some will even start asking really good questions about order, chaos, emergence, and life.

First time I did it, it was in Quick Basic, with O and X representing live and dead cells on a 5 by 5 grid. Last time I did it it was with Flash and some nice graphics. Now that I see cortex's link, I have a project from when i get the brain augmentation microchips: Write a version of Game of Life in Game of Life.
posted by dirty lies at 11:11 AM on January 20 [3 favorites has favorites]

The reason they use "c" is that c, the sped of light, is the maximal speed any change can propagate in our universe (unless you're a wingnut). The maximum speed any change can propagate in the Game of Life is one cell per cycle.

You can even create elaborate "agar" systems consisting of regular patterns and screw them up with just one tiny cell turned on; the resultant chaos will spread no faster than than one cell per cycle.

This brings you to spaceships, which travel at various speeds like c/2, and gliders (which go diagonally and flip-flop about), which travel at c/4.

The more you implement the Game of Life, the more programming you learn. I've seen some fantastically complex implementations of it, made fast by sophisticated algorithms, and you can just learn tons by proceeding through the natural development of the software.
posted by adipocere at 11:23 AM on January 20 [2 favorites has favorites]

Well, they can do it, just not very fast. Especially since I think the exponent should be 10000 (100x100) so it's even slower than you said.

So could "they" who "used to do this with graph paper and spare time on mainframes", in fact it would only put a small dent in that exponent.

Your right it should be 2^10,000 not 2^1,000. Which means you need to multiply the final result by 1024, so 10²⁸⁸ rather then 10²⁸⁵ (I think)
posted by delmoi at 11:47 AM on January 20

2^10,000 * 100 / 10¹⁰ ≈ 2 * 10³⁰⁰²
posted by ryanrs at 12:49 PM on January 20

dirty lies: Hey, now that's an idea. I'm trying to teach a bright nephew how to program (since our local educational system is ill-equipped for such things), Life would be an excellent thing to set him to work on once he's learned enough Python.
posted by JHarris at 5:08 PM on January 20

From the same guy's page, Lightspeed signals in Life is some deeply hot shit.
posted by cortex at 5:35 PM on January 20

See also.

I love that image. I don't really understand it very well, but something about that particular arrangement of cells does it for me. I chalked it up to odd coincidence that I put a sector from it on the cover of the MeFiSwap mix I made last night and then saw this post here today, but you mentioning that TM specifically is creepy.
posted by carsonb at 5:49 PM on January 20

Having grown up on "Mathematical Recreations" in SciAm, I was disappointed when I finally got my first Mac and discovered that it didn't come with any implementation of "Life"... I had naively thought that this was what personal computers were invented to do.
posted by AsYouKnow Bob at 7:06 PM on January 20

Great holy crap, adipocere. My head just exploded with the... Wow. The speed of light is the framerate of reality. It all makes sense now.

The sarcasm light, btw, is off.
posted by Mister Moofoo at 7:41 PM on January 20

dirty lies: check out Golly. One of the example programs is a Turing Machine life pattern, and the program it's running is a (visual) game of life.
posted by ntk at 12:11 AM on January 21

ntk, my mind is blown.
posted by dirty lies at 4:27 PM on January 21

Life is NP-complete.

Or is it?
posted by twoleftfeet at 1:17 AM on January 22