Life Lexicon (D)

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

: dart (c/3 orthogonally, p3) Found by David Bell, May 1992. A 25-glider recipe for the dart was found in December 2014 by Martin Grant and Chris Cain, making it the first glider-constructible c/3 spaceship.

    .......O.......
    ......O.O......
    .....O...O.....
    ......OOO......
    ...............
    ....OO...OO....
    ..O...O.O...O..
    .OO...O.O...OO.
    O.....O.O.....O
    .O.OO.O.O.OO.O.

: dead spark coil (p1) Compare spark coil.

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

: debris = ash.

: de Bruijn diagram = de Bruijn graph

: de Bruijn graph As applied to Life, a de Bruijn graph is a graph showing which pieces can be linked to which other pieces to form a valid part of a Life pattern of a particular kind.

For example, if we are interested in still lifes, then we could consider 2x3 rectangular pieces and the de Bruijn graph would show which pairs of these can be overlapped to form 3x3 squares in which the centre cell remains unchanged in the next generation.

David Eppstein's search program gfind is based on de Bruijn graphs.

: Deep Cell A pattern by Jared James Prince, based on David Bell's unit Life cell, in which each unit cell simulates two Life cells, in such a way that a Life universe filled with Deep Cells simulates two independent Life universes running in parallel.

In fact, a Life universe filled with Deep Cells can simulate infinitely many Life universes, as follows. Let P1, P2, P3, ... be a sequence of Life patterns. Set the Deep Cells to run a simulation of P1 in parallel with a simulation of a universe filled with Deep Cells, with these simulated Deep Cells running a simulation of P2 in parallel with another simulation of a universe filled with Deep Cells, with these doubly simulated Deep Cells simulating P3 in parallel with yet another universe of Deep Cells, and so on.

Deep Cell is available from http://psychoticdeath.com/life.htm.

: Demonoid The first self-constructing diagonal spaceship. A 0hd Demonoid was completed by Chris Cain in December 2015, shortly after a much larger 10hd version was constructed the previous month in collaboration with Dave Greene. The 0hd spaceship fits in a bounding box about 55,000 cells square, and displaces itself by 65 cells diagonally every 438,852 generations.

The first 0hd Demonoid was fired by a gun. No spaceship gun pattern had previously been completed before the first appearance of the actual spaceship.

In June 2017 Dave Greene completed a much simpler single-channel Demonoid using a temporary lossless elbow, which displaces itself 79 cells diagonally every 1,183,842 ticks. This was an improvement in terms of design complexity, but not in terms of speed, population, or bounding box. However, all of these could be further optimized. A smaller Hashlife-friendly single-channel Demonoid design was completed in 2018.

: demultiplexer A simple Herschel circuit consisting of three eater1s, found by Brice Due in August 2006. An input Herschel places a boat in a location accessible to an input glider. If the boat is present, a one-time turner reaction occurs and the glider is turned 90 degrees onto a new lane.

    ...........................O.....
    ........OO.................O.O...
    .........O.................OO....
    .........O.O.....................
    ..........OO.....................
    .......................OO........
    .......................O.O.......
    ........................O........
    .................................
    .................................
    .............................OO..
    ..........O..................O.O.
    ..........O.O..................O.
    ..........OOO............OO....OO
    ............O............O.O.....
    ...........................O.....
    ...........................OO....
    .................................
    .................................
    ..OO.............................
    .O.O.............................
    .O...............................
    OO...............................

If the Herschel and boat are removed from the above pattern, the glider passes cleanly through the circuit. It can be used as the "0" output of a one-bit memory cell, where the 90-degree output would be the "1" output. This was the method used to store presence or absence of neighbor metacells in the p1 megacell.

: demuxer = demultiplexer

: density The density of a pattern is the limit of the proportion of live cells in a (2n+1)x(2n+1) square centred on a particular cell as n tends to infinity, when this limit exists. (Note that it does not make any difference what cell is chosen as the centre cell. Also note that if the pattern is finite then the density is zero.) There are other definitions of density, but this one will do here.

In 1994 Noam Elkies proved that the maximum density of a stable pattern is 1/2, which had been the conjectured value. See the paper listed in the bibliography. Marcus Moore provided a simpler proof in 1995, and in fact proves that a still life with an m x n bounding box has at most (mn+m+n)/2 cells.

But what is the maximum average density of an oscillating pattern? The answer is conjectured to be 1/2 again, but this remains unproved. The best upper bound so far obtained is 8/13 (Hartmut Holzwart, September 1992).

The maximum possible density for a phase of an oscillating pattern is also unknown. An example with a density of 3/4 is known (see agar), but densities arbitrarily close to 1 may perhaps be possible.

: dependent conduit A Herschel conduit in which the input Herschel interacts with catalysts in the first few ticks. The standard interaction actually starts at T=-3, before the Herschel is completely formed. Compare independent conduit. The Herschel is prevented from emitting its first natural glider. This is useful in cases where the previous conduit cannot survive a first natural glider emitted from its output Herschel.

