Narrow Results

This study describes the spatial disorder of one-dimensional Cellular Neural Networks (CNN) with a biased term by applying the iteration map method. Under certain parameters, the map is one-dimensional and the spatial entropy of stable stationary solutions can be obtained explicitly as a staircase function.

In this paper, the problem of making a nonlinear system chaotic by using state-feedback control is studied. The feedback controller uses a simple sine function of the system state, but only one component in each dimension. It is proved, by using the anti-integrable limit method, that the designed control system generates chaos in the sense of Devaney. In fact, the controlled system so designed is a perturbation of the original system, which turns out to be a simple Bernoulli shift.

By exploiting the new concepts of CA characteristic functions and their associated attractor time-τ maps, a complete characterization of the long-term time-asymptotic behaviors of all 256 one-dimensional CA rules are achieved via a single "probing" random input signal. In particular, the graphs of the time-1 maps of the 256 CA rules represent, in some sense, the generalized Green's functions for Cellular Automata. The asymptotic dynamical evolution on any CA attractor, or invariant orbit, of 206 (out of 256) CA rules can be predicted precisely, by inspection. In particular, a total of 112 CA rules are shown to obey a generalized Bernoulli σ_τ-shift rule, which involves the shifting of any binary string on an attractor, or invariant orbit, either to the left, or to the right, by up to 3 pixels, and followed possibly by a complementation of the resulting bit string.

The most intriguing result reported in this paper is the discovery that the four Turing-universal rules , , , and , and only these rules, exhibit a 1/f power spectrum.

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 (I + 1) → ∞.

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 is equivalent globally to the classic "left-shift" Bernoulli map. Similarly, we prove the "left-copycat" local rule 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₁ ≠ 0, where b₁ 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.

This paper proves, via an analytical approach, that 170 (out of 256) Boolean CA rules in a one-dimensional cellular automata (CA) are time-reversible in a generalized sense. The dynamics on each attractor of a time-reversible rule N is exactly mirrored, in both space and time, by its bilateral twin ruleN^†. In particular, all 69 period-1 rules, 17 (out of 25) period-2 rules, and 84 (out of 112) Bernoulli rules are time-reversible.

The remaining 86 CA rules are time-irreversible in the sense that N and N^† mirror their dynamics only in space, but not in time. In this case, each attractor of N defines a unique arrow of time.

A simple "time-reversal test" is given for testing whether an attractor of a CA rule is time-reversible or time-irreversible. For a time-reversible attractor of a CA rule N the past can be uniquely recovered from the future of N^†, and vice versa. This remarkable property provides 170 concrete examples of CA time machines where time travel can be routinely achieved by merely hopping from one attractor to its bilateral twin attractor, and vice versa. Moreover, the time-reversal property of some local rules can be programmed to mimic the matter–antimatter "annihilation" or "pair-production" phenomenon from high-energy physics, as well as to mimic the "contraction" or "expansion" scenarios associated with the Big Bang from cosmology.

Unlike the conventional laws of physics, which are based on a unique universe, most CA rules have multiple universes (i.e. attractors), each blessed with its own laws. Moreover, some CA rules are endowed with both time-reversible attractors and time-irreversible attractors.

Using an analytical approach, the time-τ return map of each Bernoulli στ-shift attractor of all 112 Bernoulli rules are shown to obey an ultra-compact formula in closed form, namely,.

or its inverse map.

These maps completely characterize the time-asymptotic (steady state) behavior of the nonlinear dynamics on the attractors. In-depth analysis of all but 18 global equivalence classes of CA rules have been derived, along with their basins of attraction, which characterize their transient regimes.

Above all, this paper provides a rigorous nonlinear dynamics foundation for a paradigm shift from an empirical-based approach à la Wolfram to an attractor-based analytical theory of cellular automata.

This paper continues our quest to develop a rigorous analytical theory of 1-D cellular automata via a nonlinear dynamics perspective. The 18 yet uncharacterized local rules are henceforth partitioned into ten complex Bernoulliσ_τ-shift rules and eight hyper Bernoulliσ_τ-shift rules, the latter including such famous rules and . All exhibit a bizarre composite wave dynamics with arbitrarily large Bernoulli velocity σ and Bernoulli return time τ as the length L → ∞.

Basin tree diagrams of all ten complex Bernoulli σ_τ-shift rules are exhibited for lengths L = 3, 4, …, 8. Superficial as it may seem, these basin tree diagrams suggest general qualitative properties which have since been proved to be true in general. Two such properties form the main results of this paper; namely,

Explicit global state transition formulas are given for local rules , and . Such formulas led to the rigorous proof of several surprising periodicity constraints for rule , and to the discovery of a new global, quasi-equivalence class, defined via an alternating transformation. In particular, local rules and are globally quasi-equivalent where corresponding space-time patterns can be derived from each other by simply complementing every other row.

Another important result of this paper is the discovery of a scale-free phenomenon exhibited by the local rules , and . In particular, the period "T" of all attractors of rules , and , as well as of all isles of Eden of rules and , increases linearly with unit slope, in logarithmic scale, with the length L.

This paper presents the basin tree diagrams of all hyper Bernoulli σ_τ-shift rules for string lengths L = 3, 4, …, 8. These diagrams have revealed many global and time-asymptotic properties that we have subsequently proved to be true for all L < ∞. In particular, we have proved that local rule has no Isles of Eden for all L, and that local rules and are inhabited by a dense set (continuum) of Isles of Eden if, and only if, L is an odd integer. A novel and powerful graph-theoretic tool, called Isles-of-Eden digraph, has been developed and can be used to test the existence of dense Isles of Eden of any local rule which satisfies certain constraints, such as rules , , , , as well as all invariant local rules, such as rules , , and , subject to no constraints.

