Life Lexicon (U)

Introduction | Bibliography

1-9 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

: UC = universal constructor.

: underpopulation Death of a cell caused by it having fewer than two neighbors. See also overpopulation.

: unit cell = unit Life cell.

: unit Life cell A rectangular pattern, of size greater than 1x1, that can simulate Life in the following sense. The pattern by itself represents a dead Life cell, and some other pattern represents a live Life cell. When the plane is tiled by these two patterns (which then represent the state of a whole Life universe) they evolve, after a fixed amount of time, into another tiling of the plane by the same two patterns which correctly represents the Life generation following the one they initially represented.

It is usual to use the prefix "meta-" for simulated Life features, so, for example, for the first known unit Life cell (constructed by David Bell in January 1996), one metatick is 5760 ticks, and one metacell is 500x500 cells. Capital letters were originally used to make this distinction - e.g., Generation, Cell - but this usage is no longer common.

In December 2005, Jason Summers constructed an analogous unit cell for Wolfram's Rule 110, a one-dimensional cellular automaton that is known be universal. See also OTCA metapixel, p1 megacell.

: universal See universal computer, universal constructor, universal toolkit.

: universal computer A computer that can compute anything that is computable. (The concept of computability can be defined in terms of Turing machines, or by Church's lambda calculus, or by a number of other methods, all of which can be shown to lead to equivalent definitions.) The relevance of this to Life is that both Bill Gosper and John Conway proved early on that it is possible to construct a universal computer in the Life universe. (To prove the universality of a cellular automaton with simple rules was in fact Conway's aim in Life right from the start.) Conway's proof is outlined in Winning Ways, and also in The Recursive Universe.