This term is somewhat confusing, since it is actually the previous conduit that depends on the dependent conduit to suppress the problematic glider. Dependent conduits such as the F166 and Lx200 do not actually depend on anything. They can be freely connected to any other conduits that fit, as long as the output Herschel evolves from its standard great-grandparent. As of this writing, the Fx158 is the only known case where a conduit's output Herschel has an alternate great-grandparent, which is incompatible with dependent conduits' initial transparent block.

: destructive read The most common type of test reaction in memory cell circuitry. Information is stored in a memory cell by placing objects in known positions, or by changing the state of a stable or periodic toggle circuit. A destructive-read test consists of sending one or more signals to the memory cell. A distinct output signal is produced for each possible state of the memory cell, which is reset to a known "zero" or "rest" state. See for example boat-bit, keeper, and demultiplexer.

To permanently store information in a destructive-read memory cell, the output signal(s) must be used, in part, to send appropriate signals back to the memory cell to restore its state to its previous value. With output looped back to input, this larger composite circuit then effectively becomes a non-destructive read memory cell.

: destructor arm A dedicated construction arm in the Gemini spaceship, used only for removing previously active circuitry once it is no longer needed. More generally, any circuitry in a self-constructing pattern dedicated exclusively to cleanup.

: D-heptomino = Herschel

: diamond = tub

: diamond ring (p3) Found by Dave Buckingham in 1972.

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

: diehard Any pattern that vanishes, but only after a long time. The following example vanishes in 130 generations, which is probably the limit for patterns of 7 or fewer cells. Note that there is no limit for higher numbers of cells. E.g., for 8 cells we could have a glider heading towards an arbitrarily distant blinker.

    ......O.
    OO......
    .O...OOO

: dinner table (p12) Found by Robert Wainwright in 1972.

    .O...........
    .OOO.......OO
    ....O......O.
    ...OO....O.O.
    .........OO..
    .............
    .....OOO.....
    .....OOO.....
    ..OO.........
    .O.O....OO...
    .O......O....
    OO.......OOO.
    ...........O.

: dirty Opposite of clean. A reaction which produces a large amount of complicated junk which is difficult to control or use is said to be dirty. Many basic puffer engines are dirty and need to be tamed by accompanying spaceships in order to produce clean output. Similarly, a dirty conduit is one that does not recover perfectly after the passage of a signal; one or more extra ash objects are left behind (or more rarely a catalyst is damaged) and additional signals must be used to clean up the circuit before it can be re-used.

: diuresis (p90) Found by David Eppstein in October 1998. His original stabilization used pentadecathlons. The stabilization with complicated still lifes shown here (in two slightly different forms) was found by Dean Hickerson the following day. The name is due to Bill Gosper (see kidney).

    .....OO................OO....
    ......O................O.....
    ......O.O............O.O.....
    .......OO............OO......
    .............................
    ....OO..................OO...
    ....O.O..........OO....O.O...
    .....O..........O.O.....O....
    ..O.............OO.........O.
    ..OOOOOO........O.....OOOOOO.
    .......O..............O......
    ....OO..................OO...
    ....O....................O...
    .....O..................O....
    ..OOO..O..............O..OOO.
    ..O..OOO........O.....OOO...O
    ...O............OO.......OOO.
    ....OO..........O.O.....O....
    ......O..........OO....O..OO.
    ....OO..................OO.O.
    .O..O....................O...
    O.O.O..OO............OO..O...
    .O..O.O.O............O.O.OO..
    ....O.O................O..O..
    .....OO................OO....

: dock The following induction coil.

    .OOOO.
    O....O
    OO..OO

: domino The 2-cell polyomino. A number of objects, such as the HWSS and pentadecathlon, produce domino sparks.

: dormant An object that is either stable or oscillates without producing any output, until it is triggered by an appropriate signal, which then produces some desired action. For example, freeze-dried objects are dormant until the arrival of a particular glider.

: do-see-do The following reaction, found by David Bell in 1996, in which two gliders appear to circle around each other as they are reflected 90 degrees by a twin bees shuttle. Four copies of the reaction can be used to create a p92 glider loop which repeats the do-see-do reaction forever.

    .....................................................O.O
    .....................................................OO.
    ......................................................O.
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ........................................................
    ................................................OO......
    ................................................O.......
    ..............................................O.O.......
    ..............................................OO........
    ..............................O.O.......................
    ..............................OO........................
    ...............................O........................
    ........................................................
    .......................OOO..............................
    OO........OOO........OO.O.OO............................
    OO........O...O.....O.....OO............................
    ..........O....O.....OO.O.OO............................
    ...........O...O.......OOO..............................
    ........................................................
    ...........O...O........................................
    ..........O....O........................................
    OO........O...O............OO...........................
    OO........OOO..............OO...........................

