page_title: Reversible cellular automaton
section_title: Critters
hierarchical_section_title: Reversible cellular automaton / Examples / Critters
caption_attribution_description: English: A pattern in the Critters block cellular automaton rule
context_page_description: A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.
  Several methods are known for defining cellular automata rules that are reversible; these include the block cellular automaton method, in which each update partitions the cells into blocks and applies an invertible function separately to each block, and the second-order cellular automaton method, in which the update rule combines states from two previous steps of the automaton.
context_section_description: Conway's Game of Life, one of the most famous cellular automaton rules, is not reversible: for instance, it has many patterns that die out completely, so the configuration in which all cells are dead has many predecessors, and it also has Garden of Eden patterns with no predecessors. However, another rule called "Critters" by its inventors, Tommaso Toffoli and Norman Margolus, is reversible and has similar dynamic behavior to Life.
  The Critters rule is a block cellular automaton in which, at each step, the cells of the automaton are partitioned into 2×2 blocks and each block is updated independently of the other blocks. Its transition function flips the state of every cell in a block that does not have exactly two live cells, and in addition rotates by 180° blocks with exactly three live cells. Because this function is invertible, the automaton defined by these rules is a reversible cellular automaton.
  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. The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.
caption: Gliders escape from a central random seed region in the Critters block cellular automaton rule.
exif: {}