{'fraction_non_alphanumeric': 0.040659728347151175, 'fraction_numerical': 0.018345387193508554, 'mean_word_length': 4.205846342209979, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Full Computation-relevant Topological Dynamics Classification of Elementary Cellular Automata

Cellular automata are both computational and dynamical systems. We give a complete classification of the dynamic behaviour of elementary cellular automata (ECA) in terms of fundamental dynamic system notions such as sensitivity and chaoticity. The"complex"ECA emerge to be sensitive, but not chaotic and not eventually weakly periodic. Based on this classification, we conjecture that elementary cellular automata capable of carrying out complex computations, such as needed for Turing-universality, are at the"edge of chaos".

In the rich classical history of the theory of computation, models of computation were typically compared to the Turing machine concept, which allows us to characterize their computational power in great detail. 1,2 If, however, one would like to ascribe "computational" capacity to processes and systems observed in nature, one is naturally pushed toward using dynamical systems notions as the natural framework, leaving the problem open of how to fit this approach into, or how to link this approach with, Turing computation. A paradigmatic class of systems that comprise in a generic manner both computational and dynamical system aspects are the cellular automata (CA). While CAs are defined as a class of discrete dynamical systems, they also serve as a mathematical model of massively parallel computation, a paradigm often observed when "nature computes". Remarkably, already very simple rules make CAs computationally universal, i.e. capable of carrying out arbitrary computational tasks. By clarifying the dynamical system properties of the most popular and best-studied subclass of CA, the so-called elementary cellular automata (ECA), we will contribute here to a more profound understanding of CA as both computational and dynamical systems. We will fully classify the dynamic behavior of ECA using exclusively topological dynamics attributes such as sensitivity and chaos. Based on this classification, we will finally conjecture that the computationally most complex and biologically relevant ECA are those located at the "edge of chaos".

I. INTRODUCTION
By definition, CA are discrete dynamical systems acting in a discrete space-time. The state of a CA is specified by the states of the individual cells of the CA, i.e. by the a) schuelem@ini.phys.ethz.ch values taken from a finite set of states associated with the sites of a regular, uniform, infinite lattice. The state of a CA then evolves in discrete time steps according to a rule acting synchronously on the states in a finite neighbourhood of each cell. Despite the simplicity of these rules, CA can exhibit strikingly complex dynamical behaviour. A well-known example of a CA with intricate dynamics is the so-called Game of Life. CA have also been extensively applied as models for a wide variety of physical and biological processes. Obtaining a dynamical system classification of ECA is part of the long-standing problem in CA theory to characterise the "complexity" seen inherent in CA behaviour. In a series of influential papers, Wolfram studied the dynamical system and statistical properties of CA and devised a classification scheme. [4][5][6] According to this scheme, CA behaviour can be divided into the following classes: (W1) almost all initial configurations lead to the same fixed point configuration, (W2) almost all initial configurations lead to a periodic configuration, (W3) almost all initial configurations lead to random looking behaviour, (W4) localized structures with complex behaviour emerge. Wolfram's classification attempt was largely based on simulations of ECA. Since his pioneering work many more classification schemes have been proposed, e.g. by Li et al. 7 or Culik et al. 8 It is however still an open problem of CA theory to obtain a completely satisfying, formal classification of CA behaviour.
In this paper, we will put forward a complete topological dynamics classification of ECA. Our approach is based on the symbolic dynamics treatment of CA initiated by the seminal paper of Hedlund. 3 The topological dynamics approach allows to use the fundamental notions of dynamics system theory such as sensitivity, chaos, etc. More specifically, the classification is based on a scheme, introduced by Gilman 9 and modified by Kurka 10 , which proposes four classes: Equicontinuous CA, CA with some equicontinuous points, sensitive but not positively expansive CA and positively expansive CA. Each one-dimensional CA belongs to exactly one class, but class membership is generally not decidable. 10 We arXiv:1107.2080v8 [nlin.CG] 20 Feb 2013 determine for every ECA, as far as we know for the first time, to which class it belongs. We also (re-)derive further properties such as surjectivity and chaoticity of ECA. Taken together this gives a fairly complete picture of the dynamical system properties of ECA.
The paper is organised as follows. In Sect. II, we introduce one-dimensional CA and ECA formally. In Sect. III, we give basic notations and definitions of the topological dynamics approach to CA. In Sect. IV, we introduce a scheme that allows to express ECA rules algebraically. This will prove helpful in Secs. V and VI, where we will classify ECA in the topologically dynamics sense of Kurka. In Sect. VII, we discuss our results.