: double-barrelled Of a gun, emitting two streams of spaceships (or rakes) every period. For examples, see B-52 bomber, Simkin glider gun, and p246 gun. In most cases, the two streams are alternately emitted 1/2 period apart. It is also possible for the two streams to be emitted simultaneously, as in this double-barrelled glider gun by Bill Gosper:

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

: double block reaction A certain reaction that can be used to stabilize the twin bees shuttle (qv). This was discovered by David Bell in October 1996.

The same reaction sometimes works in other situations, as shown in the following diagram where a pair of blocks eats an R-pentomino and a LWSS. (The LWSS version was known at least as early 1994, when Paul Callahan saw it form spontaneously as a result of firing an LWSS stream at some random junk.)

    .OOOO.....OO....
    O...O......OO.OO
    ....O......O..OO
    O..O............
    ................
    .............OO.
    .............OO.

: double caterer (p3) Found by Dean Hickerson, October 1989. Compare caterer and triple caterer.

    .....OO...O........
    ....O..O..OOO......
    ....OO.O.....O.....
    ......O.OOOO.O.....
    ..OOO.O.O...O.OO...
    .O..O..O...O..O.O..
    O.O..O...O.OO....O.
    .O..........OO.OOO.
    ..OO.OO.OO...O.....
    ...O...O.....O.OOO.
    ...O...O......OO..O
    .................OO

: double ewe (p3) Found by Robert Wainwright before September 1971.

    ......OO............
    .......O............
    ......O.............
    ......OO............
    .........OO.........
    ......OOO.O.........
    O.OO.O..............
    OO.O.O..............
    .....O...O..........
    ....O...OO....OO....
    ....OO....OO...O....
    ..........O...O.....
    ..............O.O.OO
    ..............O.OO.O
    .........O.OOO......
    .........OO.........
    ............OO......
    .............O......
    ............O.......
    ............OO......

: double wing = moose antlers. This term is no longer in use.

: dove The following induction coil, found in 2015 to be a possible active reaction for the input or output of a converter.

    .OO..
    O..O.
    .O..O
    ..OOO

: down boat with tail = cis-boat with tail

: dr Short identifier for Dean Hickerson's 'drifter' search program, used at various times to find wires, eaters, higher-period billiard table configurations, and related signal-carrying and signal-processing mechanisms. See also drifter.

: dragon (c/6 orthogonally, p6) This spaceship, discovered by Paul Tooke in April 2000, was the first known c/6 spaceship. With 102 cells, it was the smallest known orthogonal c/6 spaceship until Hartmut Holzwart discovered 56P6H1V0 in April 2009.

    .............O..OO......O..OOO
    .....O...OOOO.OOOOOO....O..OOO
    .OOOOO....O....O....OOO.......
    O......OO.O......OO.OOO..O.OOO
    .OOOOO.OOO........OOOO...O.OOO
    .....O..O..............O......
    ........OO..........OO.OO.....
    ........OO..........OO.OO.....
    .....O..O..............O......
    .OOOOO.OOO........OOOO...O.OOO
    O......OO.O......OO.OOO..O.OOO
    .OOOOO....O....O....OOO.......
    .....O...OOOO.OOOOOO....O..OOO
    .............O..OO......O..OOO

: drain trap = paperclip. This term is no longer in use.

: D read = destructive read

: dried = freeze-dried.

: drifter A perturbation moving within a stable pattern. Dean Hickerson has written a search program to search for drifters, with the hope of finding one which could be moved around a track. Because drifters can be very small, they could be packed more tightly than Herschels, and so allow the creation of oscillators of periods not yet attained, and possibly prove that Life is omniperiodic. Hickerson has found a number of components towards this end, but it has proved difficult to change the direction of movement of a drifter, and so far no complete track has been found. However, Hickerson has had success using the same program to find eaters with novel properties, such as sparking eaters and the ones shown in diuresis.

: dual 1-2-3-4 = Achim's p4

: duoplet A diagonal two-bit spark produced by many oscillators and eater reactions. Among other uses, it can reflect gliders 90 degrees. The following pattern shows an eater5 eating gliders and producing duoplets which are then used to reflect a separate glider stream. If only one glider is present, the eater5 successfully absorbs it, so this mechanism may be considered to be a simple AND gate.

    ..O....................
    O.O....................
    .OO....................
    .......................
    .......................
    .......O...............
    .....O.O...............
    ......OO...............
    .....................O.
    ....................O..
    ....................OOO
    .......................
    .......................
    ................O......
    ...............O.......
    ...............OOO.....
    .......................
    ....................OO.
    ................O...OO.
    ...............O.O.....
    ..............O.O......
    ..............O........
    .............OO........

: dying spark See spark. A spark by definition dies out completely after some number of ticks.

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