Conway's Game of Life | Hacker News Reader

Conway's Game of Life

experimentgarden.blogspot.com

22 pointsNathanKP18 comments

I've been on a little Conway's Game of Life kick for the past couple weeks myself. Such a simple algorithm like this is great for learning a new programming language.

I recently started learning python, so I wrote an implementation using the pygame library. If you're interested, you can see it here: http://readysquid.com/blog/programming/conways-game-of-life/

Feel free to take the source and play with it if you'd like.

Nice share. It probably can't compete with a major Game of Life simulator such as Golly, but I agree that Conway's Game of Life is an excellent little programming project that is entertaining to implement in different languages.

This article that you linked to from your site: http://lbrandy.com/blog/2009/07/computational-performanc-a-b... Is really eye opening.

So rarely are the theoretical aspects written about. At least this one mentions a Turing Machine in passing.

Think about that. We can build a Life pattern that looks for a counter-example to the Goldback Conjecture (GC). We can build a Life pattern such that if the GC is true, the pattern will grow forever, but if it's false, then the pattern self-destructs.

With our current knowledge in mathematics, no one can tell the eventual fate of the pattern. That's a pretty deep result, equivalent (sort-of) to the Halting Problem.

I wish someone had told me that when I was writing my first "Life" simulators in 1979.

Note: The GC says every even number from 4 onwards can be written as the sum of two primes. If you like you could use another unsolved problem, like the Collatz conjecture - http://en.wikipedia.org/wiki/Collatz_conjecture

Good point. The theoretical aspects of Conway's Game of Life are really eye opening. Interestingly I have found research material that hints that Conway designed the rules specifically so that it would not be possible to determine whether or not a pattern would grow indefinitely.

It is not possible to prove that there is a pattern which can grow endlessly.

That's not quite right. Conway originally intended that no pattern could grow indefinitely, but a pattern was quickly found that could grow forever: the Gosper glider gun. http://en.wikipedia.org/wiki/Gun_%28cellular_automaton%29

What process did people use to discover patterns like this? Is there a special rule for being able to incrementally build up a pattern in Life?

True. I was thinking about growth in which it was not an oscillating reaction.

Some of this will repeat earlier comments, but I'm including them here for completeness. I'm not an expert in this, so some of it might be wrong in the detail.

Firstly, there is a comparatively simple pattern that grows endlessly - the Gosper Glider Gun.

http://en.wikipedia.org/wiki/Gun_%28cellular_automaton%29

Someone asked about the processes used to create these sorts of things. If you read about Bill Gosper:

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

you'll see that he's a hacker's hacker. If you analyse the GGG you'll see that it can be broken down into smaller pieces, each of which is a small modification of something small and easy to understand. In essence, you can build a GGG from small components, and then optimise it, the entire process being like writing a computer program, perhaps in something like BrainFuck: http://en.wikipedia.org/wiki/Brainfuck

I might meet Gosper in March next year. I've made a note to ask him if that's actually what he did. From what I've read, it is.

The question about "growth in which it was not an oscillating reaction" is hard to pin down, and it's not clear what you mean. I would guess you mean something like:

    A pseudo-periodic pattern is one which can be
    divided into two areas, P and P'. Inside P the
    pattern is periodic, and in P' the pattern is
    comprised of units, each of which is periodic
    under some isometry.

Well, using GGGs you can beat that definition too, because you can construct patterns that build GGGs at a distance, and then you can make a Turing Machine that computes the digits of pi, then you can build GGGs at distances that get further away by the amount that is a digit of pi, and then you have something that's still sort of predictable, and still isn't what you want, but still satisfies the above definition.

Part of the problem is making precise make precise what you mean. I suspect you're trying the equivalent of proving the existence of non-computable numbers, and then asking to show one. Counting arguments suggest that amorphous patterns that grow indefinitely exist, but they're the equivalent of uncomputable numbers. I can't show you one.

Interesting, I just ran across this wiki a couple of days ago

http://www.conwaylife.com/wiki/index.php?title=Main_Page

Conway's - too damn - interesting. After a few months I saw myself in one of those flip-flops.

I posted this the other day : http://news.ycombinator.com/item?id=725017

More life patterns than you can view in a week.

This applet has a bunch of interesting patterns. Click "Enjoy Life" then "Open"

http://www.ibiblio.org/lifepatterns/

someone should write an iPhone app for this. it would be a big hit

There already are a number of iPhone implementations of Conways game of Life: http://ax.search.itunes.apple.com/WebObjects/MZSearch.woa/wa...

Reading the reviews, its not really a hit; people don't always seem to get the game.

Too bad. Perhaps if it was made into more of a game, with a multiplayer aspect it would be possible.

How could you make Life into "more of a game"? Let two people make figures and hope they move in the general direction of one another to "fight"?

I played a version once that shipped with an old windows game pack. Each turn, each player was allowed to add one cell of their color and remove one of their opponent's, after which the rules were applied. The goal was to eliminate all of your opponent's cells. I remember finding it fun at the time, but I haven't played it in years.

Edit: I found the wikipedia article for the game: http://en.wikipedia.org/wiki/Life_Genesis

Great idea. I can definitely see that taking off. I even thought it would make a great RTS game.

How fast can you build spaceships and breeders to destroy the enemies spaceship fleet.

Though it is a cellular simulation it is also a game.

Reply on news.ycombinator.com