Wednesday, October 07, 2015

Game of Life

Game of Life

John Horton Conway John Horton Conway at Princeton University in 2009. is is a British mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He has also contributed to many branches of recreational mathematics, notably the invention of the cellular automaton called the Game of Life.


Conway was interested in a problem presented in the 1940s by mathematician John von Neumann, who attempted to find a hypothetical machine that could build copies of itself and succeeded when he found a mathematical model for such a machine with very complicated rules on a rectangular grid.

The Game of Life emerged as Conway's successful attempt to drastically simplify von Neumann's ideas. The game made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column.

From a theoretical point of view, it is interesting because it has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life.[2][3] Gardner wrote:
The game made Conway instantly famous, but it also opened up a whole new field of mathematical research, the field of cellular automata ... Because of Life's analogies with the rise, fall and alterations of a society of living organisms, it belongs to a growing class of what are called "simulation games" (games that resemble real life processes).
The earliest interesting patterns in the Game of Life were discovered without the use of computers. The simplest static patterns ("still lifes") and repeating patterns ("oscillators"—a superset of still lifes) were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, physical game boards (such as Go) and the like.

During this early research, Conway discovered that the R-pentomino     failed to stabilize in a small number of generations. In fact, it takes 1103 generations to stabilize, by which time it has a population of 116 and has fired six escaping glidersGame of life animated glider.gif   (these were the first gliders ever discovered)

Many different types of patterns occur in the Game of Life, including
  1. still lifes  (block Game of life block with border.svg, ,
     
  2. oscillators (period 2 beaconGame of life beacon.gif , period 3 pulsar Game of life pulsar.gif,  period 15 pentadecathlon   I-Column.gif ) and 
  3. patterns that translate themselves across the board   called "spaceships" (glider Game of life animated glider.gif,  lightweight spaceship Game of life animated LWSS.gif ). 
 Conway originally conjectured that no pattern can grow indefinitely—i.e., that for any initial configuration with a finite number of living cells, the population cannot grow beyond some finite upper limit. In the game's original appearance in "Mathematical Games", Conway offered a $50 prize to the first person who could prove or disprove the conjecture before the end of 1970.

The prize was won in November of the same year by a team from the Massachusetts Institute of Technology, led by Bill Gosper; the "Gosper glider gun" Gosper_glider_gun_with_grid
  produces its first glider on the 15th generation, and another glider every 30th generation from then on. For many years this glider gun was the smallest one known.[19]

However, on April 28, 2015, Michael Simkin found a 36 cells  Simkin glider gun  http://www.conwaylife.com/w/images/c/cf/Simkinglidergun.gif 
as the smallest glider gun ever found. 


No comments:

Post a Comment