Second order cellular automaton
- Second order cellular automaton
A second order cellular automaton is a reversible cellular automaton (CA) 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". Specifically, the neighborhood at "t-1" is used to choose a function "fn" that maps the state of the cell at time "t-2" to its state at time "t". As long as each function "fn" is invertible, it follows that the resulting automaton is reversible, regardless of how the functions are chosen.
In particular, for two-state cellular automata, any ordinary CA rule can be turned into a second order rule by xor-ing the new state of each cell at time "t" with its past state at time "t-2". In fact, all two-state second order rules may be produced in this way. The resulting second order automaton, however, will generally bear little resemblance to the ordinary CA it was constructed from. Second order rules constructed in this way are commonly denoted by appending an "R" to the number or code of the base rule.
Second order CA can be implemented quite easily and efficiently. The need to remember the state of cells at "t"-2 is not nearly as much of a burden as it may seem, since most conventional CA implementations must use some form of double buffering anyway. Converting a conventional CA implementation into a second order one may be as simple as replacing one assignment operation with an XOR.
References
* Wolfram, Stephen, 2002. [http://www.wolframscience.com/nksonline/page-437-text A New Kind of Science] , pp. 437-440, 452. Wolfram Media. ISBN 1-57955-008-8.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states … Wikipedia
Quantum dot cellular automaton — Quantum Dot Cellular Automata (sometimes referred to simply as quantum cellular automata, or QCA) Any device designed to represent data and perform computation, regardless of the physics principles it exploits and materials used to build it, must … Wikipedia
Puffer train (cellular automaton) — In a cellular automaton a puffer train, or simply puffer, is a finite pattern that moves itself across the universe , leaving debris behind. Thus a pattern consisting of only a puffer will grow arbitrarily large over time. Puffers differ from… … Wikipedia
Asynchronous cellular automaton — 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 … Wikipedia
Quantum cellular automata — (QCA) refers to any one of several models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann. It may also refer to quantum dot cellular automata, which is a proposed… … Wikipedia
Norman Margolus — Norman H. Margolus (born 1955)[1] is an Canadian American[2] physicist and computer scientist, known for his work on cellular automata and reversible computing.[3] He is a research affiliate with the Computer Science and Artificial Intelligence… … Wikipedia
List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia
Lattice gas automaton — Lattice gas automata (LGA) or lattice gas cellular automata (LGCA) methods are a series of cellular automata methods used to simulate fluid flows. It was the precursor to the lattice Boltzmann methods. From the LGCA, it is possible to derive the… … Wikipedia
Billiard ball computer — Fredkin and Toffoli Gate billiard ball model A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and… … Wikipedia
Rule 184 — is a one dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:* Rule 184 can be used as a simple model for… … Wikipedia
