Highlife (cellular automaton)

Last updated
The evolution of the replicator Highlife replicator.gif
The evolution of the replicator

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 (rule B3/S23) 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.

Cellular automaton A discrete model studied in computer science, mathematics, physics, complexity science, theoretical biology and microstructure modeling

A cellular automaton is a discrete model studied in computer science, mathematics, physics, complexity science, theoretical biology and microstructure modeling. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays.

<i>Conways Game of Life</i> 2D cellular automaton devised by J. H. Conway in 1970

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

A cellular automaton (CA) is Life-like if it meets the following criteria:

Contents

Replicator

The replicator Highlife replicator.png
The replicator

The main reason for interest in HighLife comes from the existence of a pattern called the replicator. After running the replicator for twelve generations, the result is two replicators. The replicators will repeatedly reproduce themselves, all on a diagonal line. Whenever two replicators try to expand into each other, the pattern in the middle simply vanishes. The behavior of a row of Replicators interacting with each other in this way simulates the one-dimensional Rule 90 cellular automaton, where a single replicator simulates a nonzero cell of the Rule 90 automaton and a blank space where a replicator could be simulates a zero cell of Rule 90. [1] Replicators can be used to engineer other more complex patterns, such as glider guns and high period oscillators.

Replicator (cellular automaton) Type of pattern that infinitely produces copies of itself

In cellular automata, a replicator is a pattern that produces copies of itself.

Rule 90 elementary cellular automaton

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.

A simple c/6 diagonal spaceship, found by Nathan Thompson, is known as the bomber. This pattern consists of a replicator and a blinker; after replicating itself into two replicators, one of the two new replicators reacts with the blinker to "pull" it forward to match the new position of the other new replicator. In this way, the whole pattern repeats with period 48. It is also possible to make slower spaceships of much larger size that consist of a sequence of replicators between two ends composed of oscillators or still lifes, with the pattern of the replicators carefully chosen so that they interact with the ends of the pattern in such a way as to push the front end and pull the back end at the same speed. Explicit examples of this design, known as "basilisks", include spaceships of speeds (one cell every 24 generations), , , and . A basilisk gun has also been constructed. [2]

Spaceship (cellular automaton) Type of pattern that periodically changes position

In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position. The smallest such number of generations is called the period of the spaceship.

Gun (cellular automaton) Type of stationary pattern that periodically produces spaceships

In a cellular automaton, a gun is a pattern with a main part that repeats periodically, like an oscillator, and that also periodically emits spaceships. There are then two periods that may be considered: the period of the spaceship output, and the period of the gun itself, which is necessarily a multiple of the spaceship output's period. A gun whose period is larger than the period of the output is a pseudoperiod gun.

It had been proven that replicators exist in Conway's Life as well, before an explicit example was found in 2013.

Related Research Articles

In a cellular automaton, an oscillator is a pattern that returns to its original state, in the same orientation and position, after a finite number of generations. Thus the evolution of such a pattern repeats itself indefinitely. Depending on context, the term may also include spaceships as well.

Seeds (cellular automaton) 2D cellular automaton similar to Conways Game of Life

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 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.

Day and Night (cellular automaton) 2D cellular automaton with black/white reversal symmetry

Day and Night is a cellular automaton rule in the same family as Game of Life. It is defined by rule notation B3678/S34678, meaning that a dead cell becomes live if it has 3, 6, 7, or 8 live neighbors, and a live cell remains alive (survives) if it has 3, 4, 6, 7, or 8 live neighbors, out of the eight neighbors in the Moore neighborhood. It was invented and named by Nathan Thompson in 1997, and investigated extensively by David I. Bell. The rule is given the name "Day & Night" because its on and off states are symmetric: if all the cells in the Universe are inverted, the future states are the inversions of the future states of the original pattern. A pattern in which the entire universe consists of off cells except for finitely many on cells can equivalently be represented by a pattern in which the whole universe is covered in on cells except for finitely many off cells in congruent locations.

Garden of Eden (cellular automaton) Type of pattern that has no predecessors

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.

Block cellular automaton type of cellular automata

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 Elementary cellular automaton

Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour.

Rake (cellular automaton) Type of moving pattern which periodically produces spaceships

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.

Spark (cellular automaton) Type of pattern which temporarily appears at the edge of a larger pattern

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.

Brians Brain 2D cellular automaton devised by Brian Silverman

Brian's Brain is a cellular automaton devised by Brian Silverman, which is very similar to his Seeds rule.

Sawtooth (cellular automaton) Type of pattern whose population grows without bound but does not tend to infinity

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.

Life without Death 2D cellular automaton similar to Conways Game of Life

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"; 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.

Reversible cellular automaton type of cellular automata

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 (block cellular automaton) cellular automaton

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.

References

  1. Griffeath, David (1996), "Recipe for the week of July 1–7: Replicating Skeeters", The Primordial Soup Kitchen .
  2. Goucher, Adam P. (January 19, 2013), "New HighLife velocities", Game of Life News