Life without Death is a cellular automaton

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

, similar to Conway's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

 and other Life-like cellular automaton

Life-like cellular automaton

A cellular automaton is Life-like if it meets the following criteria:* The array of cells of the automaton has two dimensions....

 rules. In this cellular automaton, an initial seed pattern grows according to the same rule as in Conway's Game of Life; however, unlike Life, patterns never shrink. The rule was originally considered by , who called it "Inkspot"; it has also been called "Flakes". In contrast to the more complex patterns that exist within Conway's Game of Life, Life without Death commonly features still life patterns, in which no change occurs, and ladder patterns, that grow in a straight line.

Rules

A cellular automaton is a type of model studied in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and theoretical biology consisting of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off". A pattern in the Life without Death cellular automaton consists of an infinite two-dimensional grid of cells, each of which can be in one of two states: dead or alive. Equivalently, it can be thought of as an array of pixel

Pixel

In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....

s, each of which may be black and white; in the figures, the white pixels represent live cells while the black pixels represent dead cells. Two of these cells are considered to be neighbors if they are vertically, horizontally, or diagonally adjacent.

Any such pattern changes over a sequence of time steps by applying the following simple rules simultaneously to all cells of the pattern: every cell that was alive in the previous pattern remains alive, every dead cell that has exactly three live neighbors becomes alive itself, and every other dead cell remains dead. That is, in the notation describing Life-like cellular automaton

Life-like cellular automaton

A cellular automaton is Life-like if it meets the following criteria:* The array of cells of the automaton has two dimensions....

 rules, it is rule B3/S012345678: a live cell is born when there are three live neighbors, and a live cell survives with any number of neighbors.

Shoots and ladders

Still life patterns are common in Life without Death: if there is no dead cell with three live neighbors, a pattern will remain unchanging for all future time steps. However, because a cell, once alive, remains alive, the set of live cells grows monotonically

Monotonic function

In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

 throughout the evolution of a pattern, and there can be no oscillators (patterns that cycle through a repeating sequence of shapes), spaceships (patterns that keep the same shape but change position), or the other more complex patterns that exist within Conway's Game of Life.

Instead, a common feature in Life without Death patterns is the presence of ladders, patterns that grow in a straight line. A ladder will grow forever unless it runs into some other part of the pattern and is blocked or unless some more quickly-growing pattern overtakes it. The most common ladder pattern is shown in the figure; every twelve steps, the same shape appears at the tip of the ladder, four cells farther from the starting position of the ladder. The speed of the ladder's growth is therefore four cells per twelve steps, or, in Life notation, 4c/12 = c/3; here c represents one unit of distance per time step. Another common pattern (called a "parasitic shoot" by Gravner and Griffeath) advances twice as quickly, at speed 2c/3, along the side of a ladder, eventually blocking the ladder and causing a chaotic explosion.

Variant ladders of other speeds were discovered in 2000 by Dean Hickerson, along with some parasitic shoots that are slower than the most common 2c/3 one. Hickerson's ladders grow at speeds 4c/9, 4c/10, and 4c/13.

Simulation of circuits

The ladders in Life without Death can be used to simulate arbitrary Boolean circuit

Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...

s: the presence or absence of a ladder in a certain position may be used to represent a Boolean signal, and different interactions between pairs of ladders, or between ladders and still life patterns, may be used to simulate the 'and', 'or', and 'negation' gates of Boolean logic, as well as the points where two signals cross each other. Therefore, it is P-complete

P-complete

In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:# which problems are difficult to parallelize effectively, and;# which problems are difficult to solve in limited space....

 to simulate patterns in the Life without Death rule, meaning it is unlikely that a parallel algorithm

Parallel algorithm

In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...

 exists for a simulation significantly faster than that obtained by a naive parallel algorithm with one processor per cellular automaton cell and one time step per generation of the pattern.

Infinite growth

Seed patterns in the form of balls of radius up to ten typically lead to a still life pattern; however, Gravner suggests that the rule is supercritical, meaning that larger or less-symmetric seeds typically expand forever chaotically. Ladders are a frequent phenomenon on the boundaries of chaotic growth regions.

A pattern in Life without Death is said to fill the plane with positive density if there is some radius r such that every cell of the plane is eventually within distance r of a live cell. The question of whether such infinite growth patterns exist was posed as an open problem by Gravner, Griffeath, and Moore. The chaotic patterns common in this rule may fill the plane, but they may also leave large empty rectangular regions framed by ladders, causing them to fail the density condition. However, in 2009 Dean Hickerson found diagonally-expanding patterns that eventually settle down into high-period infinite growth, solving the open problem.

External links

• A Way-Cool CyberFlake and Life Without Death (Revisited), from the Primordial Soup Kitchen cellular automaton web site.
• Life without death on LifeWiki.