Our scientific odyssey through the theory of 1-D cellular automata is enriched by the definition of quasi-ergodicity, a new empirical property discovered by analyzing the time-1 return maps of local rules. Quasi-ergodicity plays a key role in the classification of rules into six groups: in fact, it is an exclusive characteristic of complex and hyper Bernoulli-shift rules. Besides introducing quasi-ergodicity, this paper answers several questions posed in the previous chapters of our quest. To start with, we offer a rigorous explanation of the fractal behavior of the time-1 characteristic functions, finding the equations that describe this phenomenon. Then, we propose a classification of rules according to the presence of Isles of Eden, and prove that only 28 local rules out of 256 do not have any of them; this result sheds light on the importance of Isles of Eden. A section of this paper is devoted to the characterization of Bernoulli basin-tree diagrams through modular arithmetic; the formulas obtained allow us to shorten drastically the number of cases to take into consideration during numerical simulations. Last but not least, we present some theorems about additive rules, including an analytical explanation of their scale-free property.

In this paper, the chaotic behavior of a set-valued mapping F : X → 2^X, where X is a compact space, is investigated. The existence of the generalized shadowing property in the hyperspace 2^X is proved. Based on the generalized shadowing property of the set-valued mappings F and the assumption of the existence of an unstable chain recurrent point of the mapping F, it is shown that the Bernoulli system of bi-directional shifts is embedded in the sense of semiconjugacy into the image of mapping F, i.e. Smale's chaos in the set-valued system F is thereby proved.

Recently the strings and the string number of self-maps were used in the computation of the algebraic entropy of specific abelian group endomorphisms. We introduce two special kinds of strings, and their relative string numbers. We show that a dichotomy holds for all these three string numbers; in fact, they admit only zero and infinity as values on abelian group endomorphisms.

Monounary algebras are the most simple type of an algebraic structure. Oriented graphs with one outgoing arrow from every vertex represent them. The aim of this paper is to point out the interdisciplinary relationships concerning this structure. Bernoulli shift is a paradigmatic mapping in dynamical systems. It is also called dyadic, bit shift, doubling or sawtooth. We offer a look at the properties of this mapping via monounary algebras.

As the novel types of chaos-generating circuit usable for the bio-inspired information processing with their simple and suitable structure for the integration, capacitor-transistor pair (CTP), return-map unit and CMOS chaos multivibrator (CMV) have been developed. Noise source for the Boltzmann machine utilizing CTP or CMV, and the coupling experiment with the return-map unit are discussed. Operation of the pipelined AD converter as the chaos generating circuit under the map function of the Bernoulli-shift is also demonstrated.

This paper continues our quest to develop a rigorous analytical theory of 1-D cellular automata via a nonlinear dynamics perspective. The 18 yet uncharacterized local rules are henceforth partitioned into ten complex Bernoulliσ_τ-shift rules and eight hyper Bernoulliσ_τ-shift rules, the latter including such famous rules and . All exhibit a bizarre composite wave dynamics with arbitrarily large Bernoulli velocity σ and Bernoulli return time τ as the length L → ∞.

Basin tree diagrams of all ten complex Bernoulli σ_τ-shift rules are exhibited for lengths L = 3, 4, …, 8. Superficial as it may seem, these basin tree diagrams suggest general qualitative properties which have since been proved to be true in general. Two such properties form the main results of this paper; namely,

Another important result of this paper is the discovery of a scale-free phenomenon exhibited by the local rules , and . In particular, the period "T" of all attractors of rules , and , as well as of all isles of Eden of rules and , increases linearly with unit slope, in logarithmic scale, with the length L.

This paper presents the basin tree diagrams of all hyper Bernoulliσ_τ-shift rules for string lengths L = 3, 4, …, 8. These diagrams have revealed many global and time-asymptotic properties that we have subsequently proved to be true for all L < ∞. In particular, we have proved that local rule has no Isles of Eden for all L, and that local rules and are inhabited by a dense set (continuum) of Isles of Eden if, and only if, L is an odd integer. A novel and powerful graph-theoretic tool, called Isles-of-Eden digraph, has been developed and can be used to test the existence of dense Isles of Eden of any local rule which satisfies certain constraints, such as rules , , , , as well as all invariant local rules, such as rules , , and , subject to no constraints.

Our scientific odyssey through the theory of 1-D cellular automata is enriched by the definition of quasi-ergodicity, a new empirical property discovered by analyzing the time-1 return maps of local rules. Quasi-ergodicity plays a key role in the classification of rules into six groups: in fact, it is an exclusive characteristic of complex and hyper Bernoulli-shift rules. Besides introducing quasi-ergodicity, this paper answers several questions posed in the previous chapters of our quest. To start with, we offer a rigorous explanation of the fractal behavior of the time-1 characteristic functions, finding the equations that describe this phenomenon. Then, we propose a classification of rules according to the presence of Isles of Eden, and prove that only 28 local rules out of 256 do not have any of them; this result sheds light on the importance of Isles of Eden. A section of this paper is devoted to the characterization of Bernoulli basin-tree diagrams through modular arithmetic; the formulas obtained allow us to shorten drastically the number of cases to take into consideration during numerical simulations. Last but not least, we present some theorems about additive rules, including an analytical explanation of their scale-free property.