Search

We study two-dimensional cellular automata, each cell takes three states: resting, excited and refractory. A resting cell excites if the number of excited neighbors lies in a certain interval (excitation interval). An excited cell becomes refractory independently on states of its neighbors. A refractory cell returns to a resting state only if the number of excited neighbors belong to recovery interval. The model is an excitable cellular automaton abstraction of a spatially extended semi-memristive medium where a cell's resting state symbolizes low-resistance and refractory state high-resistance. The medium is semi-memristive because only transition from high- to low-resistance is controlled by the density of local excitation. We present a phenomeno-logical classification of the automata behavior for all possible excitation intervals and recovery intervals. We describe eleven classes of cellular automata with retained refractoriness based on the criteria of space-filling ratio, morphological and generative diversity, and types of traveling localizations. [ABSTRACT FROM AUTHOR]

Over the past eight years, we have studied one of the simplest, yet extremely interesting, dynamical systems; namely, the one-dimensional binary Cellular Automata. The most remarkable results have been presented in a series of papers which is concluded by the present article. The final stop of our odyssey is devoted to the analysis of the second half of the 30 Bernoulli στ-shift rules, which constitute the largest among the six groups in which we classified the 256 local rules. For all these 15 rules, we present the basin-tree diagrams obtained by using each bit string with L ≤ 8 as initial state, a summary of the characteristics of their ω-limit orbits, and the space-time patterns generated from the superstring. Also, in the last section we summarize the main results we obtained by means of our "nonlinear dynamics perspective". [ABSTRACT FROM AUTHOR]

More than one third of the 88 globally-independent Cellular Automata rules exhibit robust simple Bernoulli-shift dynamics. Among them we find rule $\kern.5pt{\fboxsep2pt\fbox{170}}\kern.5pt\xspace$, which we proved to be chaotic in the previous episodes of our chronicle, and rule $\kern.5pt{\fboxsep2pt\fbox{184}}\kern.5pt\xspace$, the famous global majority rule. Therefore, we cannot overstate the importance of the Bernoulli στ-shift rules which we will present in two parts of our continuing odyssey on the Nonlinear Dynamics Perspective of Cellular Automata. This paper covers the first 15 of the 30 Bernoulli στ-shift rules. In this paper, after recalling the main concepts of Bernoulli rules — such as the role of the three Bernoulli parameters σ, τ and β — we will display the basin tree diagrams of these rules together with a convenient summary of the results extracted from them. Then, we will show that the superstring is an excellent testing signal to find the robust behavior of a given rule. Finally, we will conclude this paper with a discussion about the difference between robust and nonrobust ω-limit orbits of the Bernoulli στ-shift rules. [ABSTRACT FROM AUTHOR]

This 12th part of our Nonlinear Dynamics Perspective of Cellular Automata concludes a series of three articles devoted to CA local rules having robust periodic ω-limit orbits. Here, we consider only the two rules, $\kern.5pt{\fboxsep2pt\fbox{131}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{133}}\kern.5pt\xspace$, constituting the third of the six groups in which we classified the 1D binary Cellular Automata. Among the numerous theoretical results contained in this article, we emphasize the complete characterization of the ω-limit orbits, both robust and nonrobust, of these two rules and the proof that period-3 and period-6 ω-limit orbits are dense for $\kern.5pt{\fboxsep2pt\fbox{131}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{133}}\kern.5pt\xspace$, respectively. Furthermore, we will also introduce the fundamental concepts of perfect period-T orbitsets and riddled basins, and see how they emerge in rule $\kern.5pt{\fboxsep2pt\fbox{131}}\kern.5pt\xspace$. As stated in the title, we also focus on permutive rules, which have been introduced in a previous installment of our series but never thoroughly studied. Indeed, we will review some of the well-known properties of such rules, like the surjectivity, examining their implications for finite and bi-infinite Cellular Automata. Finally, we propose a new list of the 88 globally-independent local rules, which is slightly different from the one we have used so far but has the great advantage of being selected via a rigorous methodology and not an arbitrary choice. For the sake of completeness, we display in the appendix the basin tree diagrams and the portraits of the ω-limit orbits of the rules from this refined table which have not yet been reported in our previous articles. [ABSTRACT FROM AUTHOR]

