A large pattern in the Game of Life, known as a 'breeder,' the first discovered to exhibit quadratic growth. Colors for emphasis. Source.
The Game of Life is a "zero-player game," because although its rules of behavior are somewhat board-game-like, it doesn't require input other than an initial configuration. Life exists on an infinite square grid of square cells, each of which can be "alive" or "dead." Some initial position is given, wherein all but a finite amount of cells are dead. At each "generation," every dead cell which has exactly three alive neighbors (orthogonal or diagonal) becomes alive, and every live cell which has less than two or more than three live neighbors dies; all other cells retain their current state. Though these rules are simple, interesting behavior emerges even in small patterns.
From left to right, these are the "beehive," "block," "blinker," and "glider" patterns, which are some of the most common that arise in the evolution of larger patterns. The first two are "still lives:" no new cells are born or die in their vicinity unless something else interacts with them. The blinker is a period-two oscillator, in that it returns to its original appearance after two generations. The glider is a "spaceship" with period 4 and speed c/4: it returns to its original appearance, translated by one cell diagonally, after 4 generations. c is the "speed of light," one cell per generation, which is the maximum speed any information can move in Life: no cell can affect the birth or death of any cell outside a one cell radius from it. As it turns out, free-standing spaceships can move no faster than c/2, although signals can propagate at the speed of light within larger patterns.
Although the fact that a new cell needs three live neighbors to be born limits the amount that patterns can explode outward, shortly after Life's creation, patterns began to be discovered which nevertheless exhibited infinite growth. The most famous of these is the "glider gun:"
The two patterns moving back and forth within the gun are known as "queen bees," which on their own would move forward, create a beehive, turn around, create another beehive, then turn back around and self-destructively interact with the first beehive. However, the placement of the blocks causes the outer beehives to be deleted as they're formed, and the relative positions and timings of the queen bees results in the inner beehives reacting to form a glider. Other such "guns" exist, both for gliders and larger spaceships, some of which move as they produce these spaceships. The "breeder" which is shown in the first image in this post is a very large arrangement of "rakes," or spaceship-producing spaceships, whose glider outputs all converge and interact in a carefully-designed manner to produce glider guns, that then start to shoot out gliders into space. This was one of the first patterns discovered which exhibits quadratic growth in the number of live cells.
Despite the simplicity of these patterns, the way they can interact to form new patterns and change their own behavior allows for the creation of very large, very powerful devices. In fact, the Game of Life is Turing-complete: using large enough patterns and enough time, Life can simulate anything any computer can do. Moreover, although not every pattern is the successor of another pattern, universal constructors exist in Life, which are patterns that can, given some input, produce elsewhere in the infinite grid any other pattern which can be constructed by ramming gliders together. Although Conway was able to prove the existence of universal computers and universal constructors fairly soon after inventing Life, it wasn't until very recently that they were actually built, and they comprise thousands of live cells within bounding boxes containing millions.
There are many freely available programs that enthusiasts can use to simulate Life and examine the behavior of patterns. These include Golly and MCell, and are pretty fun to fiddle about with in one's free time, be it for aesthetic or experimentation purposes!
Despite the simplicity of these patterns, the way they can interact to form new patterns and change their own behavior allows for the creation of very large, very powerful devices. In fact, the Game of Life is Turing-complete: using large enough patterns and enough time, Life can simulate anything any computer can do. Moreover, although not every pattern is the successor of another pattern, universal constructors exist in Life, which are patterns that can, given some input, produce elsewhere in the infinite grid any other pattern which can be constructed by ramming gliders together. Although Conway was able to prove the existence of universal computers and universal constructors fairly soon after inventing Life, it wasn't until very recently that they were actually built, and they comprise thousands of live cells within bounding boxes containing millions.
There are many freely available programs that enthusiasts can use to simulate Life and examine the behavior of patterns. These include Golly and MCell, and are pretty fun to fiddle about with in one's free time, be it for aesthetic or experimentation purposes!
No comments:
Post a Comment