Second order cellular automaton
Encyclopedia
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 depends not only on its neighborhood at time , but also on its state at time . Specifically, the neighborhood at time is used to choose a function from some larger set of possible functions, that maps the state of the cell at time to its state at time . As long as each possible function 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 computing the exclusive or of the what the ordinary rule would compute as the new state of each cell at time with its past state at time . 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 named by Stephen Wolfram
by appending an "R" to the number or code of the base rule.
Second-order automata may be used to simulate billiard-ball computer
s and the Ising model
of ferromagnetism
in statistical mechanics
. They may also be used for cryptography
.
Reversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
(CA) invented by Edward Fredkin
Edward Fredkin
Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...
where the state of a cell at time depends not only on its neighborhood at time , but also on its state at time . Specifically, the neighborhood at time is used to choose a function from some larger set of possible functions, that maps the state of the cell at time to its state at time . As long as each possible function 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 computing the exclusive or of the what the ordinary rule would compute as the new state of each cell at time with its past state at time . 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 named by Stephen Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
by appending an "R" to the number or code of the base rule.
Second-order automata may be used to simulate billiard-ball computer
Billiard-Ball Computer
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 Tommaso Toffoli...
s and the Ising model
Ising model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
of ferromagnetism
Ferromagnetism
Ferromagnetism is the basic mechanism by which certain materials form permanent magnets, or are attracted to magnets. In physics, several different types of magnetism are distinguished...
in statistical mechanics
Statistical mechanics
Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
. They may also be used for cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.