The Game of life is a simple set of mathematical rules which can generate very complex, unpredictable behavior.

It is interesting because the laws of physics are also very simple, and also give rise to incredibly complex things, such as human society, everything. If you could create an initial setting to the game of life that would eventually change into a turning machine which implemented a strong ai, what would be the status of a picture of that initial bit pattern?
It was created by John Conway.

Rules to the Game of Life

These are the rules to the game of life. This formulation of the rules is easy to understand and makes a lot more sense to me than the traditional explanation.
Definition: The Neighbors of a cell are the live cells touching it, either orthagonally or diagonally.

setup: start with a grid, with each cell either alive(black) or dead(white).

Explanation: Each grid is a frame in an animation. The next frame is created using the current one.

Rule to generate the next frame from the current one:
2 neighbors - same
3 neighbors - alive
else - dead


Procedure: apply the rules to every cell in the current grid, and write the result into the same cell on the new grid.

From one frame to the next:
  • If a cell has exactly 2 neighbors, it will not change.
  • If a cell has exactly 3 neighbors, it will become alive.
  • In any other situation, the cell is dead in the next frame.
The best-known example of a cellular automaton; refers to the cellular automaton with these simple rules:

grid = planar square grid
neighborhood = 8 cells adjacent to a cell either orthogonally or diagonally
generation = all cells with fewer than 2 or more than 3 neighbors die, while a cell is born in each empty node with exactly 3 neighbors.

These simple rules generate amazingly complex, chaotic behavior, but balanced in the sense that it always settles down after a while to a static or oscillatory state.

See also: barber pole, barge, beacon, beehive, blinker, block, boat, clock, eater, fishhook, glider, glider gun, loaf, long barge, long boat, long ship, pond, ship, sinking ship, spaceships, toad, tub.

Sometimes lies were more dependable than the truth --Ender (Orson Scott Card)

Individual human beings are all tools, that the others use to help us survive --Graff (Orson Scott Card)

He chuckled. "Non, non," he said. "M'sieur Alf, look around you. Look inside yourself. Life is all power games. Everyone wants to be the God of something, tout le monde. It's just a question of how big a kingdom we can each carve ourselves, how high we can raise. --Count Cagliosro (Alfred Bester)

One way of perceiving the life that we live and the workings around it is that of a game in which we are all players and pawns in each other's game of survival and dominance.

Every person has an agenda - a goal in life. Initially our goal in life is to survive and to establish a goal. Once we have a goal, we seek its accomplishment.

At midlife, we look back on what we have accomplished, our goal, and consider again if we have attained it. There is as much of a crisis in having a goal that is too difficult to attain as there is one that is attained at a younger age, with no more game to play. Both are causes for depression.

The important thing to remember in playing the game of life is that each person will manipulate the others to try to attain their goal. Sometimes our goals coincide and we are able to help each other along the way. Other times our goals clash and a conflict arises. For the most part, the conflict is rare except when people have tied their lives together later to find they are heading in opposite directions. It is rare that the clash of goals occurs outside of this for normally there is more than enough happiness to go around and satisfy all who seek it. However, there are times in career where people will reach for the same object and some must be refused.

Life is a cellular automata invented by professor John Horton Conway in the early 1970's.

The universe is an infinitely large array of square cells. Each cell can be in one of two distinct states: dead or alive, empty or full, or 1, etc. Each cell is adjacent to eight other neighbouring cells.

In every generation, a cell changes state according to its current state and the state of its eight neighbours:

  • If a cell is dead, and has exactly three living neighbours, it becomes alive (a birth).
  • If a cell is dead, and has less than three or more than three living neighbours, it remains dead.
  • If a cell is alive, and has two or three living neighbours, it remains alive.
  • If a cell is alive, and has less than two or more than three living neighbours, it dies.

neigbours: 0 1 2 3 4 5 6 7 8
if dead  : . . . A . . . . .
if alive : . . A A . . . . .   

All cells change state simultaneously. By successively repeating this operation, patterns evolve.


It is rather easy to demonstrate that a 'final' state of Conway's life is not necessarily a static world or a oscillating state.

