2D cellular automaton similar to Conway's Game of Life
Life without Death pattern that creates three ladders and shows the death of two ladders by colliding with a single cell (two different ways), the turning of a ladder and the death of a ladder by colliding with another ladder.The number of live cells per generation of the pattern shown above demonstrating the monotonic nature of Life without Death.
Life without Death is a cellular automaton, similar to Conway's Game of Life and other Life-like cellular automaton 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 Toffoli & Margolus (1987), who called it "Inkspot";[1] it has also been called "Flakes".[2] 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.
A cellular automaton is a type of model studied in mathematics 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 pixels, 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.[3]
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 3 live neighbors becomes alive itself, and every other dead cell remains dead. That is, in the notation describing Life-like cellular automaton rules, it is rule B3/S012345678: a live cell is born when there are 3 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 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.
An example of a fast parasitic shoot running alongside a slower ladder. When the tips of the shoot and of the ladder meet they are both destroyed creating a chaotic mess and sending two shoots back down the original ladder in the opposite direction.
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.[4] 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.[5] Another common pattern (called a "parasitic shoot" by Gravner and Griffeath[4]) advances twice as quickly, at speed 2c/3, along the side of a ladder, eventually blocking the ladder and causing a chaotic explosion.[4][6]
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.[7]
Simulation of circuits
The ladders in Life without Death can be used to simulate arbitrary Boolean circuits:[6] 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 "not" gates of Boolean logic, as well as the points where two signals cross each other. Therefore, it is P-complete to simulate patterns in the Life without Death rule, meaning it is unlikely that a parallel algorithm 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.[6]
Infinite growth
Seed patterns in the form of balls of radius up to ten typically lead to a still life pattern;[4] however, Gravner[8] 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.[4][6] 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.[7]
1 2 3 4 5 Gravner, Janko; David, Griffeath (1998), "Cellular Automaton Growth on Z2: Theorems, Examples, and Problems", Advances in Applied Mathematics, 21: 241–304, doi:10.1006/aama.1998.0599.
↑ The notation c is used, and c is called the speed of light, because it is the fastest speed at which information can propagate across a cellular automaton that uses the Moore neighborhood.
↑ Gravner, Janko (2003), "Growth phenomena in cellular automata", New Constructions in Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, pp.161–182, archived from the original on 2010-06-26
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.
A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.
Langton's ant is a two-dimensional universal Turing machine with a very simple set of rules but complex emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000. The idea has been generalized in several different ways, such as turmites which add more colors and more states.
Highlife is a cellular automaton similar to Conway's Game of Life. It was devised in 1994 by Nathan Thompson. It is a two-dimensional, two-state cellular automaton in the "Life family" and is described by the rule B36/S23; that is, a cell is born if it has 3 or 6 neighbors and survives if it has 2 or 3 neighbors. Because the rules of HighLife and Conway's Life are similar, many simple patterns in Conway's Life function identically in HighLife. More complicated engineered patterns for one rule, though, typically do not work in the other rule.
A cellular automaton (CA) is Life-like if it meets the following criteria:
Seeds is a cellular automaton in the same family as the Game of Life, initially investigated by Brian Silverman and named by Mirek Wójtowicz. It consists of an infinite two-dimensional grid of cells, each of which may be in one of two states: on or off. Each cell is considered to have eight neighbors, as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin where the state of a cell at time t depends not only on its neighborhood at time t − 1, but also on its state at time t − 2.
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
Rule 30 is an elementary cellular automaton introduced by Stephen Wolfram in 1983. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour.
A cyclic cellular automaton is a kind of cellular automaton rule developed by David Griffeath and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a modular value exactly one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior.
A rake, in the lexicon of cellular automata, is a type of puffer train, which is an automaton that leaves behind a trail of debris. In the case of a rake, however, the debris left behind is a stream of spaceships, which are automata that "travel" by looping through a short series of iterations and end up in a new location after each cycle returns to the original configuration.
Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells. In contrast, an asynchronous cellular automaton is able to update individual cells independently, in such a way that the new state of a cell affects the calculation of states in neighbouring cells.
In mathematics, a function or sequence is said to exhibit quadratic growth when its values are proportional to the square of the function argument or sequence position. "Quadratic growth" often means more generally "quadratic growth in the limit", as the argument or sequence position goes to infinity – in big Theta notation, . This can be defined both continuously or discretely.
In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.
In Conway's Game of Life and similar cellular automaton rules, a spark is a small collection of live cells that appears at the edge of some larger pattern such as a spaceship or oscillator, then quickly dies off.
Brian's Brain is a cellular automaton devised by Brian Silverman, which is very similar to his Seeds rule.
In a cellular automaton, a finite pattern is called a sawtooth if its population grows without bound but does not tend to infinity. In other words, a sawtooth is a pattern with population that reaches new heights infinitely often, but also infinitely often drops below some fixed value. Their name comes from the fact that their plot of population versus generation number looks roughly like an ever-increasing sawtooth wave.
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.
Critters is a reversible block cellular automaton with similar dynamics to Conway's Game of Life, first described by Tommaso Toffoli and Norman Margolus in 1987.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
