Narrow Results

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.

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.