II. DEFINITION OF ELEMENTARY CELLULAR AUTOMATA
We start with the definitions of the basic concepts underlying the theory of one-dimensional CA. The configuration of a one-dimensional CA is given by the doubleinfinite sequence x = (x i ) i∈Z with x i ∈ S being elements of the finite set of states S = {0, 1, ...}. The configuration space X is the set of all sequences x, i.e., X = S Z . The CA map F , simply called the CA F , is a map F : X → X where the local function is the map f : The integer r is called the radius of the CA. The iteration of the map F acting on an initial configuration x generates the orbit The orbits of all configurations x are a discrete space-time dynamical system also referred to as CA F . Instances of the system can be visualised in so-called space-time patterns.
A spatially periodic configuration is a configuration which is invariant under translation in space, that is, x is periodic if there is q > 1 such that σ q (x) = x where σ : X → X is the shift map σ(x) i = x i+1 . A temporally periodic or simply periodic configuration x for some CA F is given if F n (x) = x for some n > 0. If F (x) = x, x is called a fixed point. A configuration x is called eventually periodic, if it evolves into a temporally periodic configuration, i.e. if F k+n (x) = F k (x) for some k ≥ 0 and n > 0. If this holds for any configuration x, the corresponding CA is called eventually periodic.
An elementary cellular automaton (ECA) is an onedimensional CA with two states and "nearest neighbourhood coupling", that is, S = {0, 1} and r = 1. There are then 256 different possible local functions f : . Local functions are also called rules and usually given in form of a rule table. An example is: 111 110 101 100 011 010 001 000 0 1 1 0 1 1 1 0 Every ECA rule is, following Wolfram 4 , referred to by the sequence of the values of the local function, as given in the rule table, written as a decimal number. In the example above one speaks of ECA rule 110, because 01101110 written as a decimal number equals 110.

