The game of life emulated in the game of life

http://www.jwz.org/blog/2012/05/turtles-all-the-way-down-or-gliders-or-glider-turtles/

by koide • 14 years ago

300 79 14 years ago

http://golly.sourceforge.net/

huskyr• 14 years ago

The presence or absence of the eater indicates whether the cell should be on in the next meta-generation. The state of the eater is read by the collision of two antiparallel LWSSes, which radiates two antiparallel gliders (not unlike an electron-positron reaction in a PET scanner). These gliders then collide into beehives, which are restored by a passing LWSS in Brice's elegant honeybit reaction.

Reading Game of Life descriptions feels like reading papers about quantum physics :)

azmenthe2• 14 years ago

I was thinking this too. Who spends this many hours with cellular automata to not only classify structures but engineer with them... Is it Mathematicians ? Why ?

prawks• 14 years ago

Put plainly by Wikipedia[1]:

Life provides an example of emergence and self-organization. It is interesting for computer scientists, physicists, biologists, biochemists, economists, mathematicians, philosophers, generative scientists and others to observe the way that complex patterns can emerge from the implementation of very simple rules. The game can also serve as a didactic analogy, used to convey the somewhat counter-intuitive notion that "design" and "organization" can spontaneously emerge in the absence of a designer. For example, philosopher and cognitive scientist Daniel Dennett has used the analogue of Conway's Life "universe" extensively to illustrate the possible evolution of complex philosophical constructs, such as consciousness and free will, from the relatively simple set of deterministic physical laws governing our own universe.

If you go deep enough, it really is a fascinating thing. Even more-so given the extreme simplicity of its rules.

[1] http://en.wikipedia.org/wiki/Conways_Game_of_Life#Origins

sp332• 14 years ago

The most common patterns all have names, just because it's so much easier to talk about a "loaf" than "you know, the sort of triangular one with the corners missing". This page shows the relative frequency of a kind of pattern called "still lifes" http://www.conwaylife.com/wiki/List_of_common_still_lifes but most of the pages linked from there are auto-generated stubs. http://www.conwaylife.com/wiki/Loaf

Edit: You're right, people put a lot of time into discovering and engineering things in Life. But it's an odd mix of cleverness and brute-forcing. http://www.conwaylife.com/wiki/Glider_synthesis

Isamu• 14 years ago

I for one. I'm a software engineer, and I'm driven by curiosity. In the 90's I was privileged to belong to a private mailing list that included the likes of John Conway and Bill Gosper and we shared our discoveries in Life and a few other CA. I shared with them my CA discovery that John named "HighLife" and we had some fun with the simple replicator that it supports. Good times.

[edit] Someone put a nice animation of the replicator here: http://en.wikipedia.org/wiki/HighLife

maushu• 14 years ago

Reading Game of Life descriptions feels like reading papers about quantum physics :)

Which creates some disturbing ideas about our reality.

stevenrace• 14 years ago

Perhaps 'intriguing' is the better term.

I'd implore everyone to spend a few rainy weekends trudging through Mandelbrot's 'The Fractal Geometry of Nature'[1] and Wolfram's 'A New Kind of Science'[2]. Both are rather terse, but I found both added a whole new depth of analogy in the way I see the Universe(s).

It's easy to be dismissive of Stephen Wolfram for his general asshat'ery and Benoit isn't around to champion his notions in the broader sense. But if we are to take reductivism to it's extreme, it's worth exploring emergent patterns with a bit more wonderment.

[1] http://books.google.com/books/about/The_Fractal_Geometry_of_...

[2] http://www.wolframscience.com/nksonline/toc.html

mck-• 14 years ago

"What is the Game of Life"

lukifer3• 14 years ago

When discussing the idea that our universe is simulated, often the assumption is that it's an experiment by aliens or somesuch. But recently I've started to wonder if our parent universe is nearly identical to our own, and we are one of millions of virtual Earths used for political and economic predictions, because if (when) we could, that's exactly what we would do.

