Wolfram code
Encyclopedia
Wolfram code is a naming system often used for one-dimensional cellular automaton
rules, introduced by Stephen Wolfram
in a 1983 paper and used in his book A New Kind of Science
.
The code is based on the observation that a table specifying the new state of each cell in the automaton, as a function of the states in its neighborhood, may be interpreted as a k-digit number in the S-ary positional number system, where S is the number of states that each cell in the automaton may have, k = S2n + 1 is the number of neighborhood configurations, and n is the radius of the neighborhood. Thus, the Wolfram code for a particular rule is a number in the range from 0 to SS − 1, converted from S-ary to decimal
notation. It may be calculated as follows:
The Wolfram code does not specify the size (nor shape) of the neighbourhood, nor the number of states — these are assumed to be known from context. When used on their own without such context, the codes are often assumed to refer to the class of elementary cellular automata
, two-state one-dimensional cellular automata with a (contiguous) three-cell neighbourhood, which Wolfram extensively investigates in his book. Notable rules in this class include rule 30
, rule 110, and rule 184
. Rule 90
is also interesting because it creates Pascal's Triangle
modulo 2. A code of this type suffixed by an R, such as "Rule 37R", indicates a second-order cellular automaton with the same neighborhood structure.
While in a strict sense every Wolfram code in the valid range defines a different rule, some of these rules are isomorphic and usually considered equivalent. For example, rule 110 above is isomorphic with the rules 124, 137 and 193, which can be obtained from the original by left-right reflection and by renumbering the states. By convention, each such isomorphism class is represented by the rule with the lowest code number in it. A disadvantage of the Wolfram notation, and the use of decimal notation in particular, is that it makes such isomorphisms harder to see than some alternative notations. Despite this, it has become the de facto standard way of referring to one-dimensional cellular automata.
R=SS(2n+1)D
The most common example has S = 2, n = 1 and D = 1, giving R = 256. It should be noticed that the number of possible rules has an extreme dependence on the dimensionality of the system. For example, increasing the number of dimensions (D) from 1 to 2 increases the number of possible rules from 256 to 2512 (which is ~1.341×10154).
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
rules, introduced 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 :...
in a 1983 paper and used in his book A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
.
The code is based on the observation that a table specifying the new state of each cell in the automaton, as a function of the states in its neighborhood, may be interpreted as a k-digit number in the S-ary positional number system, where S is the number of states that each cell in the automaton may have, k = S2n + 1 is the number of neighborhood configurations, and n is the radius of the neighborhood. Thus, the Wolfram code for a particular rule is a number in the range from 0 to SS − 1, converted from S-ary to decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
notation. It may be calculated as follows:
- List all the S2n + 1 possible state configurations of the neighbourhood of a given cell.
- Interpreting each configuration as a number as described above, sort them in descending numerical order.
- For each configuration, list the state which the given cell will have, according to this rule, on the next iteration.
- Interpret the resulting list of states again as an S-ary number, and convert this number to decimal. The resulting decimal number is the Wolfram code.
The Wolfram code does not specify the size (nor shape) of the neighbourhood, nor the number of states — these are assumed to be known from context. When used on their own without such context, the codes are often assumed to refer to the class of elementary cellular automata
Elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors....
, two-state one-dimensional cellular automata with a (contiguous) three-cell neighbourhood, which Wolfram extensively investigates in his book. Notable rules in this class include rule 30
Rule 30
Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science...
, rule 110, and rule 184
Rule 184
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 90
Rule 90
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 the two neighboring values...
is also interesting because it creates Pascal's Triangle
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
modulo 2. A code of this type suffixed by an R, such as "Rule 37R", indicates a second-order cellular automaton with the same neighborhood structure.
While in a strict sense every Wolfram code in the valid range defines a different rule, some of these rules are isomorphic and usually considered equivalent. For example, rule 110 above is isomorphic with the rules 124, 137 and 193, which can be obtained from the original by left-right reflection and by renumbering the states. By convention, each such isomorphism class is represented by the rule with the lowest code number in it. A disadvantage of the Wolfram notation, and the use of decimal notation in particular, is that it makes such isomorphisms harder to see than some alternative notations. Despite this, it has become the de facto standard way of referring to one-dimensional cellular automata.
Generalized Cellular Automata
The number of possible rules, R, for a generalized cellular automaton in which each cell may assume one of S states as determined by a neighborhood size of n, in a D-dimensional space is given by:R=SS(2n+1)D
The most common example has S = 2, n = 1 and D = 1, giving R = 256. It should be noticed that the number of possible rules has an extreme dependence on the dimensionality of the system. For example, increasing the number of dimensions (D) from 1 to 2 increases the number of possible rules from 256 to 2512 (which is ~1.341×10154).