III. TOPOLOGICAL AND SYMBOLIC DYNAMICS DEFINITIONS AND CONCEPTS
The framework we use to study the dynamical properties of ECA is given by the symbolic dynamics approach that views the state space S Z of one-dimensional CA as the Cantor space of symbolic sequences. The topology of the Cantor space is induced by the metric Under this metric the configuration space S Z is compact, perfect and totally disconnected, i.e., a Cantor space. 11 From now on, the configuration space S Z endowed with this metric will be referred to as X. The ECA functions F are continuous in X, hence (X, F ) is a (discrete) dynamical system. Now we introduce some key concepts of the topological dynamics treatment of CA. A configuration x is an If all configurations x ∈ X are equicontinuity points then the CA is called equicontinuous. If there is at least one equicontinuity point, the CA is almost equicontinuous. A CA is sensitive (to initial conditions), if ∃ > 0, ∀x ∈ X, ∀δ > 0, ∃y ∈ X : d(x, y) < δ, ∃n ≥ 0 : d(F n (x), F n (y)) ≥ . ( A CA is positively expansive, if Positively expansive CA are sensitive 11 . If a configuration is an equicontinuity point, its orbit remains arbitrarily close to the orbits of all sufficiently close configurations. If a CA is sensitive, there exists for every configuration at least one configuration arbitrarily close to it such that the orbits of the two configurations will eventually be separated by some constant. Positive expansivity is a stronger form of sensitivity: the orbits of all configurations that differ in some cell will eventually be separated by some constant. The long term behaviour of a sensitive CA can thus only be predicted if the initial configuration is known precisely. With these concepts, CA as dynamical systems can be classified according to a classification introduced by Gilman 9 and modified by Kurka 10 . Every onedimensional CA falls exactly in one of the following classes 10 : (K1) equicontinuous CA, (K2) almost equicontinuous but not equicontinuous CA, (K3) sensitive but not positively expansive CA, (K4) positively expansive CA.
The typical emergent dynamics of the different classes are illustrated by the space-time patterns of Figure 1. It has been shown that for one-dimensional CA it is not decidable whether a given CA belongs to class (K1), (K2) or (K3)∪(K4), whereas it is still open whether the class (K4) is decidable. 12 We will show that it can be determined to which class an ECA belongs.

IV. ALGEBRAIC EXPRESSIONS OF ELEMENTARY CELLULAR AUTOMATA RULES
Here, we devise an algebraic expression scheme for ECA. The main idea is to derive in a consistent way algebraic expressions for the local ECA rules from a Boolean function form of ECA rules. The algebraic expressions of ECA rules are of use in Secs. V-VI. Algebraic expressions of specific ECA rules have been derived earlier, usually for additive ECA rules. 13 For example, rule 90 is usually given as F (x) i = x i−1 + x i+1 mod 2. 11 Other approaches, e.g. by Chua 14 , do not yield the same simple polynomial forms as obtained below. The approach taken here was introduced earlier by the present authors 15 , where, to the best of our knowledge, for the first time simple, algebraic expressions were given for all ECA rules. Note that Betel and Flocchini used a similar approach in their study on the relationship between Boolean and "fuzzy" cellular automata. 16 The rule tables which define the ECA rules can be regarded as truth tables familiar from propositional logic. Any ECA rule hence corresponds to a Boolean function, which can always be expressed as a disjunctive normal form (DNF) (or a conjunctive normal form respectively). 17 The DNF of a Boolean function is a disjunction of clauses, where a clause is a conjunction of Boolean variables. Any ECA rule can thus be expressed as where X i+j are Boolean variables associated with the states of the cells in the neighbourhood of an ECA. For example the DNF expression of ECA rule 110 reads to: The representation of ECA rules in DNF is well known and has e.g. been studied by Wolfram. 18 We may express now the Boolean operations (∧, ∨, ¬) arithmetically as We found it convenient to express the Boolean operations in this way, instead of using the more common modulo-2 operations. This replacement takes the Boolean algebra (A, ∧, ∨, ¬, 1, 0), with the set A = {0, 1}, into a Boolean ring (R, +, −, ·, 1, 0), with the set R = {0, 1} and the usual arithmetical operations.
Replacing the Boolean operations in the DNF expressions of ECA rules with their arithmetic counterparts yields, for all ECA, Boolean polynomials of the form with x i ∈ {0, 1} and α j ∈ Z. ECA rules are completely determined by the appropriate set of coefficients α j in expression (6). As examples we list here a few algebraic expressions of some interesting ECA rules.
Note how simple, for example, the algebraic expression of the "complex" ECA rule 110 is! It is well-known that the ECA rule space can be partitioned into 88 equivalence classes, because ECA rules are equivalent under the symmetry operations of exchanging left/right and 0/1 complementation. For the local func- For example, for ECA rule 110 the equivalent rules are: From now on we will use the lowest decimal ECA rule number present within the group to refer to the whole group. For example, referring to ECA rule 110 implies in this way the four rules {110, 137, 124, 193}.
Note that the approach developed here can be extended in various ways, for example to one-dimensional CA with state space {0, 1} with larger neighbourhood, or to two-dimensional CA with state space {0, 1}, etc.

V. CLASSIFICATION OF ELEMENTARY CELLULAR AUTOMATA
We will now classify ECA from their topological dynamics properties, that is, according to the scheme introduced by Gilman 9 and modified by Kurka 10 .
First, we need some more symbolic dynamics definitions and notions. A word u is a finite symbolic sequence u = u 0 ...u l−1 , with u i ∈ S, where S is a finite alphabet, e.g. in the case of ECA the state set {0, 1}. The length of u is denoted by l = |u|. The set of words of S of length l is denoted by S l , the set of all words of S with l > 0 is S + .  One-dimensional CA, and therefore ECA, are either sensitive or almost equicontinuous. The latter property is equivalent to having a blocking word: Proposition 1 (Kurka 11 ). For any one-dimensional CA F with radius r > 0 the following conditions are equivalent.
(2) F has an r-blocking word.
If a configuration x contains a m-blocking word u, then the sequence x [q,q+m) , i.e. the states of the cells in the segment [q, q + m), are at all times independent of the initial states outside of the blocking word u. Hence, the following corollary holds: For any one-dimensional CA F with radius r > 0 the following conditions are equivalent.
(1) F has a m-blocking word with m ≥ r.
Proof. (1) ⇒ (2): Denote the sequence x [q,q+m) of a blocking word u that is at all times independent of the initial states outside of u by v. The configuration x = (u) ∞ is spatially periodic and hence eventually temporally periodic. Because the sequence v is independent of the states of the cells outside of u, the sequence v is also eventually temporally periodic.
(2) ⇒ (1): The condition (2) says that for all q+m) must be independent of the initial states outside of u, hence the word u is m-blocking.
We will now systematically search for blocking words. We know by proposition 1 that whenever a blocking word can be found, the corresponding ECA is almost equicontinuous. By corollary 2, we know that this corresponds to finding a word u that contains a sequence that is eventually temporally periodic, independent of the initial states outside of u. As it turns out, we can thereby effectively determine all almost equicontinuous ECA, because any almost equicontinuous ECA corresponds to a blocking word u for which the length l = |u| is bounded.
Proposition 3. Each almost equicontinuous ECA has at least one blocking word of length l ≤ 4.
Proof. In the following, we look for blocking words, starting with the smallest possible length l = 1 and then successively for words of greater length (for a visualisation of the definition of a blocking word see again Figure 2). If a blocking word can be found, one or several almost equicontinuous ECA rules will satisfy the blocking conditions. The ECA rules are specified by a rule table which we denote by (t 0 , t 1 , t 2 , t 3 , t 4 , t 5 , t 6 , t 7 ). For example, ECA rule 110 is given by the table (0, 1, 1, 0, 1, 1, 1, 0). If an entry in the rule table is left unspecified, the entry can take on either of the two values 0 or 1, e.g. the table (0, 1, 1, 0, 1, 1, 1, t 7 ) refers to the two ECA rules 110 and 111. If a blocking word can be found, we put the ECA rule table admitted by the blocking conditions in a list. A blocking word u and the admitted rule table is denoted by , where p is the period with which the eventually periodic sequence in the word u (i.e. the sequence x [q,q+m) referred to in corollary 2) is repeated. For example, t(00, 1) = (t 0 , t 1 , t 2 , 0, t 4 , t 5 , 0, 0) refers to the blocking word 00 of period p = 1 that corresponds to 2 5 = 32 ECA rules, as denoted by the rule table. If a newly found blocking word admits ECA rules generated by a rule table obtained by a blocking word already in the list (hence of smaller length), the word and the rule table admitted by it is not listed. We also do not list blocking words, and the rule tables admitted by them, if they correspond to ECA rules equivalent to ECA rules admitted by a blocking word already in the list.
Let us further assume the following notation: The variable c i always denotes the states of cells i of a blocking word u that are at all times independent of the initial states of the cells outside of the blocking word u. The variable x i on the other hand denotes the states of cells i that are in principle influenceable by the initial states of the cells outside of u. The state x i of such a cell i is left undetermined, i.e. the value can either be 0 or 1. If it is known for configurations x, y ∈ [u] 0 that the states x i and y i of some cell i differ, we writex i . For example, the "scenario"x −1 c 0x1 x −1 c 0 x 1 refers to two configurations x, y ∈ [u] 0 that share the blocking word u = c 0 of length l = 1 that is repeated with period p = 1. At the boundaries of the blocking word u, here at the cells i = −1 and i = 1, we can assume that the configurations x and y differ, which is denoted byx −i andx i , whereas in the next time step this may not necessarily be the case anymore (at the cells i = −1 and i = 1). The proof has two parts. In part A, we determine all blocking words of length l ≤ 4. In part B, we show that for any blocking word u of length l > 4 there is a corresponding blocking word of length l ≤ 4.
Part A: Let us look at the cases (a) l = 1, (b) l = 2, (c) l = 3 and (d) l = 4, where l, as said, denotes the length of a blocking word u.
Case (1) yields blocking words already listed, because for l > 4 the conditions to be satisfied in order to obtain a blocking word u are entailed in the conditions to obtain a blocking word u with l ≤ 4. The same reasoning applies to cases (2), (3) and (4). The basic reason that such a reduction is possible is due to the fact that the conditions to be satisfied in order to obtain a blocking word depend on the values of the boundary cells, here the valuesx −1 andx l (respectively the valuesx q−1 andx q+m in cases (3) and (4)), but not on the values of the cells to the left (of i = −1) and right (of i = l) of the boundary cells, as can be checked with the scenarios treated in Part A.
Let us then look closer at case (5). We will show that if there is a blocking word c 1 c 2 ...c l−2 c l−1 , the word is repeated with period p = 2, because if the word is blocking, the word at the next time step (in case (5)) must bec 1c2 ...c l−2cl−1 . The bar signifies that the state c i of the cell i must change, i.e.c i = (1 − c i ). Without loss of generality, we can consider only the 2 4 boundary conditions for blocking words at successive time steps. That is, given the word c 1 c 2 ...c l−2 c l−1 , we consider at the next time-step all the (2 4 − 2) possible cases: c 1 c 2 ...c l−2cl−1 , c 1 c 2 ...c l−2 c l−1 , etc., excluding the two cases c 1 c 2 ...c l−2 c l−1 andc 1c2 ...c l−2cl−1 . It suffices to consider the case c 1 c 2 ...c l−2cl−1 . The other cases can be dealt with analogously. The temporal evolution of the ECA generates in this case the following scheme: The superscript denotes the time-step n. The third, fifth and sixth line are due to the fact that if the state of e.g. the cell l − 2 at time step n = 2 did not change, one would obtain a blocking word of shorter length (l − 1). By checking all 2 4 possible values for the boundary states of the initial word c 1 c 2 ...c l−2 c l−1 it can be shown that the above scheme cannot be satisfied. Thus, any initial word c 1 c 2 ...c l−2 c l−1 evolves in the next time step into either the word c 1 c 2 ...c l−2 c l−1 or the wordc 1c2 ...c l−2cl−1 . In the first case, a blocking word of period p = 1 is found, in the second case, i.e. for p = 2, one can find a blocking word of length l = 2, as can easily be shown. The case (6) can be reduced to the case already treated under (a (8)) in Part A, the case (7) to the case (5) and the case (8) again to the case treated under (c (2)) (or the example in (d) respectively) in Part A.
With this we conclude our analysis. In Part A, we have identified all blocking words of length l ≤ 4. For l ≥ 2, we omitted, for reasons of space, the presentation of the cases that do not lead to blocking words or to blocking words already identified. In Part B, we have concluded from the cases for l ≤ 4 on the general form of the scenarios that could possibly lead to blocking words for l > 4. These general scenarios could then be reduced to the scenarios obtained for l ≤ 4. One case (case (5)) required a separate treatment and was analysed by means of an example.
To arrive at a complete list of blocking words for l ≤ 4 and to exclude additional blocking words for l > 4, great care and efforts have been invested. We have tested the completeness of the list also by extensively sampling the space of initial configurations for ECA, which yielded no additional blocking words. One may also check the correctness and completeness of the cases investigated in our analysis by hand with the help of a computer, running a program that follows the lines of the proof above. Alternatively, to demonstrate the impossibility of additional blocking words, the systems of equations generated from the conditions for blocking words and the algebraic expressions of ECA rules could be used, systematically evaluated for each single case.
The class of sensitive ECA is large, because in the Cantor space left-or right-shifting rules are sensitive. We will later return to this point.
From the almost equicontinuous ECA rules, we can further specify the equicontinuous ones. We use the following lemma.
Lemma 7 (Kurka 11 ). A one-dimensional almost equicontinuous CA F is equicontinuous if and only if: (1) There exists a preperiod m ≥ 0 and a period p > 0, such that F m+p = F m .
It is almost equicontinuous but not equicontinuous if and only if: (2) There is at least one point x ∈ X for which the almost equicontinuous CA F is not equicontinuous. Proof. The proof is by showing that condition (1) of Lemma 7 holds. We only give an example for a specific ECA rule. Rule 72 is equicontinuous with preperiod m = 2 and period p = 1, because, by using the algebraic expression for the local function, we obtain Proof. The proof is by showing that condition (2) of Lemma 7 holds. We only give an example for a specific ECA rule.
ECA rule 104 is almost equicontinuous but not equicontinuous, because (10) ∞ is not an equicontinuous point. Assume the configuration x = (10) ∞ and an integer q > 0 such that Assume that y differs from x at cells (−q − 1) and (q + 1), that is y −q−1 = 1 − x −q−1 and y q+1 = 1 − x q+1 . Then, as can easily be shown by using the algebraic expression of ECA rule 104, for all n ≤ q. Hence, ECA 104 is not equicontinuous at the point x = (10) ∞ .
From the sensitive ECA, we can distinguish further the positively expansive ECA.
We will use the following lemma: Lemma 10 (Kurka 11 ). A one-dimensional CA F is positively expansive if the following condition holds.
(1) The CA is both left-and right-permutive.
A one-dimensional sensitive CA F is not positively expansive if and only if the following condition holds.
(2) There is no > 0 such that for all x = y ∈ X there is n ≥ 0 with d(F n (x), F n (y)) ≥ .
Proposition 11. The following ECA rules are sensitive but not positively expansive: 2, 3, 6, 7, 9, 10, 11, 14, 15, 18, 22, 24, 25, 26, 27,  Proof. The proof is by showing that condition (2) of Lemma 10 holds. We only provide the example of a specific ECA rule. ECA rule 110 is sensitive but not positively expansive. Assume the expansivity constant = 2 −m , then must hold. Assume the configuration x = (00110111110001) ∞ and an integer q > 0 such that 14q > m. Then, for a configuration y ∈ X that differs from x at the cells 14q, 14q + 1, 14q + 2, (7) does not hold. Note that Proposition 13 does not hold generally for one-dimensional CA. 11 We summarize the findings of this section in Table I, which shows all ECA rules according to whether they have the property of equicontinuity, almost equicontinuity, sensitivity or positively expansivity.
A configuration x is called weakly periodic, if there is q ∈ Z and p > 0 such that F p σ q (x) = x. 19 We define a configuration x as eventually weakly periodic if there is q ∈ Z and n, p > 0 such that F n+p σ q (x) = F n (x). We call an ECA eventually weakly periodic, if the ECA is not eventually periodic, but for all configurations x eventually weakly periodic. Proof. The general proof follows the argument exhibited for a specific ECA rule as follows.
Employing the algebraic expression for ECA rule 10, it can easily be shown that F 2 σ −1 (x) = F (x) for all configurations x. Hence, ECA rule 10 is eventually weakly periodic with n = 1, p = 1 and q = −1.
The classification of eventually weakly periodic ECA maps is not complete yet. There might be sensitive ECA which are eventually weakly periodic, but with such large n or p that prevents calculating the forward orbits as easily as in the proof of Proposition 14.
Surprisingly, some of the eventually weakly periodic ECA are also chaotic (but not positively expansive), while others are sensitive, but not chaotic. For this statement, we adhere to the standard definition of (topological) chaos given by Devaney 20 . A map F : X → X is chaotic, if F is sensitive, transitive and if the set of periodic points of F is dense in X. The class of chaotic ECA has already been determined by Cattaneo et al. 21 ; for the sake of completeness, we rederive the result below.
First, we shall study the surjectivity property shared by some ECA maps F . For sensitive ECA F , surjectivity is already sufficient to establish the transitivity of F and the density of periodic points in X under F , so that the chaoticity of F is implied.
A CA is surjective if and only if it has no Garden-of-Eden configurations, that is configurations which have no pre-image. A necessary (but not sufficient) condition for surjectivity is that the local rule is balanced. 11 For ECA rules this means that the local rule table contains 4 zeros and 4 ones. Further, any permutive CA is surjective. 11 Proposition 15. The following ECA rules are surjective: 15, 30, 45, 51, 60, 90, 105, 106, 150, 154, 170, 204. Proof. Apart from rule 51 and rule 204, the above listed rules are permutive, hence surjective. Rule 51 and rule 204 are surjective, because they are, trivially, bijective. For the ECA rules that are not listed, but satisfy the balance condition, it can be shown that they possess Garden-of-Eden configurations. For example, ECA rule 184 satisfies the balance condition, nevertheless it is not surjective, because any configuration containing pattern (1100) is a Garden-of-Eden as can easily be shown.
Next, we show that for ECA transitivity is equivalent to permutivity. An one-dimensional CA F is transitive if for any nonempty open sets, U, V ⊆ X there exists n > 0 with F n (U ) ∩ V = ∅. Proof. Transitivity of one-dimensional CA implies its surjectivity and sensitivity 11 . From Proposition 6 and 15 and the definition of permutivity, we gain that ECA that are surjective and sensitive are permutive. Conversely, permutive ECA are surjective 11 . From the surjective ECA that are sensitive (the surjective ECA rules 51, 204 are not sensitive, hence not transitive), the positively expansive ECA are permutive and transitive 11 . The ECA rules 15 and 170 are also permutive and transitive. Rule 106 is permutive and has been shown transitive 11 . Proofs of the transitivity of the remaining permutive and sensitive rules 30, 45, 60, 154 can be similarly constructed. The distinction between the chaotic and non-chaotic ECA is not necessarily seen in the space-time patterns. The eventually weakly periodic ECA that are chaotic and the eventually weakly periodic ECA that are sensitive but not chaotic both show similar "travelling wave" patterns. The difference between the chaotic ECA and the sensitive but not chaotic ECA is not in the space-time patterns they generate, but in how they react to perturbations.
While the eventually weakly periodic ECA show too simple behaviour to be called "complex", chaotic ECA are in a sense "too complex": their mixing properties do no allow for the memory capacities apparently needed for "complex" behaviour. In the following final section we will expand on this observation. Figure 4 summarises the results of our analysis.