k00pa• 14 years ago

That background sound is annoying...

boredguy8• 14 years ago

It's the Shepard–Risset glissando, for what it's worth: http://en.wikipedia.org/wiki/Shepard_tone

milliams• 14 years ago

I assume it's there to match up with the simulation getting faster and faster.

leeoniya• 14 years ago

Yo Dawg! But more seriously, is that carefully arranged structure required for it to work as shown? It seems a slight variation would cause it to evolve into disarray.

koide• 14 years ago

Of course it has to be precise to the cell.

The basic building block is the OTCA Metapixel http://www.conwaylife.com/wiki/OTCA_metapixel

smackfu• 14 years ago

Yeah, add one pixel in the wrong place and the thing would implode.

danielatc• 14 years ago

There even is a 3D version of the SmoothLife algorithm out there: http://www.youtube.com/watch?v=bxaOnOVGepI

Very very cool stuff!

jmaygarden• 14 years ago

Interesting! It reminds me a little bit of a lava lamp.

vastinfest• 14 years ago

Nah.. I better wait for the game of life emulated in the game of life emulated in the game of life..

Sorry.. I was forced at a gunpoint to do that..

bockris• 14 years ago

At which level do you mean this game? http://en.wikipedia.org/wiki/Life_(board_game)

;-)

espinchi• 14 years ago

I'll go get the mop to clean up the pieces of my brain that are now all over the floor.

After spending some time before reading up on the Game of Life, I'm amazed by this meta implementation.

By the way, why not go on and on recursively?

rauljara2• 14 years ago

According to the wikipedia link(http://www.conwaylife.com/wiki/OTCA_metapixel), each meta cell has 64691 actual cells. So to do a 100x100 grid once is 646,910,000 bits, or about 77 mb of storage at one bit per cell[1]. To do a 100x100 grid recursively just once would be 4.75 peta-bytes. Each cell would also have to be touched at least once per frame, so without even getting into drawing the damn thing we're talking about super computer levels of processing power.

[1] Unless you cheat by taking advantage of the fact that most of the cells are just repeats of each other. But cheating doesn't seem anywhere near as awesome.

edit--- That was actually a gross underestimation. The bounding box on the meta pixels is 4235364 cells, or about 65 times as many I said. So it's about 4.9 GB to do a 100x100 grid without any recursion. It's 643 zetabytes (2^70) to do it recursively once. It kind of makes me think that whoever did the video might have cheated even for that small animation.

raganwald• 14 years ago

"Cheating" by taking advantage of repetition is exactly how Bill Gosper's famous "HashLife" implementation handles really huge universes.

Here's my implementation in CoffeeScript, written in the "Williams Style:"

http://recursiveuniver.se

rubidium• 14 years ago

Simply amazing. I hadn't heard about "Life enthusiasts" until reading the linked articles in the post. The OTCA metapixel (http://www.conwaylife.com/wiki/OTCA_metapixel) is what allows this to work.

I bet Dwarf Fortress and Life enthusiasts would get along.

dexen• 14 years ago

Regarding the movie -- to show the 3rd level just as well, camera should pan out to include the programmer ;-)

jamesrcole• 14 years ago

I think GoL unit cells http://www.conwaylife.com/wiki/Unit_cell like this demonstrate an important point. That there's certain limitations to our knowledge of reality.

