Critters is a reversible

block Block or blocked may refer to: Arts, entertainment and media Broadcasting * Block programming, the result of a programming strategy in broadcasting * W242BX, a radio station licensed to Greenville, South Carolina, United States known as ''96.3 ...

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...

with similar dynamics to

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. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no furt ...

,.. first described by

Tommaso Toffoli Tommaso Toffoli () is an Italian-American professor of electrical and computer engineering at Boston University where he joined the faculty in 1995. He has worked on cellular automata and the theory of artificial life (with Edward Fredkin and other ...

and

Norman Margolus Norman H. Margolus (born 1955) is a Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing.. He is a research affiliate with the Computer Science and Artificial Intelligence Laborato ...

in 1987..

Definition

Critters is defined on a two-dimensional infinite grid of cells, which may be identified with the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or gri ...

. As in Conway's Game of Life, at any point in time each cell may be in one of two states: alive or dead. The Critters rule is a

block cellular automaton 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 (with different partitions at different time steps) and the transition rule ...

using the Margolus neighborhood. This means that, at each step, the cells of the automaton are partitioned into 2 × 2 blocks and each block is updated independently of the other blocks. The center of a block at one time step becomes the corner of four blocks at the next time step, and vice versa; in this way, the four cells in each block belong to four different 2 × 2 blocks of the previous partition. The transition function for Critters counts the number of live cells in a block, and if this number is exactly two it leaves the block unchanged. If the number of live cells is zero, one, or four, the transition function flips the state of every cell in the block. And finally, if the number of live cells is exactly three, the transition flips every state and then rotates the whole block by 180°. Because the function that combines these operations is invertible, the automaton defined by these rules is a reversible cellular automaton. Because cells in blocks away from active blocks will oscillate between alive and dead on successive generations, the whole field will appear to "flicker". In some implementations of Critters, this flicker is removed by inverting the image (but not the cell states) on odd-numbered generations. An alternative version of the transition function flips the states only in blocks with exactly two live cells, and in alternating time steps rotates either the blocks with three live cells or the blocks with one live cell. Unlike the original transition function, this preserves the number of live cells in each step, but leads to equivalent dynamic behavior to the original version of the function, without the need for the image-inversion step. (I.e. the two versions are the same, up to flipping all states every other generation.)

Dynamics

In the Critters rule, as with any reversible cellular automaton, initial states in which all cells take randomly chosen states remain unstructured throughout their evolution. However, when started with a smaller field of random cells centered within a larger region of dead cells, many small patterns similar to life's

glider Glider may refer to: Aircraft and transport Aircraft * Glider (aircraft), heavier-than-air aircraft primarily intended for unpowered flight ** Glider (sailplane), a rigid-winged glider aircraft with an undercarriage, used in the sport of gliding ...

escape from the central random area and interact with each other. It has been conjectured, but not proven, that for

periodic boundary conditions Periodic boundary conditions (PBCs) are a set of boundary conditions which are often chosen for approximating a large (infinite) system by using a small part called a ''unit cell''. PBCs are often used in computer simulations and mathematical mode ...

(so that the entire space of the cellular automaton is finite) initial fields of random cells that are sufficiently smaller than the whole space will lead with high probability to states in which a single glider follows a

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb ...

through a field of oscillating debris.. In Conway's life, collisions of gliders may result in a completely dead state, a stable pattern, or an oscillator, but this is not possible in Critters. Instead, because of the reversibility of the rule, every collision of two or more gliders must result in a pattern from which at least one glider emerges, and when two gliders collide symmetrically, the result must also be a symmetric collection of two or more gliders leaving the collision site. With an initial state that carefully arranges the sites of these collisions, the Critters rule can be made to simulate a

billiard-ball computer A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer based on Newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli. Instead of using electronic signals ...

and thus, like Life, it can support universal computation. The Critters rule can also support more complex spaceships of varying speeds as well as

oscillators Oscillation is the repetitive or periodic variation, typically in time, of some measure about a central value (often a point of equilibrium) or between two or more different states. Familiar examples of oscillation include a swinging pendulum ...

with infinitely many different periods. Despite the complexity of its behavior, Critters obeys certain

conservation law In physics, a conservation law states that a particular measurable property of an isolated physical system does not change as the system evolves over time. Exact conservation laws include conservation of energy, conservation of linear momentum, ...

s and symmetry rules. For instance, the parity of the number of live cells along certain diagonals of the grid is not changed by the update rule, and remains unchanged throughout the evolution of any Critters pattern. Additionally, if a pattern starts out with a finite number of live cells, then after any even number of steps it will have the same finite number of live cells. (After odd numbers of steps, this number will instead count the dead cells of the pattern.) Unlike many of the other reversible block cellular rules studied by Toffoli and Margolus, the Critters rule is not its own inverse, so Critters patterns do not obey time-reversal symmetry; however, it is instead symmetric under a combination of time reversal and state complementation.

References

{{reflist Cellular automaton rules