A method, using asymmetry graphs, both classifies and determines information flow patterns in a one-dimensional cellular automaton. The method presents a graphical representation of information flow in cellular automata using the eXclusive OR (XOR) relationship of the digits of the binary representation of the Wolfram number of the cellular automaton.
Asymmetry Graphs—a Means of Classifying and Determining Information Flow in Cellular Automata
Wolfram([1]) classifies cellular automata into four classes, I to IV. Class III automata produce intrinsic randomness, Class IV automata produce complexity, and the two other classes produce uninteresting behavior. This note proposes that one can both classify, and determine information flow in a cellular automaton by calculating the XOR asymmetry of the binary number of its rule.
The logical function eXclusiveOR (XOR) is given by: XOR (1,1) = 0; XOR (0,0) = 0; XOR (1,0) = 1; XOR (0,1) = 1. If the inputs to the function are the same (symmetric inputs), then the output is 0. Otherwise, if the inputs are different (asymmetric), the output is 1. A XOR output value of ‘0’ indicates no information flow. A XOR output value of ‘1’ indicates that there is information flow.
We form an asymmetry graph (A-Graph) from a given cellular automaton rule as follows—
Rule #30, illustrating randomness is, in binary notation 00011110. Write this backwards for convenience in calculation. Thus, 01111000, then form all couples starting from the left, giving us
01, 01, 01, 01, 00, 00, 00 forming couples with the first digit, and all the rest of the digits
11, 11,11, 10, 10 ,10 forming couples the second digit, and all the rest of the digits
11, 11, 10, 10,10 forming couples with the third digit, and all the rest of the digits
11, 10, 10, 10 …the fourth digit…
10, 10, 10 …the fifth digit…
00, 00 …the sixth digit...
00 …the seventh digit…
Let each couple so formed represent inputs to the XOR function, and write the output. Then obtain the ratio of the number of ‘1s’ in each column (numbering the columns from left to right) to the number of entries in that column.
1 2 3 4 5 6 7 COLUMNS—note: distance between digits is ‘1’ in column #1, ‘2’ in column #2, etc.
1, 1, 1, 1, 0, 0, 0
0, 0, 0, 1, 1, 1
0, 0, 1, 1, 1
0, 1, 1, 1
1, 1, 1
0, 0
___________________________
2/7, 3/6, 4/5, 4/4, 2/3, 1/2, 0/1, and write these as decimals, and graph on the ordinate as in Figure 1:
1 2 3 4 5 6 7 DISTANCE BETWEEN DIGITS—PLOTTED ON ABSCISSA
0.28, 0.5, 0.80, 1.0, 0.66, 0.5, 0 ASYMMETRY RATIO=INFORMATION FLOW—PLOTTED ON
ORDINATE
The distance between digits of the binary number (0,1,2,3,4,5,6,7) are graphed on the abscissa. The asymmetry graph of rule #30 is unimodal (one ‘hill’). Note: the XOR of a digit with itself is ‘0.’
Abbildung in dieser Leseprobe nicht enthaltenFigure 1
For rule #110, illustrating complexity, we have, 01101110 written backwards for convenience in calculating. Thus, 01110110, and form couples and take the XOR value of each couple to obtain,
1, 1, 1, 0, 1, 1, 0
0, 0, 1, 0, 0, 1
0, 1, 0, 0, 1
1, 0, 0, 1
1, 1, 0
0, 1
____________________________________
4/7, 4/6, 2/5, 1/4, 2/3, 1, 0
0.57, 0.66, 0.40, 0.25, 0.66, 1.0, 0
Plot these values on the abscissa of figure 1 and note the bimodal shape (hill-valley-hill) of the asymmetry graph of rule #110.
For rule #0, 00000000 in binary, its asymmetry graph is the flat dashed horizontal line shown in figure 1. Rule #7 (alternating dashes and dots) is also shown; we see that the A-graph of this rule is open on the right (not zero).
Let theordinatevalues of each asymmetry graph represent information flow in the cellular automaton.
Then we have:
Rule #0 no information flow
Rule #7 controlled information flow
Rule #30 uncontrolled information flowà randomness.
Rule #110 both controlled and uncontrolled information flowà complexity (structure).
Complexity = delicate balance between randomness and order.
The A-graph is a ‘scale-free map of information flow in a cellular automaton.’
Information flow beneath the single ‘hill’ of the A-graph of rule #30 is uncontrolled; therefore, information flows together into a jumble leading to intrinsic randomness. Similarly, beneath the first hill of rule #110, all information at shorter distances also flows together into a jumble; but the valley between the two hills of rule #110 indicates less information flow at medium distances, thus forming a ‘membrane’ or partial barrier to information flow rate ‘surrounding’ the structures that were formed at shorter distances beneath the first hill. Information is prevented from flowing outward from these structures, thereby preserving these structures so they stand out against the background.
The second hill of the A-graph of rule #110 allows information flow at greater distances among these preserved structures so that one sees random collisions of these structures. Thus, complexity arises due to random collisions under the second hill among random structures formed under the first hill, these structures having been maintained by the valley of low information flow between the hills.
Complexity can be viewed as macroscopically-partitioned randomness such that the partitioning allows our perception and analysis to observe what we call complexity. In a general sense, complexity is a form of randomness.
Complexity arises from random interactions among structures that are made up of random elements.
Therefore, forming the A-graph of any cellular automaton rule gives us a quick way to help classify the rule based on the shape of the A-graph. The A-graph also illustrates a graphical picture of information flow at all scales in the cellular automaton. Any rule with a bimodal asymmetry graph might produce complexity. However, the height, placement, overall shape of the hills, and the depth of the valley between the hills are critical factors.
A useful general rule is:
Asymmetry + Entropy à Complexity
Therefore, Non-homogeneity + Randomization à Complexity if the asymmetry has a bimodal A-graph representation, such that there is scale-independent control over the information flow rate at intermediate distances.
For cellular automata, another expression of the same rule is:
XOR Asymmetry + Computation à Complexity, if the asymmetry has a bimodal A-graph representation, such that there is scale-independent control over the information flow rate at intermediate distances.
In a steady state we can write Ohms law as,
Current = electromotive force/resistance
or
Current flow = electromotive force x conductance.
Now, equating current flow with information flow, conductance with XOR asymmetry, and electromotive force with computation, we can write:
Information flow = (computation) x (XOR asymmetry)
as a more general statement of Ohms law. Accordingly, we might ask, which cellular automaton rules (e.g. rule #7) mimic superconductivity. Can the study of the information flow in cellular automata suggest, and allow fabrication of materials that are superconductive at room temperature?
In addition, since chemical reactions can be viewed as the transfer of information (electrons) among various molecules, can the formation of complex chemicals and life, itself, be described by rule #110?
In a general sense, life requires complexity, the maintenance of structure versus entropy or randomness. Therefore, if aging and disease represent loss of complexity, then should our treatments best be directed, most generally, towards re-establishment of information flow (biochemical reactions) that parallels that of the A-graph of rule #110?
____________
References
1. Wolfram, S.,A New Kind of Science©2002 Wolfram Media Inc. Wolfram, Stephen, Wolfram Media, Inc., May 14, 2002, ISBN 1-57955-008-8.
2. Goldberg, M., ‘Complexity.’ Telicom—the Journal of the International Society for
Philosophical Enquiry, Vol. XV No. 10 September 2002, pp 44-49. ISSN: 1087-6456.
3. Goldberg, M., ‘Complexity and Randomness.’ Telicom—the Journal of the International
Society for Philosophical Enquiry, Vol. XVI, No. 3 June/July 2003, pp 65-67. ISSN: 1087-
Frequently Asked Questions: Asymmetry Graphs and Cellular Automata
What is the main idea of the text?
The text proposes using XOR asymmetry graphs (A-graphs) to classify cellular automata and determine information flow within them. It suggests that the shape of the A-graph can indicate whether an automaton exhibits randomness, complexity, or uninteresting behavior.
How are asymmetry graphs (A-graphs) created?
A-graphs are created from the binary representation of a cellular automaton rule. The binary digits are taken in pairs, and the XOR function is applied to each pair. The ratio of '1' outputs to the total number of entries in each column is calculated, and these ratios are then plotted against the distance between the digits in the binary number.
What does the XOR function represent in this context?
The XOR function determines information flow. A XOR output of '0' indicates no information flow, while a XOR output of '1' indicates information flow between the binary digits being compared.
How does the shape of the A-graph relate to the behavior of a cellular automaton?
A unimodal (single hill) A-graph is associated with randomness (e.g., rule #30). A bimodal (hill-valley-hill) A-graph is associated with complexity (e.g., rule #110). A flat A-graph (e.g., rule #0) indicates no information flow, and an open A-graph (e.g., rule #7) indicates controlled information flow.
What is the significance of the valley between the hills in the A-graph of rule #110?
The valley in the A-graph of rule #110 represents less information flow at medium distances. This acts as a partial barrier, preserving structures that were formed at shorter distances. This contributes to the complex behavior observed in rule #110.
How does the text define "complexity"?
The text defines complexity as a delicate balance between randomness and order. It is further described as macroscopically-partitioned randomness, where the partitioning allows for observation and analysis. It is further expanded to say Complexity arises from random interactions among structures that are made up of random elements.
What is the relationship between asymmetry, entropy, and complexity?
The text proposes the formula: Asymmetry + Entropy à Complexity. This suggests that non-homogeneity and randomization, combined with a bimodal A-graph representation, can lead to complexity. The shape of the asymmetry graph should be such that there is scale-independent control over the information flow rate at intermediate distances
How is Ohm's Law applied to information flow in cellular automata?
The text draws an analogy between Ohm's Law (Current = Electromotive Force / Resistance) and information flow. It equates information flow with current, computation with electromotive force, and XOR asymmetry with conductance. This leads to the statement: Information Flow = (Computation) x (XOR Asymmetry).
What are some potential applications of this research?
The text suggests potential applications in fields such as superconductivity (mimicking cellular automaton rules with desirable information flow properties) and understanding chemical reactions and the origin of life (describing the formation of complex chemicals using rule #110). The final suggested application is to help determine the re-establishment of information flow to assist aging or diseases.
- Citar trabajo
- Marshall Goldberg (Autor), 2016, Classification of Cellular Automata Using Asymmetry Graphs, Múnich, GRIN Verlag, https://www.grin.com/document/341659