In this paper, we design a cellular automaton and a discrete-time cellular neural network (DTCNN) using nonlinear passive memristors. They can perform a number of applications, such as logical operations, image processing operations, complex behaviors, higher brain functions, RSA algorithm, etc. By modifying the characteristics of nonlinear memristors, the memristor DTCNN can perform almost all functions of memristor cellular automaton. Furthermore, it can perform more than one function at the same time, that is, it allows multitasking. [ABSTRACT FROM AUTHOR]

The 11th part of our tour through one-dimensional binary Cellular Automata concerns period-2 rules, which form the second group in our classification of the 88 globally-independent CA rules according to the properties of their periodic orbits. In this article, we display the basin tree diagrams of all period-2 rules along with their time-2 characteristic functions, and then we prove that all rules belonging to group 2 have robust period-2 ω-limit orbits for any finite, and infinite, bit string length. This rigorous result, which pairs with the one about period-1 rules given in the tenth installment of our chronicle, confirms what we stated about period-2 rules on the basis of empirical evidence. In the second part of this tutorial, we introduce the notion of quasi global-equivalence and prove that there are only 82 quasi globally-independent CA rules. For the first time, we show that the space-time patterns of globally-independent local rules can depend on each other, and we present an example of quasi-global transformation. We also define the super string 턞, and its unique decimal representation x턞, dubbed the super decimal, which provides a completely transparent yet rigorous proof that rule $\kern.5pt{\fboxsep2pt\fbox{170}}\kern.5pt\xspace$ is chaotic when L → ∞. Moreover, we present the basin tree generation formulas, which uncover the analytical relationships between basin trees of globally-equivalent rules. Last but not least, for pedagogical and epistemological reasons, we conclude this paper with the selection of rule$\kern.5pt{\fboxsep2pt\fbox{137}}\kern.5pt\xspace$, instead of rule $\kern.5pt{\fboxsep2pt\fbox{110}}\kern.5pt\xspace$, as the prototypic universal Turing machine for our future discourse. [ABSTRACT FROM AUTHOR]

This stage of our journey through the universe of one-dimensional binary Cellular Automata is devoted to period-1 rules, constituting the first of the six groups in which we systematized the 88 globally-independent CA rules. The first part of this article is mainly dedicated to reviewing the terminology and the empirical results found in the previous papers of our quest. We also introduce the concept of the ω-limit orbit with the purpose of linking our work to the classical theory of nonlinear dynamical systems. Moreover, we present the basin tree diagrams of all period-1 rules — except for rule $\kern.5pt{\fboxsep2pt\fbox{0}}\kern.5pt\xspace$, which is trivial — along with their Boolean cubes and time-1 characteristic functions. In the second part, we prove a theorem demonstrating that all rules belonging to group 1 have robust period-1 rules for any finite, and infinite, bit-string length L. This is the first time we give analytical results on the behavior of CA local rules for large values of L and, consequently, for bi-infinite bit strings. The theoretical treatment is complemented by two remarkable practical results: an explicit formula for generating isomorphic basin trees, and an algorithm for creating new periodic orbits by concatenation. We also provide several examples of both of them, showing how they help to avoid tedious simulations. [ABSTRACT FROM AUTHOR]

In this paper, we propose new difference equations which can generate the evolution rules of cellular automata. [ABSTRACT FROM AUTHOR]

