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 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]
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. [2]
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. [4]
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] [4] 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]
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 further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.
A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματα, which means "self-making".
The Rule 110 cellular automaton is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
A cellular automaton (CA) is Life-like if it meets the following criteria:
Seeds is a cellular automaton in the same family as the Game of Life, initially investigated by Brian Silverman and named by Mirek Wójtowicz. It consists of infinite two-dimensional grid of cells, each of which may be in one of two states: on or off. Each cell is considered to have eight neighbors, as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of one cell every four generations, or . The glider is often produced from randomly generated starting configurations. John Conway has remarked that he wishes he hadn't called it the glider. The game was developed before the widespread use of interactive computers, and after seeing it animated, he feels the glider looks more like an ant walking across the plane.
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin where the state of a cell at time t depends not only on its neighborhood at time t − 1, but also on its state at time t − 2.
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 and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
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 like a conventional computer, it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly. It was devised to investigate the relation between computation and reversible processes in physics.
A rake, in the lexicon of cellular automata, is a type of puffer train, which is an automaton that leaves behind a trail of debris. In the case of a rake, however, the debris left behind is a stream of spaceships, which are automata that "travel" by looping through a short series of iterations and end up in a new location after each cycle returns to the original configuration.
Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells. In contrast, an asynchronous cellular automaton is able to update individual cells independently, in such a way that the new state of a cell affects the calculation of states in neighbouring cells.
Lattice gas automata (LGA), or lattice gas cellular automata, are a type of cellular automaton used to simulate fluid flows, pioneered by Hardy–Pomeau–de Pazzis and Frisch–Hasslacher–Pomeau. They were the precursor to the lattice Boltzmann methods. From lattice gas automata, it is possible to derive the macroscopic Navier–Stokes equations. Interest in lattice gas automaton methods levelled off in the early 1990s, as the interest in the lattice Boltzmann started to rise.
In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".
Life without Death is a cellular automaton, similar to Conway's Game of Life and other Life-like cellular automaton rules. In this cellular automaton, an initial seed pattern grows according to the same rule as in Conway's Game of Life; however, unlike Life, patterns never shrink. The rule was originally considered by Toffoli & Margolus (1987), who called it "Inkspot"; it has also been called "Flakes". In contrast to the more complex patterns that exist within Conway's Game of Life, Life without Death commonly features still life patterns, in which no change occurs, and ladder patterns, that grow in a straight line.
Norman H. Margolus 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 Laboratory at the Massachusetts Institute of Technology.
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.
In mathematics, a surjunctive group is a group such that every injective cellular automaton with the group elements as its cells is also surjective. Surjunctive groups were introduced by Gottschalk (1973). It is unknown whether every group is surjunctive.