A Nonlinear Dynamics Perspective of Wolfram's New Kind of Science. Volumes III and IV

Andrew Adamatzky (University of the West of England, Bristol, UK)

Kybernetes

ISSN: 0368-492X

Article publication date: 8 June 2012

67

Citation

Adamatzky, A. (2012), "A Nonlinear Dynamics Perspective of Wolfram's New Kind of Science. Volumes III and IV", Kybernetes, Vol. 41 No. 5/6, pp. 817-819. https://doi.org/10.1108/03684921211243446

Publisher

:

Emerald Group Publishing Limited

Copyright © 2012, Emerald Group Publishing Limited


If you are not a programmer and want to play with one‐dimensional cellular automata you can download DDLab, MCell or Golly. But if your village is hit by an electro‐magnetic bomb and your computer is dead, then, with trembling gratefulness, you take from the shelf Leon Chua's volumes of “nonlinear dynamics perspective of Wolfram's new kind of science”. The volumes are generously illustrated and will keep you occupied for days.

The book is a lavishly illustrated personal account of Leon Chua's experiments with and analytical thoughts of binary‐state ternary‐neighbourhood one‐dimensional cellular automata (Chua, 2009), their classification, characterisation and mathematisation. Chua's book are nevertheless inspired by Wolfram's approach to complex systems as cellular automata, and indeed his famous classification of one‐dimensional cellular automata. As Chua writes: “Our quest for an analytical holy grail is propelled by our firm conviction that there must exist an elementary yet rigorous analytical theory of cellular automata that underpins the empirical morass collected in Wolfram fundamental tome … ”. Here we can highlight three key topics discussed in the book.

First, one only needs to study 88, out of 256 rules, since any other rule is globally equivalent to one of the 88 globally independent rules.

Second, the 88 rules can be partitioned rigorously into six mutually‐exclusive groups. Group 1 contains 25 rules with robust period‐1 attractors. Group 2 contains 13 rules with robust period‐2 attractors. Group 3 contains two rules with robust period‐3 or period‐6 attractors. Group 4 contains 32 rules with robust Bernoulli attractors. Group 5 contains ten rules with robust quasi‐ergodic “complex” Bernoulli attractors, and group 6 contains eight rules with robust quasi‐ergodic “hyper” Bernoulli attractors.

Third, the qualitative dynamics of all rules belonging to groups 1‐4 are completely predictable. The remaining 18 rules belonging to groups 5 and 6 may never be completely characterized because some of these rules may be Turing machines capable of universal computations.

A truly surprising result presented in this book is that the steady‐state space‐time diagrams of more than half of the 256 elementary rules are “time reversible” in the sense that the “past” of a steady‐state space‐time diagram can be recovered by applying the last bit string as the initial state of its associated “left‐right equivalent” rule. In other words, the “past” of one rule is the “future” of its associated rule, and vice‐versa. Indeed, these time‐reversible rules are “time machines”.

Another surprising discovery is that almost all rules (except for 28) are endowed with “isolated” periodic orbits, called “Isles of Eden”, with an empty “basin of attraction”. Unlike other periodic orbits, an “Isle of Eden” is not an attractor: one has to start from a bit string belonging to an Isle of Eden to get on it! For example, the bit string consisting of alternating “0” and “1” bits is an Isle of Eden of the famous “random‐noise generator” rule 30. There are no other bit strings of rule 30 that converge to this alternating bit string.

In Volume III of Chua's book you will find characterisation of equivalence classes of elementary cellular automata in terms of Bernoulli shifts (e.g. the steady‐state space‐time diagram of all rules belonging to group 4 can be generated by simply shifting each bit string by a fixed number of bits, either to the left, or to the right, and then followed possibly by taking its complement), steady‐state analysis of the classes and their qualitative properties. There you will also find colourful galleries of basin tree diagrams for 18, 22, 54, 73, 90, 105, 122, 126, 146, 150 (in Wolfram notations), characterization of the rules using the difference equations (ideas inherited from famous cellular non‐linear networks invented by Chua), global state transition formulas for additive rules and tree diagrams for hyper Bernoulli‐shift rules 26, 30, 41, 45, 60, 106, 110, 154. The book also illustrates how to use famous de Bruijn graphs to detect presence of non‐constructible patterns, or Isle of Eden configurations.