The concept of isles of Eden when generalized from finite cellular automata to classical dynamical systems on ℝd calls the attention to the ZUK Theorem — Z for [Zubov, 1957], U and K for [Ura & Kimura, 1960] — a fifty years old and almost forgotten result in topological dynamics, a classification theorem for compact isolated invariant sets. We provide a simple proof and discuss various consequences including a new result on pointwise Liapunov functions. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 $\kern.5pt{\fboxsep2pt\fbox{60}}\kern.5pt\xspace$ has no Isles of Eden for all L, and that local rules $\kern.5pt{\fboxsep2pt\fbox{154}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{45}}\kern.5pt\xspace$ 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 $\kern.5pt{\fboxsep2pt\fbox{154}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{45}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$, as well as all invariant local rules, such as rules $\kern.5pt{\fboxsep2pt\fbox{170}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{240}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{15}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{85}}\kern.5pt\xspace$, subject to no constraints. [ABSTRACT FROM AUTHOR]

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 $\kern.5pt{\fboxsep2pt\fbox{30}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{110}}\kern.5pt\xspace$. 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 $\kern.5pt{\fboxsep2pt\fbox{90}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$. Such formulas led to the rigorous proof of several surprising periodicity constraints for rule $\kern.5pt{\fboxsep2pt\fbox{90}}\kern.5pt\xspace$, and to the discovery of a new global, quasi-equivalence class, defined via an alternating transformation. In particular, local rules $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$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 $\kern.5pt{\fboxsep2pt\fbox{90}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$. In particular, the period "T" of all attractors of rules $\kern.5pt{\fboxsep2pt\fbox{90}}\kern.5pt\xspace$, $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$, as well as of all isles of Eden of rules $\kern.5pt{\fboxsep2pt\fbox{105}}\kern.5pt\xspace$ and $\kern.5pt{\fboxsep2pt\fbox{150}}\kern.5pt\xspace$, increases linearly with unit slope, in logarithmic scale, with the length L. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 ${\fbox{170}}$ is equivalent globally to the classic "left-shift" Bernoulli map. Similarly, we prove the "left-copycat" local rule ${\fbox{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, b1 ≠ 0, where b1 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. [ABSTRACT FROM AUTHOR]

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 $\fbox{110}$, $\fbox{124}$, $\fbox{137}$, and $\fbox{193}$, and only these rules, exhibit a 1/f power spectrum. [ABSTRACT FROM AUTHOR]

We prove rigorously the four cellular automata local rules 110, 124, 137 and 193 have identical dynamic behaviors capable of universal computations. We exploit Felix Klein's remarkable Vier-ergruppe to partition the 256 local rules studied empirically by Wolfram into 89 global equivalence classes of which only 50 may exhibit complex dynamics. We define a 24-element rotation group which induces 30 local equivalence classes of nonlinear difference equations whose parameters can be mapped into each other among members of the same class. [ABSTRACT FROM AUTHOR]

Wolfram's celebrated three-input Cellular Automata is further developed and extended from the perspective of neural networks. A single explicit formula involving two nested absolute-value functions and eight adjustable parameters called synaptic weights, is presented. Such a neuron is proved to be universal by specifying the synaptic weights of all 256 local rules. Applying the nonlinear dynamics concepts developed from Part I of this multipart series of papers, we present the rational for partitioning the entire set of 256 local rules into 16 distinct gene families, each composed of 16 gene siblings. Such a partitioning allows us to explain, if not predict, the pattern features generated from each local rule. Finally, these 16 gene families of Cellular Automata rules are encoded onto a new compact and insightful representation called the "double-helix torus." [ABSTRACT FROM AUTHOR]

This tutorial provides a nonlinear dynamics perspective to Wolfram's monumental work on A New Kind of Science. By mapping a Boolean local Rule, or truth table, onto the point attractors of a specially tailored nonlinear dynamical system, we show how some of Wolfram's empirical observations can be justified on firm ground. The advantage of this new approach for studying Cellular Automata phenomena is that it is based on concepts from nonlinear dynamics and attractors where many fuzzy concepts introduced by Wolfram via brute force observations can be defined and justified via mathematical analysis. The main result of Part I is the introduction of a fundamental concept called linear separability and a complexity index κ for each local Rule which characterizes the intrinsic geometrical structure of an induced "Boolean cube" in three-dimensional Euclidean space. In particular, Wolfram's seductive idea of a "threshold of complexity" is identified with the class of local Rules having a complexity index equal to 2. [ABSTRACT FROM AUTHOR]

In this paper we analyze the replication properties of additive or parity Cellular Automata (CA). The objective of the paper is twofold. Firstly, to review and extend the existing results in the cases of one- and two-dimensional CA. Secondly, to report a general result that states the replication properties of an n-dimensional CA, whose evolution law depends on an arbitrary m number of neighbor cells. [ABSTRACT FROM AUTHOR]

This paper presents a novel approach for studying the relationship between the properties of isolated cells and the emergent behavior that occurs in cellular systems formed by coupling such cells. The novelty of our approach consists of a method for precisely partitioning the cell parameter space into subdomains via the failure boundaries of the piecewise-linear CNN (cellular neural network) cells [Dogaru & Chua, 1999a] of a generalized cellular automata [Chua, 1998]. Instead of exploring the rule space via statistically defined parameters (such as λ in [Langton, 1990]), or by conducting an exhaustive search over the entire set of all possible local Boolean functions, our approach consists of exploring a deterministically structured parameter space built around parameter points corresponding to "interesting" local Boolean logic functions. The well-known "Game of Life" [Berlekamp et al., 1982] cellular automata is reconsidered here to exemplify our approach and its advantages. Starting from a piecewise-linear representation of the classic Conway logic function called the "Game of Life", and by introducing two new cell parameters that are allowed to vary continuously over a specified domain, we are able to draw a "map-like" picture consisting of planar regions which cover the cell parameter space. A total of 148 subdomains and their failure boundaries are precisely identified and represented by colored paving stones in this mosaic picture (see Fig. 1), where each stone corresponds to a specific local Boolean function in cellular automata parlance. Except for the central "paving stone" representing the "Game of Life" Boolean function, all others are mutations uncovered by exploring the entire set of 148 subdomains and determining their dynamic behaviors. Some of these mutations lead to interesting, "artificial life"-like behavior where colonies of identical miniaturized patterns emerge and evolve from random initial conditions. To classify these... [ABSTRACT FROM AUTHOR]

The goal of this letter is to report a novel class of dynamical behaviors observed from a generalized cellular automata CNN [Chua, 1998] with piecewise-linear (PWL) cells. Starting from an almost homogeneous initial condition, self-making (autopoietic in the sense of [Varela et al., 1974]) patterns, reminiscent of simple living systems, emerge as a result of the nonlinear coupling among cells. Similar to patterns of organization characterizing living systems, our patterns display features such as growth, maturity and death. The discovery of such patterns was made possible via mutations in several piecewise-linear CNN cell realizations of the "Game of Life" [Conway, 1982]. [ABSTRACT FROM AUTHOR]

A new stand-alone complex system hardware emulator, called the Wolfram Machine, is introduced in this paper. The system is a programmable hardware cellular automaton able to emulate and show the outcome of all elementary cellular automata, allowing for their experimental analysis. The system consists of an LED matrix and a board equipped with a microcontroller. This simple low-cost system can be programmed to reproduce the complex behavior of Wolfram's cellular automata, ranging from periodic patterns to Turing machines and Isles of Eden. A complete gallery of experiments is included. [ABSTRACT FROM AUTHOR]

Introduces a structure called the simplicial cellular neural network (CNN). Use of any Boolean/Gray-level function of any number of variables; Analysis of circuit architectures for the implementation of the simplicial CNN based on resonant tunneling diodes; Application of a fully programmable CNN in a hardware platform based on nanoelectronic devices.