Classification of Cellular Automata Using Asymmetry Graphs

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-

6456.