Until recently, no universal Life computer had ever been built in practice In April 2000, Paul Rendell completed a Turing machine construction (see http://rendell-attic.org/gol/tm.htm for details). This, however, has a finite tape, as opposed to the infinite tape of a true Turing machine, and is therefore not a universal computer. But in November 2002, Paul Chapman announced the construction of a universal computer, see http://www.igblan.free-online.co.uk/igblan/ca/. This is a universal register machine based around Dean Hickerson's sliding block memory.

In 2009 Adam P. Goucher constructed a programmable Spartan universal computer/constructor pattern using stable Herschel circuitry. It included memory tapes and registers capable of holding a simple universal instruction set and program data, and also a minimal single-arm universal constructor. Its size meant that it was extremely impractical to program it to be self-constructing, though this was theoretically possible if the escape of large numbers of gliders could be allowed as a side effect.

In February 2010, Paul Rendell completed a universal Turing machine design with an unlimited tape, as described in his thesis at http://eprints.uwe.ac.uk/22323/1/thesis.pdf.

In 2016 Nicolas Loizeau ("Coban") completed a Life pattern emulating a complete 8-bit programmable computer.

See also universal constructor.

: universal constructor A pattern that is capable of constructing almost any pattern that has a glider synthesis. This definition is a bit vague. A precise definition seems impossible because it is not known, for example, whether all still lifes are constructible. In any case, a universal constructor ought to be able to construct itself in order to qualify as such.

An outline of Conway's proof that such a pattern exists can be found in Winning Ways, and also in The Recursive Universe. The key mechanism for the production of gliders with any given path and timing is known as side-tracking, and is based on the kickback reaction. A universal constructor designed in this way can also function as a universal destructor: it can delete almost any pattern that can be deleted by gliders.

In May 2004, Paul Chapman and Dave Greene produced a prototype programmable universal constructor. This is able to construct objects by means of slow glider constructions. It likely that it could be programmed to construct itself, but the necessary program would be very large; moreover an additional mechanism would be needed in order to copy the program.

A universal constructor is theoretically most useful when attached to a universal computer, which can be programmed to control the constructor to produce the desired pattern of gliders. In what follows I will assume that a universal constructor always includes this computer.

The existence of a universal constructor/destructor has a number of theoretical consequences.

For example, the constructor could be programmed to make copies of itself. This is a replicator.

The constructor could even be programmed to make just one copy of itself translated by a certain amount and then delete itself. This would be a (very large, very high period) spaceship. Any translation is possible, so that the spaceship could travel in any direction. If the constructor makes a rotated but unreflected copy of itself, the result would be a looping spaceship or reflectorless rotating oscillator.

The constructor could also travel slower than any given speed, since we could program it to perform some time-wasting task (such as repeatedly constructing and deleting a block) before copying itself. Of course, we could also choose for it to leave some debris behind, thus making a puffer.

It is also possible to show that the existence of a universal constructor implies the existence of a stable reflector. This proof is not so easy, however, and is no longer of much significance now that explicit examples of such reflectors are known.

Progressively smaller universal-constructor mechanisms without an attached universal computer have been used in the linear propagator, spiral growth pattern, and the Demonoids and Orthogonoid. See also single-channel.

Another strange consequence of the existence of universal constructors was pointed out by Adam P. Goucher and Tanner Jacobi in 2015. Any glider-constructible pattern, no matter how large, can be constructed with a fixed number of gliders, by working out a construction recipe for a universal constructor attached to a decoder that measures the distance to a faraway object. The object's position encodes a numeric value that can be processed to retrieve as many bits of information as are needed to build a slow salvo to construct any given target pattern. The simplest design, requiring less than a hundred gliders, is described in reverse caber tosser.

: universal destructor See universal constructor.

: universal register machine = URM

: universal regulator A regulator in which the incoming gliders are aligned to period 1, that is, they have arbitrary timing (subject to some minimum time required for the regulator to recover from the previous glider).

Paul Chapman constructed the first universal regulator in March 2003. It is adjustable, so that the output can be aligned to any desired period. A stable universal regulator was constructed by Dave Greene in September 2015, with a minimum delay between test signals of 1177 ticks. Later stable versions have reduced the delay to 952 ticks.

A universal regulator can allow two complex circuits to interact safely, even if they have different base periods. For example, signals from a stable logic circuit could be processed by a period-30 mechanism, though the precise timing of those signals would change in most cases.

: universal toolkit A set of Life reactions and mechanisms that can be used to construct any object that can be constructed by glider collisions. Different universal toolkits were used to construct the linear propagator, 10hd Demonoid, 0hd Demonoid, and Orthogonoid, for example.

: universe The topology of the cells in the Life grid. In the normal universe (the usual Life arena), the grid is infinite in both directions. In a cylindrical universe, the grid is finite in one direction, and the cells at the two edges are adjacent to each other. In a torus universe, the grid is finite in both directions, and the cells at the top and bottom edges are adjacent, and the cells at the left and right edges are adjacent. There are several other more obscure types of universe.

Objects found in the cylindrical and toroidal universes can also run in the normal universe if an infinite number of copies are arranged to support each other. Sometimes the objects can be supported in other ways to make a useful finite object. This is one reason that soup searches are run in alternative universes, to find such objects.

: unix (p6) Two blocks eating a long barge. This is a useful sparker, found by Dave Buckingham in February 1976. The name derives from the fact that it was for some time the mascot of the Unix lab of the mathematics faculty at the University of Waterloo.

    .OO.....
    .OO.....
    ........
    .O......
    O.O.....
    O..O..OO
    ....O.OO
    ..OO....

: unknown fate An object whose fate is in some way unanswerable with our current knowledge. The simplest way that the fate of an object can be unknown involves the question of whether or not it exhibits infinite growth. For example, the fate of the Fermat prime calculator is currently unknown, but its behavior is otherwise predictable.

A different type of unknown fate is that of the Collatz 5N+1 simulator, which may become stable, or an oscillator, or have an indefinitely growing bounding box. Its behavior is otherwise predictable, and unlike the Fermat prime calculator the population is known to be bounded.

Life objects having even worse behavior (e.g. chaotic growth) are not known as of July 2018.

: up boat with tail = trans-boat with tail

: U-pentomino Conway's name for the following pentomino, which rapidly dies.

    O.O
    OOO

: URM A universal register machine, particularly Paul Chapman's Life implementation of such a machine. See universal computer for more information.

1-9 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z