VII. DISCUSSION
The results of this paper show that one can classify the dynamic behaviour of every elementary cellular automaton (ECA) in terms of the standard notions of dynamical system theory, that is, according to the classification proposed by Gilman 9 and Kurka 10 . We also determined which ECA are chaotic in the sense of Devaney, rederiving a result by Cattaneo et al. 21 This gives a fairly complete picture of the dynamical system properties of ECA in the standard topology, as summarised in Fig. 4. The topological dynamics approach to CA thus delivers a relevant and coherent account of the dynamical behaviour of ECA.
In the light of our results, the class of "complex" ECA can be characterised as those ECA that are sensitive, but not surjective, and not eventually weakly periodic. This class corresponds well to what one would intuitively regard as "complex", given the space-time patterns of ECA. In particular, the ECA rules of Wolfram's class (W4) seem to fall into this class.
Among the ECA rules, a few deserve special interest from a computational point of view. The most prominent example is ECA rule 110 which has been shown to be computationally universal. 23 Based on our results we conjecture that sensitivity is a necessary condition of computational universality. In contrast, Wolfram conjectured that, for example, ECA rule 73, which is not sensitive, may be computationally universal. 18 This difference is due to the fact that our results hold generally for ECA without any restrictions on the initial conditions, whereas Wolfram considers specific sets of initial configurations on which the rule acts. On such a restricted set of configurations, ECA rule 73 might indeed be sensitive.
If a CA is sensitive, then its dynamics defies numerical computation for practical purposes, because a finite precision computation of an orbit may result in a completely different orbit than the real orbit. Hence, while sensitivity seems inherent to the in principle computationally most powerful rules, as e.g. rule 110, their limited robustness to small changes in the initial conditions may impair their practical usage in a physical or biological system: Even a single bit-flip in the input of a sensitive ECA may completely change the computed output.
Among the many questions left open, a natural extension of our study would consist in giving a complete characterisations in the topological dynamics sense for more general CA than ECA. Examples by Cattaneo et al. 21 , however, show that the approach taken here to establish chaoticity can already fail in slightly more general settings. In the general case, long-term properties of CA and hence classification schemes based on these properties are typically undecidable. It would therefore be useful to pinpoint where exactly undecidability enters.
Establishing a verifiable notion of computational universality in the Turing-machine sense in terms of necessary and sufficient conditions related to the dynamic behaviour of the underlying system would greatly advance our understanding of the relation between computational and dynamic properties of physical and biological systems. Part of the problem to clarify this relation is that there is no unanimous accepted definition of computational universality for computational systems such as CA (see e.g. the discussion by Ollinger 24 and Delvenne et al. 25 Delvenne et al. also prove necessary conditions for a symbolic system to be universal, according to their definition of universality, and demonstrate the existence of a universal and chaotic system on the Cantor space.). To different definitions of universality, there might thus correspond different topological dynamics properties. Despite this fact, we conjecture that for ECA sensitivity and non-surjectivity are necessary conditions of universality. This conjecture is in accordance with the intuitive idea that systems at the "edge of chaos", i.e. systems with neither too simple nor chaotic dynamical behaviour, are the computationally relevant systems for biology. Such intermittent systems have, moreover, been characterised as having the largest complexity in the sense that their behaviour is the hardest to predict. 26 If computation is measured as a reduction of complexity 27 , the intermittent systems may then be said to provide the complexity needed for efficient computations.
The extension of the results and observations from ECA to general one-dimensional CA or higherdimensional CA is thus not without problems. Being much more tractable, ECA provide an important benchmark to test ideas on universality, the "edge of chaos" hypothesis and, generally, on how "computation" occurs in nature.