Imagine an intelligent being in a GoL board, made of a huge pattern of cells (just like we're made of a huge number of atoms).

Even though when we look at a GoL board, we know it's made up of cells and that everything operates according to a fixed number of rules, this intelligent being wouldn't just be able to know this. It's perceptual system would be made of these elements (perhaps it somehow uses spaceships to find out about what is out there). Remember that you can't just "see" reality - you need inputs and to infer what's out there on the basis of them. The sort of view of its reality it could infer would be much more coarsely grained than at the level of individual cells, just as our unaided view of reality is much more coarsely grained than the level of individual atoms.

That intelligent GoL being could observe the way things behave and, on the basis of this, theorise the GoL rules - that everything was a bunch of cells, and that if there's an empty cell and it has three neighbours then that cell will be 'on' in the next moment, and so forth.

And if it existed in a 'standard' Game of Life board, it would have theorised correctly. But if it lived in a Game of Life board where each of the cells it has posited is actually one of these unit cells like in the linked page, then there would be a deeper reality than it realises (and of course there could be 'deeper levels' within that).

There's no way that GoL being could tell.

jerf3• 14 years ago

Generalized: There's no way to know which Turing Complete substrate we are "truly" running on. We can examine the parameters of our system and hypothesize which rules are the most parsimonious to produce the system we live in in the Occam's Razor sense, but we can't prove it.

d2vid• 14 years ago

How about triggering a buffer overflow? Assuming the Turing Complete substrate doesn't have infinite memory, maybe we can break out ;)

jokermatt999• 14 years ago

You would likely enjoy Permutation City by Greg Egan if you haven't read it yet. It touches on the idea of viewing a simulation from the inside.

jared314• 14 years ago

If you also implemented it on other GOL variants (pentagonal, hexagonal, multicolored) it would be a virtual machine.

Makes me want to build a compiler back-end for one of the GOL turing machines.

eranation• 14 years ago

Here is the video that inspired this one: http://www.youtube.com/watch?v=QtJ77qsLrpw

dllthomas• 14 years ago

It is completely unsurprising that this is possible - GoL is turing complete and obviously we can run GoL on turing equivalent systems.

It is really awesome that someone was able to do the attendant engineering work.

lelf• 14 years ago

http://www.youtube.com/watch?v=D6aP9S9rEQk — all the way down

shocks• 14 years ago

Save yourself and mute the video.

sakai2• 14 years ago

Bizarre / incredible timing. I just created an interactive D3.js implementation of Conway's Game of Life yesterday: http://boydgreenfield.com/conwayjs/

Would love to hear peoples' thoughts...

(And sorry for the promotion)

zevyoura• 14 years ago

Nice job. I think some good next steps would be speed controls and the ability to draw/erase by clicking and dragging.

sakai2• 14 years ago

Indeed. Definitely on the list. (And thanks!).

datadata• 14 years ago

The cells appear to rectangular and not square.

joezydeco• 14 years ago

I'm gonna wake up and get flushed out a sewer pipe, aren't I?

unabridged• 14 years ago

My favorite thing to do with metacells is to destroy a small part of one of them and watch the chaos. Digital cancer.

obsession• 14 years ago

This was surprisingly fun to do. Adding just one cell in the right place destroyed the whole metagame.

digeridoo• 14 years ago

I never quite get the excitement over game of life (is emergent behaviour really that surprising?), but this is extremely impressive.

Cbasedlifeform• 14 years ago

Amazing... I'm old enough (sigh) to remember reading about Life in a Martin Gardner column 40 years ago and playing it on a piece of graph paper.

TheEzEzz• 14 years ago

It should be possible to make a closed loop video. When you zoom out to the full meta level it is exactly the same as the initial frame of the movie. Then the whole thing can be looped seamless forever, as you zoom out to meta-meta-meta levels.

dchichkov• 14 years ago

The size of the field, is it fixed or growing? I guess, if it is fixed, this implementation still needs some work...

Either way, I think that Turing Machine with infinitely growing stacks [see http://rendell-attic.org/gol/fullutm/index.htm] is a way cooler.

po• 14 years ago

Also interesting to nerds like me is that the annoying audio in the video is a seemingly always-increasing tone called a Shepard Tone:

http://en.wikipedia.org/wiki/Shepard_tone

edit: …and now reading that I've stumbled across the Tritone paradox which I wasn't familiar with and is equally cool.

http://en.wikipedia.org/wiki/Tritone_paradox http://deutsch.ucsd.edu/psychology/pages.php?i=206

The game of life emulated in the game of life

Related Stories