The simplest case of this is that of a simple glider. This collection of cells will repeat its shape but be shifted in position. In doing so, it no longer remains a oscillating set (such as a blinker).

Some objections may be raised that a change in position does not constitute enough to say that the life world is not oscillating. For those who raise this objection the glider gun should be demonstrated. This is a finite pattern that has unbounded growth - every 30 iterations it produces another glider. In doing this, it has altered the world so that there is another 5 cells in the world and another position that will never repeat itself.

The glider gun is only one such example of infinite growth within Conway's Life. Many other examples of infinite growth can be found (the first of which was the glider gun) and some of them have been listed at:
http://www.argentum.freeserve.co.uk/lex_i.htm#infinitegrowth
http://www.argentum.freeserve.co.uk/lex_t.htm#totalaperiodic

For the purposes of mathematically modeling the rules to the Game of Life (which would be useful if, for example, you want to program your own version of the game), I humbly present the following:

Given that the game is played out on a two-dimensional grid, let f(x,y) be the function describing the state of the grid point (x,y).
If f(x,y) = 1, then the point is alive. If f(x,y) = 0, then the point is dead.

Let N(x,y) be the number of neighbors of (x,y) that are alive. In other words:
N(x,y) = f(x-1,y-1) + f(x-1,y) + f(x-1, y+1) + f(x, y+1) + f(x+1, y+1) + f(x+1, y) + f(x+1, y-1) + f(x, y-1)