Volume IV deals with quasi‐ergodicity and its relation to complexity, as well as fractals in rules 60, 90, 105, 150. Illustrative analysis of 28 strictly dissipative, i.e. without Isle of Eden, local rules is also provided together with colourful illustrations of basin tree diagrams of period‐1 rules.

Leon Chua volumes well complement and in some topics overlap with other classical monographs on one‐dimensional cellular automata.

First of all, I must mention iconic Atlas of Basins of Attraction Fields of One‐Dimensional Cellular Automata by Andy Wuensche (Wuensche and Lesser, 1992). Many parts of theoretical studies of Wuensche's and Chua's books are similar, including calculation of pre‐images. Analytical expressions of state‐transition functions suggested by Chua well complement empirically derived parameter by Wuensche in (Wuensche and Lesser, 1992). Catalogs of global transition graphs are another common feature of Wuensche and Chua boks. Talking about global transition graphs it is advisable to download DDLab at www.ddlab.com and observe dynamics of elementary rules discussed in Chua's volumes, as well as compare global transition graphs dynamically constructed in DDLab with those illustrated in Chua's book. Recent advances in DDLab and user‐friendly instructions on the software usage can be found in marvellous, and unique in its own sense, Wuensche's book Exploring Complex Dynamics (Wuensche, 2011).

Second, computational analysis and analytic representation of elementary rules is offered by Burton Voorhees in his book (Voorhees, 1996) published in 1996. There you can also find Boolean expression for two‐ and three‐site rules, and a compendium of extensive analytical results on Garden of Eden configurations.

Third, I would suggest to have a look at Harold McIntosh's excellent introduction to one‐dimensional cellular automata and tools for their analysis (McIntosh, 2009). McIntosh was the first who in 1980s applied de Bruijn graphs to analysis of cell‐state transition rules and prediction of cellular automata behaviour. In his book you will find detailed results on representations of de Bruijn matrices, their relation to probabilistic matrices and global evolution of cellular automata, subset diagrams, calculating of Garden‐of‐Eden configuration, and application of de Bruijn graphs in studies of reversible cellular automata.

The book is unusual. This is not a typical book written by someone from the field of cellular automata. This is a journey‐tutorial. Leon Chua is a world‐wide expert in non‐linear circuits. And in his book he presents his personal journey into the field of cellular automata. The book makes a good didactic material, excellent tutorial and is an accessible introduction to the non‐linear theory of cellular automata.

A unique feature of this book that makes it accessible to high school kids is the use and exploitation of the “Boolean Cubes” for representing the truth tables. This attractive geometric representation makes it possible to uncover the hidden symmetry of the CA rules, and led directly to the equivalence classes cited above. Indeed, kids will be able to derive, by inspection, the equivalent “siblings” of every rule, and extract from them the 88 globally‐equivalence classes.

Notes

Volume 1 (ISBN‐13: 978‐9812569776) was published in 2006, and Volume 2 (ISBN‐13: 978‐9812569769) in 2007

References

Chua, L.O. (2009), “A nonlinear dynamics perspective of Wolfram's new kind of science”, Part XI Int. J. Bifurcation Chaos, Vol. 11, pp. 1751930, (2009), Part XII Int. J. Bifurcation Chaos, Vol. 19, pp. 3887‐4038; (2010), Part XIII Int. J. Bifurcation Chaos, pp. 1859‐2003; (2010), Part XIV Int. J. Bifurcation Chaos, Vol. 20, pp. 2253‐2425.

McIntosh, H.V. (2009), One‐Dimensional Cellular Automata, Luniver Press, Beckington.

Voorhees, B.H. (1996), Computational Analysis of One‐Dimensional Cellular Automata, World Scientific, Singapore.

Wuensche, A. (2011), Exploring Discrete Dynamics, Luniver Press, Beckington.

Wuensche, A. and Lesser, M. (1992), The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One‐Dimensional Cellular Automata, Addison‐Wesley, Reading, MA.

Related articles