×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

A New Glider Found For Conway's Game of Life

timothy posted about a year and a half ago | from the also-a-new-number-between-11-and-12 dept.

Math 50

An anonymous reader writes "Conway's Game of Life is now forty two years old, but it continues to inspire as well as being the basis of an actively researched field, with computer scientists now announcing they have found a new form of the famous 'glider' pattern (once suggested by Eric S Raymond as the insignia of computer hackers) that runs over a so-called Penrose universe."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

50 comments

Life enthusiast (5, Funny)

Apocryphon (1849660) | about a year and a half ago | (#40904335)

"Life enthusiast Adam Goucher has discovered ...."

About time! I've always found the terms pro-life and pro-choice too politicized and constraining.... I'm a life enthusiast!

not life as we know it (5, Informative)

Dave Whiteside (2055370) | about a year and a half ago | (#40904431)

it's not a new glider in the game of life , but a glider in the Penrose tiled universe - inspired by Conways Game of life...

the article need to be read

it is seriously cool though

Re:not life as we know it (4, Funny)

Thud457 (234763) | about a year and a half ago | (#40904615)

not life as we know it

I'm a doctor, not a tile layer, Jim!

Re:not life as we know it (0)

Anonymous Coward | about a year and a half ago | (#40907371)

You got the quote wrong. It is:

I'm a doctor, not a bricklayer.

Re:not life as we know it (0)

Anonymous Coward | about a year and a half ago | (#40907707)

not life as we know it

I'm a doctor, not a tile layer, Jim!

Bricklayer.

One lays bricks. One can even lay cable.

Tiles are set.

Re:not life as we know it (1)

Anonymous Coward | about a year and a half ago | (#40905323)

_I'd_ always played in the original orthoginal universe. Never considered other tilings - but isn't Penrose rather messy and counterintuitive?
Now that I think about it, I'd have thought the next logical universe would be hexagonal. Has anyone _created_ an hexagonal application/simulation?

Re:not life as we know it (4, Informative)

uigrad_2000 (398500) | about a year and a half ago | (#40905611)

I'm pretty sure I attempted a hexagonal game of life. It's the first thing people would think to try after discovering Conway's original version.

The problem with the hexagonal version is that each tile has only 6 neighbors, as opposed to 8 in Conway's version. This reduces the complexity so finding interesting patterns is a lot more difficult. The way around this is to add more states.

After reading the article, it sounds like one researcher theorized that a stable glider could not be found for the Penrose tiling, and offered $100 to anyone who did. Some other friends of his found an answer, but had to "cheat" by expanding the number of states (for a given tile) from 2 to 4.

It is kind of cool, or would be if they actually showed the 4 states and the exact rules. Since they decided to leave the technical explanation out, it's a rather uninteresting article. It's not really slashdot worthy, in my own humble opinion.

Re:slashdot worthy (2)

TaoPhoenix (980487) | about a year and a half ago | (#40905755)

I dunno, at the rate which we aggressively avoid reading TFA's, maybe it is Slashdot worthy - someone who really is interested will deep-click to the meaty theory on the web.

Re:not life as we know it (0)

Anonymous Coward | about a year and a half ago | (#40907367)

It's the first thing people would think to try after discovering Conway's original version.

That would probably depend a lot on what software they were using (or if writing their own). The most straightforward thing to me to try after Conway's version is different rule sets followed by non-binary state rule sets like wireworld. Those can be distracting enough to not get around to finding or writing a program to run on different grids.

Re:not life as we know it (0)

Anonymous Coward | about a year and a half ago | (#40908055)

You can work out the rules by watching the video. Here's my guess from a cursory watching:

Four states:
  + blue = empty
  + lime = tail
  + teal = head
  + red = "feeler"

Rules:
1. A feeler tile is replaced by an empty tile

2. A tail tile, or any empty tile with both tail & head neighbours (corner-neighbours count) becomes a feeler tile.

3. An empty tile sharing an edge with a head tile, and neighbouring a feeler tile (corner-neighbours count) becomes a head tile.

4. A head tile with a feeler neighbour becomes a tail tile.

Basically, the glider puts out "feelers" from the head-tail joint, which rule out possible paths. This singles out the one tile that leads forward - the one edge of the head with no feeler - which then becomes the new head.

Re:not life as we know it (1)

WildBlueYonder (1714974) | about a year and a half ago | (#40923301)

That would be an interesting next step to take. When I took my first CS class I put my own spin on the Game of Life, it was still an orthogonal board, but with two species, Cows and Wolves, with different propagation rules. You could make some interesting gliders with them, the Wolves appeared to chase the Cows.

Re:not life as we know it (0)

Anonymous Coward | about a year and a half ago | (#40905831)

I see timothy is showing his typical level of reading comprehension.

not the same (2, Interesting)

eyenot (102141) | about a year and a half ago | (#40904475)

They didn't prove anything except that by increasing the complexity of 'Life', they can force some kind of complex behaviour that would have been impossible for the simpler version we're all more familiar with. They changed the rules from 'alive or dead' tiles to '00 01 10 or 11' tiles. There are two different rhomboids in the Penrose tile universe they're playing in, so it seems to make sense that you will find some sufficiently complex means of navigating it if you observe two bits at once.

I think it should have been couched differently: Penrose universe NOT non-repeating, given a sufficiently complex, self-changing pattern to look for.

Re:not the same (4, Insightful)

ceoyoyo (59147) | about a year and a half ago | (#40904617)

You have it backwards. By increasing the complexity, namely by making the pattern of tiles non-repeating, it was believed things like gliders were impossible. That turns out not to be the case.

The existence of the glider has nothing to do with whether the universe is non-repeating or not. Penrose universes are mathematical constructs that are proven to be non-repeating.

Re:not the same (0)

Anonymous Coward | about a year and a half ago | (#40906031)

Sorry, you're both right/wrong. First, they made the pattern of tiles non-repeating, and gliders seemed (still) impossible.

Then, they changed it so the tile could have 4 states instead of just 2. And then they found a glider for that case.

toinspire? (-1)

Anonymous Coward | about a year and a half ago | (#40904559)

what the fuck is a "toinspire"?

I can't wait! (0)

Anonymous Coward | about a year and a half ago | (#40904569)

Maybe in 42 years, Crawford will finally release Warp Life.

Continues toinspire (0)

kriston (7886) | about a year and a half ago | (#40904595)

I can't deny that I almost had to look up the word "toinspire" in the dictionary.

Re:Continues toinspire (0)

Anonymous Coward | about a year and a half ago | (#40905079)

At first I thought it was some play on Toynbee but then I guess that would be toynspire. Not sure what that would be mean, maybe to generate an initial interest and then be relegated to academic history.

Re:Continues toinspire (1)

julesh (229690) | about a year and a half ago | (#40920659)

That's 'cos you're not Irish. If you were, you'd know the toinspire is what you find on top of the toin church.

Faster than light.... (1, Interesting)

stanlyb (1839382) | about a year and a half ago | (#40904623)

Do you know that this game proved the possibility of having speed faster than the speed of the light? God Bless The Speed Of Information.

Not so fast Sparky (0)

Anonymous Coward | about a year and a half ago | (#40905569)

I'm pretty sure exchange of information is still bound by the speed of light. If you have any information on the contrary, let's have it on the table please!

Re:Not so fast Sparky (0)

Anonymous Coward | about a year and a half ago | (#40905897)

I want the information yesterday.

Re:Not so fast Sparky (1)

hairyfeet (841228) | about a year and a half ago | (#40907363)

I take it you missed the article from about a week ago about quantum entanglement and the possibility of making a functional Maxwell's demon?

The more we learn about the quantum world the more I think we are like those classical scientists that thought everything was made of of four classic elements, the whole air/fire/water/earth bit. It is looking more and more like what we can see with our eyes is just this teeny tiny layer at the top that tells us about as much about what is really going on as throwing a log on a fire showed those early observers thousands of years ago who thought that the fire must be contained within the log.

Re:Not so fast Sparky (1)

kestasjk (933987) | about a year and a half ago | (#40911703)

about quantum entanglement and the possibility of making a functional Maxwell's demon?

Are they those floating red things in Doom?

No... (1)

Anonymous Coward | about a year and a half ago | (#40906005)

The famous "warp tunnel" construct in Conway's Game of Life did not make information go faster than the speed of light.

It did make information move across the board faster than the theoritical limit of the board. But nothing actually moved across real space faster than the real speed of light.

Also...the trick by which this was accomplished involves constantly creating the information in advance and failing to destroy it from the back-end when something else is present (which itself gets destoryed). A difficult act to stage in the real world. And anyway, how would you feel about that star trek transporter beam if you knew it created the other you on the ground several minutes before the current you even stepped up to the platform to be destroyed?

Re:Faster than light.... (0)

Anonymous Coward | about a year and a half ago | (#40907483)

The star gate setup in game of life doesn't really move information faster than light, even if looks that way. It is no different than having a chain of train stations along a rail, each with a train set to leave a predetermined time. You can chose the times such that the train would leave a little before one from the previous station gets there, then tell the train to stop a short time after it leaves if the previous train doesn't arrive (after all, the glider coming out of the star gate arrangement is traveling a c/2 and can be still influenced by information catching up to it).

If you can set predetermined times for things to happen, you can get all sorts of things to appear to happen faster than the speed of light even in real life. You can create a marquee light sign that shows a pattern moving faster than the speed of light. Wouldn't be hard to synchronize if each light is connected by an equal length wire to a controller (or different length wires just using propagation time for timing). Still doesn't send information faster than light as you need to wait long enough for signals to propagate down all the wires before starting the display, i.e. the signal for the final light already has to be en route before it looks like the light signal starts.

As expected... (5, Informative)

vlm (69642) | about a year and a half ago | (#40904691)

Its creation is an achievement because gliders were previously thought to exist only in regular cellular automata, such as the most famous one, the Game of Life

On wikipedia that would get flagged as weasel words (or the whole article deleted for non-notoriety). Who thinks gliders should only exist in regular automata? If anything my opinion is that modern automata thought was the other way around, expecting them to exist.

Note that gliders are not rare or unusual in automata. Some of the first original researchers thought that only gliders/spaceships that exist lived only in Conways GoL but further research a long time ago showed they're ridiculously commonplace in other rulesets. As seen below. So the tone of this discovery is more accurately described as "much as we suspected, but never bothered to prove, until now" rather than the stereotypical serendipitous discovery tone of "that result looks weird, WTF, who ever would have guessed"

This is separate from the penrose tile thing, which I don't follow. It might, or might not, be the case that a glider in the very specific ruleset of penrose tiles is a hard problem. But in the wide universe of all rulesets, gliders/spaceships and stuff seem very widespread. As a general rule if a ruleset is terminally boring then it definitely does not have gliders, but if its not terminally boring then almost all of them have either chaotic and/or glider-like behavior.

http://www.ics.uci.edu/~eppstein/ca/ [uci.edu]

".... I have investigated whether gliders exist in many semitotalistic rules similar to Life, where the behavior of a cell depends only on its own state and the number of live neighbors. The results show that the existence of gliders is commonplace ....."

http://uncomp.uwe.ac.uk/genaro/rule54/glidersRule54.html [uwe.ac.uk]

".... We displayed all gliders of Rule 54 including two new glider guns (also extensible) ... "

Rule 54 has nothing to do with the famous rule 34. Well I guess there are self replicating patterns in CA rule 54 which could be interpreted as pr0n by another one dimensional cellular automata, I guess.

Re:As expected... (3, Interesting)

sFurbo (1361249) | about a year and a half ago | (#40905053)

Gliders are commonplace on repeating grids. According to TFA (and this makes sense), it was thought that they could not be made on non-repeating grids. After all, which direction should it follow? How to make sure it can even exist in the place it will move to?

However, I feel that by allowing more types of tiles, it should be clear that it was possible. For example, with four types of cells, you could have
"front of glider" (becomes "back of glider")
"back of glider" (becomes "not glider")
"side of glider" to keep the rest in check (keeps status unless in contact with "back of glider", when it becomes "not glider")
"not glider" (becomes "side of glider" if in contact with one "side of glider" and one "front of glider", becomes "front of glider" if in contact with two "side of glider" and no "back of glider")

This seems to be what they have done.

Re:As expected... (1)

vlm (69642) | about a year and a half ago | (#40907399)

it was thought that they could not be made on non-repeating grids.

I think its a general emergent behavior thing.

So if something really simple results in ridiculously unpredicted behavior, it seems very unlikely that a system that's even more complicated would have to be more boring. Aside from penrose tiles, just look at the world... much more complicated rule set than Conways GoL (don't get started on the combinatorial and bitstream physics guys here) and movement is in fact possible in the world.

Another good example is the more dimensions and neighbors a CA has, the more "entertaining" it becomes. So adding weird topology is also, at a gut level, strongly likely to be entertaining.

http://en.wikipedia.org/wiki/Emergence [wikipedia.org]

Re:As expected... (1)

sFurbo (1361249) | about a year and a half ago | (#40907647)

It really is a balance: Give it too few possibilties, and it becomes boring. Give it too many possibilities, and it becomes random. Entertaining is somewhere in between. I would put gliders, as defined in CA, at the lower end of interesting, so making it more complex could remove gliders. Gliders isn't just movement, roughly speaking it is movement without change. A rock flying through the ground is a glider, a horse isn't, as it uses energy, so it doesn't return to the same state.

Re:As expected... (0)

Anonymous Coward | about a year and a half ago | (#40905703)

Rule 54 has nothing to do with the famous rule 34.

Rule 34 [wolframalpha.com] is

terminally boring

, but "nothing" seems a bit exaggerated. related alt text [xkcd.com]

Re:As expected... (1)

Anonymous Coward | about a year and a half ago | (#40906995)

self replicating patterns in CA rule 54 which could be interpreted as pr0n by another one dimensional cellular automata, I guess.

Glider Guns are the original CA money shot. Don't get me started on Glider Eaters.

Re:As expected... (1)

radtea (464814) | about a year and a half ago | (#40907857)

The New Sensationalist article starts out:

If someone asked you to walk in a straight line over a constantly shifting floor, you would probably declare it impossible after a few tries and a couple of grazed knees.

Either that, or you're a sailor and have no difficulty walking a straight line over a constantly shifting deck, and think that this declaration is silly, as well as being an excellent example of the fallacy of composition: Penrose tilings have no globally repeating patterns so no globally straight glider path can exist, right?

Wrong: Penrose tilings are full of local order (thus the name "quasi-crystal" for naturally occurring structures with 5-fold local symmetries) and that creates the possibility that a sufficiently adaptive automaton that exists on a comparable scale to the local order (four or five tiles across, maybe up to ten) will be able to thread its way through the extremely rigidly defined deviations from perfect regularity to generate a straight course.

There are a couple of interesting things about this result that the New Sensationalist misses. One is: how come 4 states? Could this have anything to do with the five-dimensional regularity that Penrose tilings are based on? Another is: what about tilings with even less order? One could create a tiling that has no order whatsoever... would it still be possible to build a glider on it? Does the number of required states scale with the order parameter?

The word you are looking for is cellular automaton (3, Informative)

Hentes (2461350) | about a year and a half ago | (#40904855)

This not Conway's game of life.

Re:The word you are looking for is cellular automa (0)

Anonymous Coward | about a year and a half ago | (#40917425)

You right!

Not Hasbro's Game of Life (1)

hawguy (1600213) | about a year and a half ago | (#40904915)

When I first read the summary, I thought they meant Hasbro's Game of Life [hasbro.com], which as a child, is much more fun than a cellular automaton.

Re:Not Hasbro's Game of Life (1)

nitehawk214 (222219) | about a year and a half ago | (#40906353)

When I first read the summary, I thought they meant Hasbro's Game of Life [hasbro.com], which as a child, is much more fun than a cellular automaton.

I would disagree for the state of today's children's educational passtimes. Logo and Conway's were great fun to play with as a kid. But at least Hasbro's Game of Life did show that you always do better by getting a college education.

Re:Not Hasbro's Game of Life (1)

TheCycoONE (913189) | about a year and a half ago | (#40906771)

I don't know, as a child I had a competitive multiplayer version of Conway's Game of Life that was pretty fun.

Actually I wish I remembered what it was called. Each player could place a number of cells, then a configurable number of rounds pass and you can place again. The goal being to wipe out all the other players cells. Different colored cells would participate with each other for suffocation, and iirc for replication it would match the majority of the neighbors.

Re:Not Hasbro's Game of Life (1)

makomk (752139) | about a year and a half ago | (#40908215)

I think it was part of one of Microsoft's freebie game packs that came bundled with PCs in a distant long-ago era.

Game of Fuck (-1)

Anonymous Coward | about a year and a half ago | (#40906541)

I used to be fascinated with a lot of game of life type stuff and CS things in general until that ESR fuckwad came along. What a fucking blowhard buttcake. Take your VALinux money and your guns and shoot some pussy. Don't forget to thrust that dildo up your ass 3/4 of the way in.

How many commercials did you have to sit through? (1)

Lando (9348) | about a year and a half ago | (#40908349)

After the third, I figured I wasn't going to wait any longer to get to the content. Time to blacklist newscientist I guess.

Model for the universe? (0)

Anonymous Coward | about a year and a half ago | (#40910423)

Wolfram's New Kind of Science [wolframscience.com] suggests that the universe may operate on a quantum level as a cellular automata, his idea being that complex structures can come about from simple rules. Although it's not particularly surprising that the Penrose tile system has gliders, I take this as the first interesting example of signal propogation in a non-regular model. Penrose tiles still have a lot of structure, so maybe it's still to special a case, but it's progress.

Stupid Slashdot! (1)

SigmundFloyd (994648) | about a year and a half ago | (#40915919)

This is NOT "Conway's game of life". I rushed frantically to TFA in disbelief, only to be disappointed.

Are your misleading titles and summaries a pathetic attempt to prove you can still pull a "slashdot effect" on sites nowadays?

Be warned, your readership's patience is not endless. Mine certainly isn't.

Lamers.

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...