Recent from talks
Nothing was collected or created yet.
Wolfram code
View on WikipediaWolfram code is a widely used[1] numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper[2] and popularized in his book A New Kind of Science.[3]
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 SS2n + 1 − 1, converted from S-ary to decimal 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, 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.
Generalized cellular automata
[edit]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. 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).
References
[edit]- ^ Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010). Cellular Automata and Groups. Springer. p. 28. doi:10.1007/978-3-642-14034-1. ISBN 978-3-642-14034-1. Retrieved 22 October 2022.
- ^ Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
- ^ Wolfram, Stephen (May 14, 2002). A New Kind of Science. Wolfram Media, Inc. ISBN 1-57955-008-8.
Wolfram code
View on GrokipediaFundamentals of Cellular Automata
Elementary Cellular Automata
Cellular automata are discrete computational models consisting of a lattice of cells, each in one of a finite number of states, that evolve over discrete time steps according to a set of local rules derived from the states of neighboring cells.[2] These models simulate complex global patterns emerging from simple local interactions, with the lattice typically forming a regular grid such as a one-dimensional line or higher-dimensional array.[2] The evolution occurs synchronously, meaning all cells update their states simultaneously based on the current configuration.[2] Elementary cellular automata (ECA) represent the simplest form of one-dimensional cellular automata, where each cell assumes one of two binary states: 0 or 1.[1] The neighborhood for each cell comprises exactly three cells: the cell itself and its two immediate nearest neighbors (left and right).[3] This restricted setup, with a neighborhood radius of 1, defines the local rule as a function mapping the binary tuple of these three cells to the next state of the central cell.[3] In the evolution process, an initial configuration of the lattice serves as the starting point (often called generation 0), and each subsequent generation is computed by applying the local rule to every cell based solely on its three-cell neighborhood from the previous generation.[1] There are possible neighborhood configurations, each of which can map to either 0 or 1 in the next state, yielding a total of distinct possible ECA rules.[1] Wolfram codes provide a binary labeling system to uniquely identify each of these 256 rules.[1] To illustrate the evolution, consider a simple one-dimensional lattice with periodic boundary conditions under a generic majority rule, where a cell's next state is 1 if at least two of its three-neighbor cells (including itself) are 1 in the current generation, and 0 otherwise. The following table depicts the evolution of an initial configuration over four time steps, with the lattice wrapping around for edge cells:| Time | Cell Positions (1 to 5) |
|---|---|
| 0 | 0 1 0 1 0 |
| 1 | 0 0 1 0 0 |
| 2 | 0 0 0 0 0 |
| 3 | 0 0 0 0 0 |
| 4 | 0 0 0 0 0 |
Neighborhood and Rules
In elementary cellular automata, the neighborhood of a cell consists of the cell itself and its two immediate neighbors, one to the left and one to the right, forming a three-cell tuple represented as binary values (0 or 1).[1] This local structure captures all relevant information for determining the cell's next state, with the eight possible configurations ranging from 000 (all inactive) to 111 (all active).[4] A rule in these automata functions as a deterministic mapping that assigns a binary output (0 or 1) to each of the eight possible neighborhood inputs, specifying the state of the central cell in the subsequent time step.[1] This mapping ensures that the evolution of the entire grid proceeds synchronously and locally, with no direct interaction between non-adjacent cells.[4] The rule can be fully represented as a truth table enumerating all inputs and their corresponding outputs, allowing any specific behavior to be defined by selecting 0 or 1 for each case. For clarity, the table below shows the standard ordering of neighborhoods from 111 to 000, with generic outputs denoted as variables to , where each is either 0 or 1:| Neighborhood | Output |
|---|---|
| 111 | |
| 110 | |
| 101 | |
| 100 | |
| 011 | |
| 010 | |
| 001 | |
| 000 |
- Step 0: 000010000
- Step 1: 000101000
- Step 2: 001000100
- Step 3: 010101010
- Step 4: 100000001
- Step 5: 010000010
The Wolfram Code System
Construction of the Code
The construction of the Wolfram code begins with the output table for an elementary cellular automaton rule, which specifies the next state (0 or 1) of the central cell for each of the eight possible three-cell neighborhoods, ranging from 111 to 000 in binary notation.[6] These neighborhoods are ordered in descending binary value: 111, 110, 101, 100, 011, 010, 001, 000, with the outputs forming an 8-bit binary string where the most significant bit (MSB) corresponds to the neighborhood 111 and the least significant bit (LSB) to 000. This binary string is then interpreted as a base-2 integer and converted to its decimal equivalent, yielding the unique Wolfram code number between 0 and 255.[1] Mathematically, the Wolfram code is given by the formula where is the output (0 or 1) for the -th neighborhood in the reversed order (with for neighborhood 000 as the LSB, and for 111 as the MSB).[6] This summation directly computes the decimal value from the binary representation, ensuring a systematic encoding. For example, consider a rule with outputs 0 for 111, 1 for 110, 0 for 101, 1 for 100, 1 for 011, 0 for 010, 1 for 001, and 0 for 000. The resulting binary string is 01011010, which converts to decimal 90 (since ). Thus, this rule is designated as Rule 90.[1][6] This mapping is bijective, as there are exactly possible output combinations, each corresponding to a unique binary string and thus a distinct integer from 0 to 255, providing a complete and non-overlapping labeling for all elementary rules.Interpretation of the Number
To interpret a Wolfram code, which is a decimal number between 0 and 255 representing an elementary cellular automaton rule, the process begins by converting the decimal value to its 8-bit binary equivalent, padding with leading zeros if necessary to ensure exactly eight bits.[1] This binary string directly encodes the rule's output for each of the eight possible neighborhood configurations in a one-dimensional cellular automaton with two states (0 or 1) and a three-cell neighborhood (left, center, right).[1] The bits of the binary representation are assigned to the neighborhood patterns in decreasing order of their binary value, starting from the most significant bit (MSB, bit 7) for the pattern 111 and ending with the least significant bit (LSB, bit 0) for the pattern 000.[1] Each bit specifies the output state (1 for "on" or black, 0 for "off" or white) for the center cell in the next generation when that neighborhood occurs.[1] This mapping allows reconstruction of the full rule table, which is the reverse of the encoding process where outputs are combined into a binary number.[1] For example, consider Wolfram code 90. Converting 90 to binary yields 01011010 (or ).[7] The bits map as follows:| Neighborhood | Binary Value | Bit Position | Output |
|---|---|---|---|
| 111 | 7 | 7 (MSB) | 0 |
| 110 | 6 | 6 | 1 |
| 101 | 5 | 5 | 0 |
| 100 | 4 | 4 | 1 |
| 011 | 3 | 3 | 1 |
| 010 | 2 | 2 | 0 |
| 001 | 1 | 1 | 1 |
| 000 | 0 | 0 (LSB) | 0 |
