×

A nonlinear dynamics perspective of Wolfram’s new kind of science. V: Fractals everywhere. (English) Zbl 1094.37500

Summary: This fifth installment is devoted to an in-depth study of CA characteristic functions, a unified global representation for all 256 one-dimensional cellular automata local rules. Except for eight rather special local rules whose global dynamics are described by an affine (mod 1) function of only one binary cell state variable, all characteristic functions exhibit a fractal geometry where self-similar two-dimensional substructures manifest themselves, ad infinitum, as the number of cells \(4(I + 1) \to \infty\).
In addition to a complete gallery of time-1 characteristic functions for all 256 local rules, an accompanying table of explicit formulas is given for generating these characteristic functions directly from binary bit-strings, as in a digital-to-analog converter. To illustrate the potential applications of these fundamental formulas, we prove rigorously that the “right-copycat” local rule 170 is equivalent globally to the classic “left-shift” Bernoulli map. Similarly, we prove the “left-copycat” local rule 240 is equivalent globally to the “right-shift” inverse Bernoulli map.
Various geometrical and analytical properties have been identified from each characteristic function and explained rigorously. In particular, two-level stratified subpatterns found in most characteristic functions are shown to emerge if, and only if, \(b_{1} \neq 0\), where \(b_{1}\) is the “synaptic coefficient” associated with the cell differential equation developed in Part I. Gardens of Eden are derived from the decimal range of the characteristic function of each local rule and tabulated. Each of these binary strings has no predecessors (pre-image) and has therefore no past, but only the present and the future. Even more fascinating, many local rules are endowed with binary configurations which not only have no predecessors, but are also fixed points of the characteristic functions. To dramatize that such points have no past, and no future, they are henceforth christened “Isles of Eden”. They too have been identified and tabulated.
For parts II, III and IV see [ibid. 13, No. 9, 2377–2491 (2003; Zbl 1046.37004), 14, No. 11, 3689–3820 (2004; Zbl 1091.37500) and 15, No. 4, 1045–1183 (2005; Zbl 1084.37011)].

MSC:

37B15 Dynamical aspects of cellular automata
92B20 Neural networks for/in biological studies, artificial life and related topics
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnsley M. F., Fractals Everywhere (1988) · Zbl 0691.58001
[2] Billingsley P., Ergodic Theory and Information (1978) · Zbl 0184.43301
[3] DOI: 10.1142/S0218127402006333 · Zbl 1043.37009 · doi:10.1142/S0218127402006333
[4] DOI: 10.1142/S0218127403008041 · Zbl 1046.37004 · doi:10.1142/S0218127403008041
[5] DOI: 10.1142/S0218127404011764 · Zbl 1091.37500 · doi:10.1142/S0218127404011764
[6] DOI: 10.1142/S0218127405012995 · Zbl 1084.37011 · doi:10.1142/S0218127405012995
[7] Devaney R. L., A First Course in Chaotic Dynamic Systems: Theory and Experiment (1992) · Zbl 0768.58001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.