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 :)
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.
I don't know if one could call NKS terse, at over 1000 pages. It was a very enjoyable and mildly enlightening read, I'd recommend it, but I'd really like to see his theories fleshed out in a more formal way. It was a bit heavy on conjecture and speculation for me.
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.
If true, this has an interesting implication - if our parent universe bothers to do it, it probably means they get useful information from it. That means that the recursion eventually terminates, that eventually in some great great grandchild universe they are able to produce the seed of the answer to whatever the original question was, rather than start another simulation.
My intuition is that the recursion shouldn't hurt getting useful results, even if the simulation was allowed to proceed past the point where such a simulation was developed (which they may not have), in a manner akin to the resolution of Zeno's Paradox. Though there's likely a bound on how many layers deep we can go, but my quantum information theory isn't what it used to be so I have to hand wave my conjectures.
That would apply to real-time simulations. But wouldn't every layer run successively slower? The inhabitants wouldn't notice how fast their simulation is running in the (grand)parent universe. So given infinite time the layering could be infinitely deep.
It could also simply be monitored for CPU usage, and have the process auto-terminate when spiked by recursive children. Creating our own Virtual Earth might then destroy the universe. :P
Another disturbing thought: if our universe were spun up or down like we do virtual machines, would we even notice?
I imagined I had given some thought to these subjects, but Permutation City did have new ideas. If you slow down a simulation to some ridiculous degree, the simulated beings don't notice. Even if you run the simulation backwards or in random order, they wouldn't notice. If you abruptly shut it down, they'll just continue finding the pattern somewhere.
If the recursion spawns an average of more than one child universe per parent universe, then it would spawn an infinite number of universes, and maybe this is still the first run which, to the disappointment of our unknown benefactors, will produce no useful information.
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 ?
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.
You make me a bit jealous, rubbing shoulders with Conway and Gosper. Martin Gardner's October 1970 column in SciAm introduced me to cellular automata, and I spent a few hours meticulously tracking generations on a checkerboard before it occurred to me that the university's IBM 1130 was probably better than I was at that sort of thing. Soon friends and I were writing competing Fortran programs for that 1130, monopolizing it all night every night, calculating Life.
I corresponded with Gardner once or twice, and subscribed to Robert T. Wainwright's Lifeline newsletter, which had begun a taxonomy of Life objects and reported community progress. Our little group was surprisingly competitive in the beginning, considering the limited resources at our backwater university, but when the MIT group kicked into high gear the exploits of Gosper, Woods and others at MIT were simply mind blowing. Woods' Atavist backtracker, Gosper's Glider Gun, the first discovery of a Garden-of-Eden configuration... who could compete with that? And Gosper continued to amaze with his astonishing Breeder.
Conway's GoL inspired other acquaintances, electrical engineers. One of them built a special-purpose computer to compute generations; he'd have surprised to know then that the computer was Turing-complete. Another EE pal built a crude raster display for the lab's Nova 1220 mini, with the specific intent to display GoL generations. Hardly such a thing as glass TTYs in those days, kids.
Sorry for the free-association; you know how old guys get. Think I've still got my old stack of Lifelines around, stored in the garage. Maybe I'll haul 'em out like an old yearbook, and see how they go with a Stone Levitation.
> Sorry for the free-association; you know how old guys get. Think I've still got my old stack of Lifelines around, stored in the garage. Maybe I'll haul 'em out like an old yearbook, and see how they go with a Stone Levitation.
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.
I have always been fascinated with cellular automata. I think they serve a really good purpose in being a "fun" way to approach complexity and it's consequences and I spent more than a few hours playing with game of life programs especially when I was younger.
But I am still curious as to who has the time to engineer with them? Is it just "hobbyists" or do some academics derive useful work out from pursuing them?
One thing that may be worth pointing out is that the hobbyists do not engineer their Life systems by sitting in front of a grid and clicking one square at a time. A large bank of off-the-shelf technologies has been built. Building something large like this life simulator is not trivial, but it's not as hard as it looks, either. You're sort of seeing the machine language view of a program built with a lot of advanced C++. The effort to build is a lot less than a casual perusal of the machine language may indicate. (Though I still respect them for it.)
> Is it just "hobbyists" or do some academics derive useful work out from pursuing them?
The excessive search for "useful work" is one of the bigger problem of academia today. Even the most practical research usually doesn't look useful at the beginning, and pursuing things that seem immediately applicable to real-world problems can be a form of premature optimization. Not to say we shouldn't pursue the "practicality" route at all, but today most research seems to be optimized for short-term money generation and/or fame.
Anyway, cellular automata are a separate research field, and I'm pretty sure that some of those game-of-life engineers are academics who are doing this as research because it's fun/interesting. And hail to them, because those hobbyst-scientists create tools that enterpreneurs can forge progress with.
It's not Conways life, but biologists use cellular automata as models to show that simple rules can create such things as a zebra's stripes, a leopard's spots, the competition between bacterial colonies, development of the human brain, etc. Google "cellular automata in biology" for examples (the first hit I got is http://www.math.pitt.edu/~bard/pubs/jtb_ca.pdf. Twenty years old, but to my outsider's eye, it appears to be a decent overview)
I did simulations of spread of fire and smoke inside buildings with cellular automata for my BSc. CA's have lots of interesting applications in many different domains, even not related to science itself.
> complex patterns can emerge from the implementation of very simple rules... "design" and "organization" can spontaneously emerge in the absence of a designer
Self-organization is fascinating stuff; I suppose the economic corollary would be the "invisible hand." But in this example, is there not a "designer" setting the "simple rules" that make the self-organization possible?
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
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).
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.
The idea has been explored in "the literature", which in this case is a really fancy-pants way of saying "science fiction". In the general case, since we can't figure out what the consequences of a crash are, I don't think I'd recommend it, but if we can get specifics, who knows?
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.
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.
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.
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.
Bizarre / incredible timing. I just created an interactive D3.js implementation of Conway's Game of Life yesterday: http://boydgreenfield.com/conwayjs/
Reading Game of Life descriptions feels like reading papers about quantum physics :)