Critters

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