The function f'(x,y), which describes whether (x,y) will be dead or alive on the next turn, can be defined as:

          {  0       if N(x,y) < 2
f'(x,y) = {  f(x,y)  if N(x,y) = 2
          {  1       if N(x,y) = 3
          {  0       if N(x,y) > 3

"The Game of Life" is board game originally issued by Parker Brothers back in the 1950s. The game simulated (as much as a board game can) the major life decisions an individual would make from high school until retirement: going to college, choosing a career, getting married, buying a home, having children, living through random windfalls and disasters, and so forth. The object is simply to have the most money upon retirement.

I played this game with my siblings all the time when I was a kid; it's essentially random who comes out ahead at the end, so every player has a chance to win if they don't screw up the major choices. Every game with the same number of players also lasts the same amount of time, so it never drags on. Despite this, it's still just as much fun for grownups as for kids. I recently bought a version to play with my eleven-year-old stepdaughter, and we both enjoyed it equally.

Since it's original release, Parker Brothers has changed the game slightly while keeping the basics identical. Prices have been updated to more contemporary quantities. You now have a chance to choose your salary and career from three randomly-chosen cards, assuming you take the time to go to college. Four kinds of insurance have been resolved down to two: auto and homeowner's. The confusing "stock market" bar has been replaced with "stock certificates" that pay off whenever someone spins that number. Best of all, certain spaces -- "night school", "taxes due", "throw a party", and so forth -- pay off to specific players if those players hold certain careers. All these changes are improvements, IMO: it's easier to follow all the rules, and it's more fun the more people are playing.

However, I still think there's room for improvement. What benefits and losses might be incurred if you don't want to get married, for example, or you choose to pursue a homosexual lifestyle? Why do doctors take just as long to finish college as teachers? Why can't you cash in your stock certificates upon retirement? Why don't you lose money every payday the more children you have? And should there be spaces like "Divorce! Pay half your salary in alimony" or "Tornado strikes! Collect insurance and buy new home"?

Realistically, it's more like "The Game of Idyllic Suburban Life", but then again it was created in the 1950s. It leaves room for good-natured abuse, too. My stepdaughter decided to make up for not having any children one game by stealing my pink-peg daughter and accusing me of leaving her to wander the roadside for three hours negligently. I retorted that it didn't matter if she had the most money at the end: she had never landed on the "Become a born-again Christian" space (there isn't one), so she was going to Hell and all her ill-bought gains would avail her naught in the afterlife.

If you tally up the neighbors using a vertical counter so you have each bit in the neighbor count as a separate variable:
using C operators, | (logical or), & (logical and), and ~ (logical not)

a = state of cell in the next generation
b = state of cell in the current generation
c = bit 2 of neighbor count (count & 4)
d = bit 1 (count & 2)
e = bit 0 (count & 1)

a = (~c)&d&(e|b)
Bit 3 (count & 8) can be ignored (just lose the carry from bit 2) because the rules for 8 neighbors and for 0 are identical. This lets you calculate the next state for multiple cells in parallel.

Truth table:

b c d e | a
-----------
0 0 0 0 | 0
0 0 0 1 | 0
0 0 1 0 | 0
0 0 1 1 | 1 Three neighbors to an 'off' cell.
0 1 0 0 | 0
0 1 0 1 | 0
0 1 1 0 | 0
0 1 1 1 | 0
1 0 0 0 | 0
1 0 0 1 | 0
1 0 1 0 | 1 Two neighbors to an 'on' cell.
1 0 1 1 | 1 Three neighbors to an 'on' cell.
1 1 0 0 | 0
1 1 0 1 | 0
1 1 1 0 | 0
1 1 1 1 | 0

In an attempt to node my homework and do a favor to anyone who needs it, here's the source code in C++ for the game of life.

If you see a way I can optimize it (boy, my code can usually be optimized quite a bit), /msg me, and I'll credit you at the bottom.

Skill level: Moderately skilled beginner


#include <iostream.h>
#include "apstring.h"
#include "apmatrix.h"
// you can get the ap*.h files from the college board website

void dispgrid(apmatrix <int> grid);
void figsurr(apmatrix <int> &grid, apmatrix <int> &grids);
void change(apmatrix <int> &grid, apmatrix <int> &grids);

void main()
{
 apmatrix <int> grid(10,10,0);
// grid holds the alive/dead value
 apmatrix <int> grids(10,10,0);
// grids holds the surrounding alive/dead cells
 char cont='Y';

// this is where we make the base setup.
// you can change it however you want
// everything is declared as a 0 already,
//  so just make it a '1' to start.
// the suggested values for beginning: 
 grid[2][4]=1;
 grid[3][5]=1;
 grid[4][3]=1;
 grid[4][4]=1;
 grid[4][5]=1;
 grid[5][3]=1;
 grid[5][4]=1;
 grid[5][5]=1;

 while(cont=='Y')
 {
  dispgrid(grid);
// display the grid
  figsurr(grid, grids);
// figure out surrounding alive/dead cells
  change(grid, grids);
// do the next generation
  
  cout<<"\nDo you want to continue? [Y/N] ";
  cin>> cont;
  cont = toupper(cont);
  cin.ignore(100,'\n');
// allows the program to repeat
 }
}

void figsurr(apmatrix <int> &grid, apmatrix <int> &grids)
{
 int surr;
// the two for loops run through the whole grid
//  regardless of size
 for(int i=0; i<grid.numrows(); i++)
 {
  for(int j=0; j<grid.numcols(); j++)
  {
   surr=0;
// the i!=__ clauses are basic bounds checking
// the grid____==1 clauses are to check if a surrounding
//  cell is alive or dead
   if(i!=0&&j!=0&&grid[i-1][j-1]==1)
    surr++;
   if(i!=0&&grid[i-1][j]==1)
    surr++;
   if(i!=0&&j!=9&&grid[i-1][j+1]==1)
    surr++;
   if(j!=0&&grid[i][j-1]==1)
    surr++;
   if(j!=9&&grid[i][j+1]==1)
    surr++;
   if(i!=9&&j!=0&&grid[i+1][j-1]==1)
    surr++;
   if(i!=9&&grid[i+1][j]==1)
    surr++;
   if(i!=9&&j!=9&&grid[i+1][j+1]==1)
    surr++;
   grids[i][j]=surr;
// send the results to the corresponding cell on "grids"
  }
 }
}

void change(apmatrix <int> &grid, apmatrix <int> &grids)
{
// here's where the rules come into play
// you can change them depending on how you
//  want to run the game.
// Currently: if the current cell is alive
//  and there are less than two surrounding living
//  cells, the cell will die of starvation.
//  More than three and it will die of overcrowding

// If it's dead, and there are exactly 3 surrouding
//  living cells, the cell will gain life.

 for(int i=0; i<grid.numrows(); i++)
 {
  for(int j=0; j<grid.numcols(); j++)
  {
   if(grid[i][j]==1&&(grids[i][j]<2||grids[i][j]>3))
   {
    grid[i][j]=0;
   }
   else if(grid[i][j]==0&&grids[i][j]==3)
    grid[i][j]=1;
  }
 }
}

void dispgrid(apmatrix <int> grid)
{
// just neato formatting.
// Change it to please you.

 cout << "\n   0123456789\n";
 cout << "   __________\n";
 for(int i=0; i<grid.numrows(); i++)
 {
  cout << i << " |";
  for(int j=0; j<grid.numcols(); j++)
  {
   if(grid[i][j]==0)
    cout << ".";
   if(grid[i][j]==1)
    cout << "x";
   //InfoDisplay:cout << grid[i][j] << grids[i][j];
  }
  cout << "|\n";
 }
 cout << "   ----------\n";
}
Conway's Game of Life as a Turing Machine:

An amazing aspect of a game of life grid is that you can implement Turing Machines using these simple rules. And people have actually done it! To see how this can be done, first we must know that there are certain patterns that, if put in a game of life grid, will repeat themselves. A pattern that moves across the grid in a predictable course is called a glider. These gliders can also interfere with each other destructively. So one can program gliders so that when they hit another glider, both disappear.

These gliders can be generated by glider guns. A glider gun is simply a pattern that , while following the rules to the game of life, spawns a glider off of itself in a set path every so often. So, for instance, say we have a glider gun in a game of life grid that shoots a glider off every second (think clock tick). We could implement a not gate very easily. If we shoot another glider into the path of the not gate, it will be destroyed, and no gliders will emerge. However, if no glider interferes, a glider will emerge unharmed. This is the principle of a not gate. Now it is trivial to implement an and gate, an or gate, etc. These are the building blocks of a modern Von Neumann architecture.

Memory cells can be modeled using a series of glider guns as well, and they can be queried, or stream their output. It always amazes me when people go back to the primordial building blocks of modern computers, and I think that it is extremely educational to look at cases like this.


Thanks go to Damian Conway for his excellent talk on Life, the Universe, and Everything, but all misunderstandings/inaccuracies are my fault. For an example of someone actually doing this, see http://rendell.uk.co/gol/tm.htm
There's a complete and very good Java implementation at

http://www.math.com/students/wonders/life/life.html

complete with a decent history of the topic, and gallery of some of the more famous discoveries.
There's patterns with all kinds of crazy properties - There's even a pattern that determines if a number is prime or not. The mind boggles (at least mine does) at all this complexity from squat in terms of input. Life begins to seem a very apt name indeed.

Those with math-ish minds beware! I have just wasted a whole afternoon playing around with this thing. All those morphing patterns - it's kind of mentally addictive!.


Incidentally, it always struck me that some of the things this system generates, like infinite growth, seem to disobey the second law of thermodynamics. Maybe someone could enlighten me?

Update: Several people have messaged me on this, so I think I now have my answer. Basically, the laws of the game are a bit too arbitrary for the second law to necessarily apply (which is, after all, essentially only an observational law about the real world. It need not to apply to some imagined system)
Txikwa points out that if we assume that changing the state of a cell requires some energy, then we can't have infinite growth without infinite energy input, just like the real world.
Also, as tdent points out, for most sensible definitions of entropy, an initial condition consisting of a few cells has very low entropy, and infinite growth means infinitely larger entropy.
Anyway, we are now far from the main subject of this node, so I will leave it at that.

Welcome, contestants, to the Universal Machine Contest!

Your purpose, as I'm sure you know from the pre-briefing notes that were handed out, is to build a machine. However, this is no ordinary contest, and these will be no ordinary machines.

The prize? I'm afraid I'm not allowed to divulge that information. The purpose of the machines? I can't tell you that either, although you're more than welcome to guess.

You will each be given a workshop, sealed off from the rest of the contestants. Each workshop contains a small mountain of references in a digital format. We've been kind and given you a few technical manuals, but most of the material relates only to the external appearance and functionality of previous machines - not all of which may have been completed or even existed.

You will also be given access to our parts warehouse, which contains several million different components. Some of them are new, but most of them are spare parts designed for previous machines - or the disassembled remnants of such. As such, none of them are labelled, and many that look okay on the first inspection may conceal a fatal flaw deep inside. Others which look obsolete and worn-out may serve as an anchor to hold your entire machine together.

We don't like to dictate what your machine must or must not contain, but as a hint, the input/output and encryption/decryption subsystems may come in very handy, since they'll allow you access to the references. Of course, you can get by without them, but it'll be a long, difficult journey, and whether or not you believe there'll be an additional reward for doing it "blind", as it were, is entirely up to you. Implementing a network interface will allow you to communicate with other machines, although bandwidth is very limited due to our large number of contestants and the aging network. It's needed an overhaul for a long time, but as of yet nobody has managed to come up with a machine capable of the task, although we've had some worthy contenders.

You will be given a "black box" power supply to start you off. Activation of said power supply will be your very first task, and its deactivation - whether your fault or not - will cause you to forfeit your place in the contest. Deactivation can be caused by four things.

First, a major malfunction in your machine may cause enough backlash to overload and destroy your supply. Ideally, this should never happen - but it's fairly common in the case of particularly badly-built machines, or those using faulty parts.

Secondly, interference - either accidental or intentional - from another machine can cause shutdown. It's nasty, but it does happen.

Thirdly, every five minutes we select a random contestant from our database of several billion current contestants. They are removed from the Contest and taken to the next level. Which, of course, I can't tell you about.

And fourthly, your power supply has a limited lifetime built into it, randomly selected upon activation - anything from one day to over a hundred years. Once this time is up, the next level awaits.

Part of the beauty of this contest is that we give you no tools to start off with, apart from the power supply. Your machine will become your tool, as well as your source of reference and your overall purpose. The first components you add will be building blocks which will allow you to add more sophisticated components, which in turn will allow you to add yet more, or even to construct your own. You'll probably find that you end up doing a lot of work on the fly, as opposed to stripping entire subsystems out for rebuilding. Just watch out - although some pieces may slot in easily and immediately mesh with the rest of the system, there are others which may cause things to seize up or break or, more insiduously, slowly damage and corrupt other components, requiring extensive repair later on.

Of course, this wouldn't be the Universal Machine Contest without the Challenges. Every so often, depending on your performance in previous Challenges, your machine will be entered into a series of improbable and extreme situations, often joining with or competing against other machines. You may get the chance to help repair a badly damaged machine or have your own machine repaired by another. You may be tasked to keep your machine running under an onslaught of attacks from others. You might have the opportunity to set up temporary or permanent networks with other machines, to compare and contrast the inner workings of other projects. You may have networks that you set up in previous Challenges disrupted or subverted. Every Challenge is different.

Passing a Challenge entitles you to a reward, which may range from a whole new subsystem... to nothing at all. You will have the chance to modify your machine on the fly during each Challenge, repairing damage, or occasionally picking up discarded parts from other machines and making them part of yours.

In the end, every machine is unique. No machine undergoes the same set of Challenges as any other, and even those which look identical at a quick glance are usually radically different inside. You'll end up with something that any sane designer would flee in terror from, an assemblage of odd parts tied together with duct tape and hope that somehow works despite all the odds. Maybe you'll be proud of your creation. Maybe you'll hate the sight of it by the time your spell in Stage One ends. Regardless, I'm sure you'll find the Contest to be the experience of a lifetime.

And now, without further ado... I bid you luck. You may begin.


Inspired by a couple of pages of night-time scribble found in an old, forgotten notebook.

Closed-captioned for the Metaphorically Impaired (clumsily)

Log in or registerto write something here or to contact authors.