Critters is a reversible block cellular automaton with similar dynamics to Conway's Game of Life,[1] [2] first described by Tommaso Toffoli and Norman Margolus in 1987.[3]
Critters is defined on a two-dimensional infinite grid of cells, which may be identified with the integer lattice. 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 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.[3]
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.[3] 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.[4]
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.[2] (I.e. the two versions are the same, up to flipping all states every other generation.)
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.[1] [3] 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 escape from the central random area and interact with each other.[1] [2] [3] It has been conjectured, but not proven, that for periodic boundary conditions (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 through a field of oscillating debris.[5]
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,[1] [5] and when two gliders collide symmetrically, the result must also be a symmetric collection of two or more gliders leaving the collision site.[1] With an initial state that carefully arranges the sites of these collisions, the Critters rule can be made to simulate a billiard-ball computer and thus, like Life, it can support universal computation.[1] The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.[2]
Despite the complexity of its behavior, Critters obeys certain conservation laws 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.)[1] 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.[3]