Cuong Le Van, Cermsem

CORE Raouf Boucekkine
email: boucekkine@core.ucl.ac.be.

Cagri Saglam

Cuong Le Van

Optimal control in infinite horizon problems : a Sobolev space approach

Keywords: Optimal control, Sobolev spaces, Transversality conditions, Order ideal

In this paper, we make use of the Sobolev space W 1,1 (R + , R n ) to derive at once the Pontryagin conditions for the standard optimal growth model in continuous time, including a necessary and sufficient transversality condition. An application to the Ramsey model is given.

We use an order ideal argument to solve the problem inherent to the fact that L 1 spaces have natural positive cones with no interior points.

Introduction

Typically, the first-order necessary conditions of optimization problems in continuous time, the so-called Pontryagin conditions, are established using variational methods. This kind of methods is for example used throughout the textbooks of [START_REF] Hadley | Variational methods in economics[END_REF] and [START_REF] Kamien | Dynamic optimization[END_REF], but it is indeed at the basis of optimal control theory as initially designed by [START_REF] Pontryagin | The mathematical theory of optimal processes[END_REF]. For a finite time horizon, the set of Pontryagin conditions include optimality conditions with respect to the control, state and co-state variables, plus the corresponding transversality conditions which depend on the assumptions on the time horizon and the terminal state. All these conditions can be identified using standard variational methods.

When the optimization time horizon goes to infinity, things become much more complicated. In particular, it turns out that while the usual Pontryagin conditions obtained for finite horizons with respect to the control, state and co-state variables are preserved, the transversality conditions cannot be safely extrapolated. As the horizon gets to infinity, it is quite easy to show (see for example [START_REF] Halkin | Necessary conditions for optimal problems with infinite horizon[END_REF]) that taking the limits of the transversality conditions obtained for finite time horizons is highly misleading. In particular, the traditional "economic" condition according to which the shadow price should go to zero as the time horizon goes to infinity was shown to be clearly erroneous in the case of non-discounted problems.

This has lead to a kind of split in the optimal control treatment under infinite horizons: while the Pontryagin conditions can still be obtained by variational methods, the transversality condition is obtained using another type of argument. This is for example true in the seminal paper of [START_REF] Michel | On the transversality condition in infinite horizon problems[END_REF], who concentrates on the necessary transversality condition part. Michel provides a fairly general inspection into this issue in the case of discounted problems (without a priori sign or concavity assumptions on the objective and state functions). In such a framework, he proves that the right necessary transversality condition when time tends to infinity is the limit of the maximum of the Hamiltonian going to zero. This extends the property valid in a finite horizon problem with free terminal time to the infinite horizon case. On the other hand, he shows that the this necessary condition implies the traditional "economic" transversality condition, mentioned above, provided the objective function is non-negative and if "enough possibilities of changing the state's speed exist indefinitely". [START_REF] Ye | Nonsmooth maximum principle for infinite horizon problems[END_REF] extends this analysis by allowing for the non-differentiability of the problem data and obtains the maximum principle in terms of differential inclusions in analogy to the finite horizon problem.

Unfortunately the resulting characterization of the cases where the "economic" transversality condition holds reveals unpractical. Alternative dualitybased theories for discounted problems were developed starting with Benveniste and Scheinkman (1982). Under some concavity conditions (needed to apply an envelop condition), [START_REF] Benveniste | Duality theory for dynamic optimization models of economics: The continuous time case[END_REF] establishes the necessity of the transversality condition, lim t→∞ [-v 2 (x (t) , .

x (t) , t)] x = 0 for the continuous time reduced form model:

max ∞ 0 v (x (t) , . x (t) , t) dt subject to x (0) = x 0 , (x (t) , . x (t)) ⊂ (R n ) 2 .
when the assumptions of non-negativity and integrability of v for all feasible paths are verified. [START_REF] Kamihigashi | Necessity of transversality conditions for infinite horizon problems[END_REF] generalizes this analysis by allowing for unbounded v with the assumptions of local boundedness of v 1 and v 2 and the existence of an open set that the optimal pair x * (t) , .

x * (t) belongs to and under which v (., ., t) is continuously differentiable. [START_REF] Long | A note on transversality conditions[END_REF] prove the necessity of a transversality condition of the

form lim t→∞ [x * (t) -x 0 ] [v 2 (x (t) , .
x (t) , t)] = 0 under the assumption that v is twice differentiable and the optimal pair belongs to the interior of a set

under (R n ) 2 .
This paper provides a simple and unified functional analysis argument to derive at once the Pontryagin conditions, including the transversality condition in infinite horizon problems. More specifically, we make use of the Sobolev space W 1,1 (R + , R n ), which appears to be quite natural to derive not only the convenient transversality conditions, but also the whole set of Pontryagin conditions. Our choice of the Sobolev space W 1,1 (R + , R n ) is relevant for many optimal growth models, e.g. the Ramsey model, in which the feasible capital paths are proved to belong to this space and the feasible consumption paths belong to L 1 (see Askenazy and Le Van, 1999, page 42). In addition to this crucial topological choice, our setting is based on an assumption (Assumption 4 in the text), which is close to the concept of supported control trajectories traditionally used in the optimal control literature (see for example, [START_REF] Peterson | A sufficient maximum principle[END_REF]. Combining this concept with the Sobolev space W 1,1 (R + , R n ) turns out to be a powerful tool to get through the problem very easily. In particular, we extract the usual transversality conditions as necessary optimality conditions, together and at the same time as the other Pontryagin conditions.

To our knowledge, the first analysis that uses Sobolev spaces in economics was [START_REF] Chichilnisky | Nonlinear functional analysis and optimal economic growth[END_REF]. She studies the problem of existence and the characterization of the solutions of optimal growth models in many sector economies.

In this context, the prices are continuous linear functionals defined on the space of consumption paths. Mathematically, the question turns out to be the existence of an appropriate continuous linear functional separating the set of feasible paths from the set of paths which yield higher utilities than the optimal one. In [START_REF] Chichilnisky | Nonlinear functional analysis and optimal economic growth[END_REF], the space of consumption paths on which the optimization is performed is the completion of L ∞ endowed with L 2 norms while the space of admissible capital paths is the completion of the space C 1 b of continuously differentiable and bounded functions endowed with the norm given by the scalar product:

(f, g) = ∞ 0 1 k D k f (t)D k g(t) e -rt dt.
The basic tool needed to prove the existence of competitive prices for optimal programs, the Hahn-Banach theorem, requires one of the convex sets being separated to have an interior or an internal point. However, all L p spaces with 1 ≤ p < ∞ have natural positive cones with no interior or internal points. To overcome this problem, the objective function being maximized is shown to be continuous in weaker L 2 topology. Another inconvenient feature of L 2 spaces is related to the fact that their topology is weaker. It creates a difficulty in having conditions on the utility function which yield L 2 -continuity of nonlinear objective functional, the discounted social utility of the stream of consumption.

As mentioned above, in contrast to the previous studies, we shall use Sobolev space W 1,1 (R + , R n ) . Nonetheless, as in the alternative approaches listed above, we still face the problem that the involved L 1 spaces have natural positive cones with no interior or internal points. In order to overcome this problem, we shall use the concepts of properness and order ideal. The notion of properness is proved to be very useful in analyzing the existence of equilibrium in Banach lattices or Riesz spaces (see the excellent survey of Aliprantis, Cornet and Tourky, 2002, and its references). The properness is a notion weaker than continuity. A complete characterization for strictly increasing separable concave functions in L p + is given in Araujo and Monteiro (1989). Le Van (1996) characterizes properness for separable concave functions in L p + without assuming monotonicity. Dana, Le Van and Magnien (1997) provides an existence theorem when the consumptions sets being the positive orthant of a locally convex solid Riesz space has an empty interior. They use the approach of Mas-Colell and Zame (1991) by considering an economy restricted to the order ideal generated by the total resource, which is dense in the initial consumption space. This suffices to obtain a quasi-equilibrium price which can be extended to a linear form in the initial topology by the properness of the every utility function.

The paper is organized as follows. Section 2 presents the considered optimization problem, and gives some preliminary definitions and assumptions needed to derive our necessary and sufficient transversality condition. Section 3 proves the latter condition in the described mathematical framework, yielding the main result in Theorem 1. Section 4 is an application to the Ramsey model.

Preliminaries

Let C 1 c (R ++ , R n ) denote the set of continuously differentiable functions from R ++ to R n with compact support. We have the following general definitions and notations.

Definition 1 The space W 1,1 (R + , R n ) is the space of functions, x ∈ L 1 (R + , R n ) such that there exists a function x ∈ L 1 (R + , R n ) that satisfies ∞ 0 xφ dt = - ∞ 0 x φ dt, ∀φ ∈ C 1 c (R ++ , R n ) .
In this case, x is called the derivative of x in the sense of distributions.

We recall some results that will be useful in our analysis (see [START_REF] Brezis | Analyse Fonctionelle: Théorie et applications, Collection Mathematiques appliquees pour la maitrise[END_REF] for the proofs, pp 119-148) about Sobolev space W 1,1 (R + , R n ) :

• W 1,1 (R + , R n ) is a Banach space for the norm: x W 1,1 = x L 1 + x L 1 . • If x ∈ W 1,1 (R + , R n )
, there exists a unique continuous mapping

∼ x on R + such that x = ∼
x almost everywhere.

• For all τ, τ ∈ R + ,

∼ x (τ ) - ∼ x (τ ) = τ τ x (t) dt and lim t→∞ ∼ x (t) = 0.
We consider a standard optimal control problem with an infinite horizon arising in dynamic models in continuous time:

max ∞ 0 u (x (t) , c (t)) e -rt dt subject to . x (t) = f (x (t) , c (t)) x (0) = x 0 where x (t) ∈ R n + and c (t) ∈ R m + .
We denote by E the space of functions from

R + to R n such that xe -rt ∈ W 1,1 (R + , R n ) . Let x E = ∞ 0 x e -rt dt + ∞ 0
x e -rt dt. By L 1 (e -rt ) , we define the set of functions such that xe -rt ∈ L 1 , for a given r > 0. Observe that x ∈ E implies x (t) e -rt → 0 when t → ∞.

Next we make the following assumptions.

Assumption 1 x ∈ E and c ∈ L 1 (e -rt ) .

Assumption 2 f and u are continuous and the derivatives f x , u x are continuous.

Assumption 3 If x * , c * are optimal then f x (x * , c * ) ∈ L 1 (e -rt ) and u x (x * , c * ) ∈ L 1 (e -rt ) .

The condition x (0) = x 0 must be understood in the sense that the unique continuous function

∼
x which is almost everywhere equal to x satisfies

∼ x (0) = x 0 .
Lemma 1 Let L : E → R + be defined by L (x) = x (0) . The mapping L is Lipschitzian.

Proof. See Bonnisseau and Le Van (1996).

Lemma 2 Let D : x (t) → Dx (t) = . x (t) . D is continuous from E into L 1 (e -rt ) .
Proof. It is easy.

Definition 2 A trajectory (x(t), c(t)), t ∈ [0, +∞) is admissible if x ∈ E, c ∈ L 1 (e -rt ) , satisfy the constraints . x (t) = f (x (t) , c (t))
x (0) = x 0 and if the integral in the objective function converges. A trajectory (x * (t), c * (t))

is an optimal solution if it is admissible and if the value of the objective function corresponding to any admissible trajectory is not greater than that of

(x * (t), c * (t)).
The optimization problem under consideration can be recast in the following form (P):

max U (x, c) = ∞ 0 u (x (t) , c (t)) e -rt dt subject to Dx = f (x, c) Lx = x 0
where U : E ∩ L 1 + (e -rt ) × L 1 (e -rt ) → R∪ {-∞} . We now set an assumption, which is most crucial to our analysis: Assumption 4 The optimal path is supported in the following sense. Let (x * (t) , c * (t)) be an optimal solution. There exist multipliers (a, q, λ)

∈ R + × L ∞ × R n such that: ∀x ∈ E ∩ L 1 + (e -rt ) , ∀c ∈ L 1 + (e -rt ) , aU (x * , c * ) -q (Dx * -f (x * , c * )) -λ (Lx * -x 0 ) ≥ aU (x, c) -q (Dx -f (x, c)) -λ (Lx -x 0 ) . (1)
Notice that Assumption 4 is supposed to characterize the optimal paths: to each optimal solution, we assume that we can always assign multipliers, as usual associated with the objective function and constraints of the optimization problem respectively, so that inequality (1) holds. Whether such multipliers do exist when an optimal path exists is addressed in Section 4 for the Ramsey case: We don't argue here that such a property is inherent to optimality whatever the characteristics of the optimal control problem under study. Our first aim is to show that putting such an assumption in an appropriately defined Sobolev space very easily gives the Pontryagin conditions, including the transversality condition, at once. Proving the existence of the multipliers introduced in Assumption 4 is another task, which will be dealt with later.

Before showing this, some comments on Assumption 4 are necessary. As to the originality of our approach, it is fair to mention that an assumption like our Assumption 4 is not that far from the definition of supported control trajectories used in [START_REF] Peterson | A sufficient maximum principle[END_REF] and more recently applied to a class of finite horizon optimal control problems by Carlson and Angell (1998). See for example Definition 5, page 76, in Carlson and Angell. As in the pioneering work of Peterson, the latter authors easily prove for a class of undiscounted optimization problems with finite horizon that a control-trajectory which is feasible and supported is necessarily optimal (Theorem 6, page 76). All these papers assume the existence of multipliers supporting the optimal trajectories in a sense fairly close to our inequality [START_REF] Aliprantis | Existence and optimality of equilibria[END_REF]. However, beside the fact that the statement of inequality (1) depends on the optimization problem under study, 1 there are two main differences between this approach and ours. First of all, the literature mentioned just above follows different optimality criteria, namely overtaking optimality, 2 which has a lot to do with the undiscounted nature of the Ramsey problems under consideration. Moreover, we know by the Halkin's counter-example that these undiscounted problems may not satisfy the usual transversality conditions. Therefore our framework and the associated optimality criterion (see Definition 2 above) are much better suited to the study of transversality conditions in economic problems.

Second, and more importantly, the treatment of the supporting function, q in our case, is far from similar, and it can, by no way, be the same because the involved functional spaces are completely different. Our application section provides an insightful constructive method to get the supporting function q, using the concept of order ideal in L 1 topology.

The next section gives the main results of the paper.

Main results

In this section, we shall show how our approach allows to derive properly and easily the Pontryagin conditions, and more importantly, it will be shown how it settles in a simple and natural way the problem of the necessity and sufficiency of the transversality condition for infinite horizon problems.

The next proposition can be viewed as a more accurate characterization of the supporting function q under assumptions 1 to 4.

Proposition 1 Let Assumptions 1-4 be satisfied. Assume that x * (t) > 0,

1 It depends notably upon the boundary conditions of the problem under study. ∀t. Then ∃ p ∈ L 1 such that:

au x (x * , c * ) e -rt + . p (t) + p (t) f x (x * , c * ) = 0, (2)
in the sense of distributions.

Proof. It is clear from (1) that one can write:

∀x ∈ E ∩ L 1 + (e -rt ) , a ∞ 0 [u (x * , c * ) -u (x, c * )] e -rt dt - ∞ 0 q (t) [Dx * -Dx] e -rt dt + ∞ 0 q (t) [f (x * , c * ) -f (x, c * )] e -rt dt -λ [x * (0) -x (0)] ≥ 0, (3) Let h (t) ∈ C 1 c (R + , R n ) . If x * (t)
> 0, ∀t, as x * (t) can be assumed to be continuous [recall that every element of the Sobolev space W 1,1 can be identified with a continuous function], we can choose µ sufficiently small such that x (t) = x * (t) + µh (t) ∈ E. We obtain:

∞ 0 au x (x * , c * ) e -rt h (t) dt- ∞ 0 q (t) e -rt . h (t) dt+ ∞ 0 q (t) e -rt f x (x * , c * ) h (t) dt = 0
and hence, with p (t) = q (t) e -rt ∈ L 1 ,

au x (x * , c * ) e -rt + . p (t) + p (t) f x (x * , c * ) = 0,
in the sense of distributions.

It is easy to see that equation ( 2) is indeed the Pontryagin condition with respect to the state variable. Notice that the derivation of such a result is done in a very elementary way within our functional framework. The derivation of the necessary transversality condition is even more elementary:

Corollary 1 Under the assumptions of Proposition 1, if an optimal solution (x * (t) , c * (t)) exists, then necessarily p (t) e rt ∈ L ∞ , with p(t) = q (t) e -rt , defined in Proposition 1. In particular, lim t→∞ p (t) = 0 , and

lim t→∞ p (t) (x * (t) -x 0 ) = 0.
The proof is trivial. In particular, the result of Long and Shimomura can be easily recovered. Indeed, knowing that p (t) x * (t) = q (t) e -rt x * (t) → 0 and p (t) → 0 as t→ ∞, we can derive directly lim t→∞ p (t) (x * (t) -x 0 ) = 0 , as a necessary optimality condition. A further characterization of the multiplier p(t) is also allowed.

Proof. ¿From (1), it can be noted that,

∀z ∈ L 1 + (e -rt ) , a ∞ 0 [u (x * , c * ) -u (x * , z)] e -rt dt + ∞ 0 p (t) [f (x * , c * ) -f (x * , z)] dt ≥ 0. (5)
Assume on the contrary, by continuity, au (x * (t) , c * (t)) e -rt +p (t) f (x * (t) , c * (t)) < au (x * (t) , c) e -rt +p (t) f (x * (t) , c) in some interval I around t with some positive constant c ≥ 0. Let c (t) = c * (t) , t / ∈ I and c (t) = c when t ∈ I. Note that c (t) ∈ L 1 + (e -rt ) . However, ( 5) is not satisfied leading to a contradiction.

We now move to the sufficiency part and prove among others that the previously derived transversality condition is sufficient for optimality under some conditions which are known in the optimization literature (see for example, [START_REF] Carlson | Infinite horizon optimal control: deterministic and stochastic systems[END_REF]. To this end, we use the Hamiltonian concept.

Assumption 5 Define the Hamiltonian

H (x, c, p, t) = u (x (t) , c (t)) e -rt + p (t) f (x (t) , c (t)) .
Suppose that , max c≥0 H (x, c, p, t) is concave in x and H (x * , c * , p, t) ≥ H (x * , c, p, t) , ∀c ≥ 0.

The next proposition shows the sufficiency of the transversality condition when Assumption 5 is added to our assumptions set.

Proposition 3 Under Assumptions 1-3 and Assumption 5, a sufficient condition for (x * (t) , c * (t)) to be optimal is p (t) e rt ∈ L ∞ .

Proof. By Assumption 5, the following holds for every T > 0 :

T 0 u (x * (t) , c * (t)) e -rt dt - T 0 u (x (t) , c (t)) e -rt dt ≥ p (T ) (x (T ) -x * (T )) .
By assumption, p (t) e rt ∈ L ∞ . We then have:

| p (T ) (x (T ) -x * (T ))| ≤ p (T ) e rT x (T ) e -rT + x * (T ) e -rT ≤ K x (T ) e -rT + x * (T ) e -rT .
Since x ∈ E and x * ∈ E, we get K x (T ) e -rT + x * (T ) e -rT → 0 as T → ∞. That ends the proof.

Along this section, we have shown how the Sobolev space topology choice simplifies greatly the analysis of the necessary and/or sufficient transversality condition. While the sufficiency part of our analysis relies on standard conditions, the necessary conditions part is not that standard, at least in the literature of transversality conditions. Clearly, the crucial part of our analysis is Assumption 4. We show in the next section how this assumption is checked in the Ramsey-like models using common tools in general equilibrium theory.

Application to the Ramsey Model

We consider the following usual type of Ramsey model:

max ∞ 0 u (c (t)) e -rt dt subject to c (t) + . x (t) ≤ f (x (t)) -δx (t) c (t) ≥ 0, ∀t x (t) ≥ 0, ∀t x (0) = x 0 > 0, is given.
under the following assumptions.

Assumption 6 u is C 1 , strictly concave, increasing with u (0) ≤ +∞.

Assumption 7 f is C 1 , strictly concave, increasing with f (0) > δ, f (0) < ∞, f (∞) = 0. Proposition 4 The optimal solution (x * (t) , c * (t)) satisfy x * ∈ W 1,1 ∩ L 1 + and c * ∈ L 1 + (e -rt ) .
Proof. See Askenazy and Le [START_REF] Askenazy | A model of optimal growth strategy[END_REF].

In accordance with this proposition, we can use W 1,1 ∩ L 1 + as the state space and L 1 + as the control space. Let X = W 1,1 ∩ L 1 + × L + has an empty interior. Hence, the direct application of the theorem V.3.1 of [START_REF] Hurwicz | Programming in linear spaces[END_REF] is not possible for proving the existence of the multipliers (a, q, λ) ∈ R + × L ∞ × R n associated with this problem. We then use the same approach as Mas-Colell and Zame (1991) and Dana, Le [START_REF] Dana | General equilibrium in asset markets with or without short-selling[END_REF]. We consider an order ideal which is dense in the original space. There we have the positive orthant of the order ideal with a nonempty interior for its lattice norm.

It is well known (see for example, Askenazy and Le [START_REF] Askenazy | A model of optimal growth strategy[END_REF], Proposition 5) that there exists α > 0 such that the optimal consumption path satisfies: together with the properness condition lead us to obtain that qy ≥ qv.

On the other hand, since c * + 1 µ (v + y) ≥ 0, we have also -qy ≥ qv.

Now, let y ∈ A ∩ I (c) . y + and y -belong to A ∩ I + (c) . We have qy + ≥ qv and -qy -≥ qv so that qy ≥ 2qv. We have proved that the linear form q is bounded from below in an open neighborhood of 0. Therefore, q is continuous on I (c) with the initial topology. Since I (c) is dense in L 1 , q has a unique extension in (L 1 ) = L ∞ .

2

 2 see for example, Carlson and Angell, 1998, Definition 19, page 85.

u

  (c (t)) e -rt dt subject to g (x, c) ≥ 0 Lx = x 0 where g (x, c) = f (x) -δx -c -Dx and Lx = x (0) . Note that g takes values in L 1 + and L 1

  c * (t) ≥ α, ∀t ≥ 0. Let c = c * and I (c) = {y ∈ L 1 : ∃µ > 0 s.t. |y| ≤ µc} . The ideal I (c) is dense for both the L 1 topology and for the weak topology (see Aliprantis, Brown and Burkinshaw, 1989, pages 103,104). We define on I (c) the norm . c : y c = inf {µ > 0 : | y| ≤ µc} . One can verify that the positive orthant of I (c) , I + (c) has nonempty interior for the topology defined by . c . More precisely, c ∈ int I (c) .

  Corollary 2 If c * (t) is piecewise continuous then

				. p (t) is piecewise contin-
	uous.
	Proof. Since p (t) ∈ L 1 , it follows from (2) that	. p (t) ∈ L 1 and hence,
	p (t) is continuous. This implies that	. p (t) is piecewise continuous.
	The next proposition gives the Pontryagin condition with respect to the
	control. Again, our approach allows for an almost immediate proof.
	Proposition 2 Let Assumptions 1-4 be satisfied. Assume that c * (t) is con-
	tinuous and hence,	. x	* (t) is continuous. Then we have, for any c ∈ R m + ,
	au (x

* (t) , c * (t)) e -rt +p (t) f (x * (t) , c * (t)) ≥ au (x * (t) , c) e -rt +p (t) f (x * (t) , c) .

As u is increasing by Assumption 6, along an optimal path, we have g (x * , c * ) = 0, i.e. g (x * , c * ) ∈ I + (c) . Consider the problem:

where one can now apply the Theorem V.3.1 of [START_REF] Hurwicz | Programming in linear spaces[END_REF] and obtain:

Now we shall prove that q is a continuous linear form on I (c) for the L 1norm topology. Since I (c) is dense in L 1 , it extends to a continuous form on L 1 for the L 1 -norm topology. To this end, we follow Dana, Le [START_REF] Dana | General equilibrium in asset markets with or without short-selling[END_REF] and utilize the notion of properness.

Since c * t ≥ α > 0, ∀t, it is clear that u (c * (t)) ∈ L ∞ . From Le Van (1996), U is proper at c * . Hence, there exists an open solid neighborhood of 0, denoted by A and a vector v ∈ L 1 + such that

Let y ∈ A ∩ I + (c) . There exists µ > 1 such that 0 ≤ y ≤ µ c = µc * .

Define z = (1/µ) y. We have c * + 1 µ (v -y) ≥ 0. By applying the inequality (6):


Eric Goles

Pedro Montealegre

Kévin Perrot

Guillaume Theyssier

On the complexity of two-dimensional signed majority cellular automata

Keywords: cellular automata dynamics, majority cellular automata, signed two-dimensional lattice, Turing universal, intrinsic universal, computational complexity

We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length.

Introduction

In this paper we study the dynamics of signed majority (synchronous) cellular automata in two dimensional regular grids with the von Neumann neighborhood. They are a particular case of threshold automata, i.e. each local function being a threshold one. Concretely, each cell carries a -1 or a 1 and evolves depending on whether the pondered sum of its neighbors is positive or not. This class contains the well-known majority vote (all positive weights) and minority vote (all negative weights) cellular automata [START_REF] Moore | Majority-vote cellular automata, ising dynamics, and pcompleteness[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority[END_REF]. We consider both uniform and non-uniform weights and distinguish between symmetric and non-symmetric ones (i.e. whether the mutual weights of two neighboring cells are equal).

To our knowledge the first models taking into account majority functions in discrete networks were related with the physical problems of spin glasses and bootstrap percolation. The spin glasses problem appears in statistical mechanics as a model of magnetization. Roughly speaking, two spins of magnetic atoms S i and S j are coupled via an interaction w ij S i S j . The sign of w ij may be ±1. Spins change trying to minimize the global quantity -1 2 N i,j=1 w ij x i x j . The ground state corresponds to the minimum of a quadratic expression over {-1, +1} n . Algorithms, and complexity characterization of such discrete problems have been given, e.g., [START_REF] Bieche | On the ground state of the frustration model of a spin glass by a matching method of graph theory[END_REF][START_REF] Barahona | On the computational complexity of Ising glass models[END_REF]. Among the local strategies to find the minimum, the most usual corresponds to the local majority, i.e. the spin takes the most represented orientation in its neighborhood.

The majority operator appears also in the bootstrap percolation problem [START_REF] Chalupa | Bootstrap percolation on a Bhete lattice[END_REF]. Given a grid with a proportion of sites in state 1, such that a site in state 1 remains forever in this state, the bootstrap percolation problem consists in determining the proportion of 1's necessary to contaminate the whole grid with this state when strict majority is applied at every node.

For the majority operator, it was proved that the class of symmetric threshold networks updated in parallel admits only fixed points and cycles of period two [START_REF] Goles-Chacc | Decreasing energy functions as a tool for studying threshold networks[END_REF]. Further, at the heart of this proof, lies an energy operator associated to the automaton (and similar to the spin glasses energy) which drives the parallel dynamics. For the particular case of symmetric signed majority functions, since states belong to the hypercube {-1, +1} n and weights belong to the set {-1, 0, 1}, convergence occurs in time O(n 2 ) where n is the size of the network. Signed majority has also been used to model artificial neural networks. In [START_REF] Shingai | Maximun Period of 2-dimensional Uniform Neural Networks[END_REF][START_REF] Shingai | The maximum period realized in 1-dimensional uniform neural networks[END_REF] Shingai studied the dynamical behavior of one and two dimensional grid with von Neumann neighbors and bounded border conditions. He proved that in a bounded one-dimensional threshold automata every possible cycle has period less than four and in the two dimensional case there exists a bounded asymmetric threshold automaton with unbounded cycles.

On the other hand in [START_REF] Moore | Majority-vote cellular automata, ising dynamics, and pcompleteness[END_REF] C. Moore introduced a decision problem for the majority automaton acting in a d-dimensional grid: given an initial configuration, determine if a specific cell will change its state during the parallel dynamics within some time bound. In this context, he proved that for d ≥ 3 this problem is P-complete by reducing to the monotone circuit problem, i.e. with specific configurations of the automaton it is possible to convey information and to built logical gates as well as crossover in order to simulate arbitrary monotone circuits which is a well know P-complete problem. The two dimensional case with von Neumann neighborhood remains open. Recently, for bootstrap percolation, it was proved that the associated decision problem is in the class NC [START_REF] Ch | The complexity of the bootstraping percolation and other problems[END_REF]. Further, it was also proved that the same decision problem for the usual majority is P-complete over planar graphs [START_REF] Goles | The complexity of the majority rule on planar graphs[END_REF].

Our study follows this line of research and establishes new results concerning the complexity of these kind of systems inspired by physics or biology. However, following the trend of natural computing, we also consider them as potential computing devices and aim at classifying them according to the type of computations they can handle. In order to do this, we put a new look on the embedding of Boolean circuits into cellular automata. Since the first constructions of von Neumann in the 60s, encoding of logical circuits into CA has been the main tool to show various kind of complexity hardness or universality results [START_REF] Moore | Majority-vote cellular automata, ising dynamics, and pcompleteness[END_REF][START_REF] Durand | Cellular Automata: a Parallel Model[END_REF][START_REF] Banks | Universality in cellular automata[END_REF]. Usually, a global hardness result is claimed (P-completeness of prediction, Turing universality, etc) but a specific circuit construction is hidden in the proof. We argue that, on the contrary, the focus should be put on the circuit simulation itself. For instance, there is no general implication between P-completeness and Turing-universality although a suitable circuit simulation implies both: proofs factorize well at the level of circuit simulation. More importantly, we can identify two modes of simulation depending on whether a logical gate gadget can be re-used reliably several times or is corrupted after the first passage of information. In particular, we establish that in the re-usable case there is a generic solution to crossing of information (Theorem 4) and that simulating AND plus OR gates is enough (even in our planar setting) to yield intrinsic universality [START_REF] Ollinger | Universalities in cellular automata[END_REF][START_REF] Delorme | Bulking II: classifications of cellular automata[END_REF].

But our main contribution is to establish various universality and hardness results within the class of signed majority cellular automata:

• We first show that uniform signed rules can be partitioned in three equivalence classes, called symmetric, antisymmetric and asym-metric uniform rules. This implies that the study of the uniform rules is reduced to the study of three local functions.

• any asymmetric uniform rule is Turing-universal and has a P-complete prediction problem;

• the symmetric non-uniform one is also Turing-universal and has a P-complete prediction problem, but is provably not intrinsically universal, like any symmetric rule (uniform or not).

• the non-uniform signed majority CA is intrinsically universal;

Besides, we show that asymmetric uniform rules posses super-polynomial cycles, contrary to symmetric rules which have only cycles of length at most two.

The paper is organized as follows: in Section 2, we introduce the necessary formalism around the objects we study and notions of complexity and universality. In Section 3, we develop a generic toolbox to derive complexity results from the existence of circuit simulations in any cellular automata. In Sections 4 and 5, we present our results about uniform and non-uniform rules respectively. We conclude and give some research perspectives in section 6.

Preliminaries

Signed Majority Cellular Automata

In this paper we study cellular automata (CA) defined over a regular two dimensional lattice and a von Neumann neighborhood, i.e. for a cell v with coordinates (i, j) ∈ Z 2 , the neighbors of v, are N [v] = {v, v n , v e , v s , v w } where v n = (i, j + 1), v e = (i + 1, j), v s = (i, j -1), v w = (i -1, j). We will also consider finite cell spaces with periodic boundary conditions, in that case the cell space will be of size N = n 2 and the above neighborhood is taken modulo n.

A two dimensional regular lattice is called a signed regular lattice if there exists a sign matrix W = (w uv ) u,v∈Z 2 where for each pair of neighbors u, v, the value w uv ∈ {-1, 1} is called the sign of (u, v). A signed majority automaton (smca) is defined as a cellular automaton A = (Q, F W ) defined over a signed regular lattice with sign matrix W , with state set Q = {-1, 1} and where the rule is defined as

F W : {-1, 1} Z 2 → {-1, 1} Z 2 where F W (x) = u → 1 if v∈N [u] w uv x v > 0, - 1 otherwise.
Let v = (i, j) be a cell in a signed majority automaton, and let w c , w n , w e , w s and w w the signs of the edges (v, v), (v n , v), (v e , v), (v s , v) and (v w , v) respectively. We say that W v = (w c , w n , w e , w s , w w ) is the sign vector of cell v. A smca is called uniform (usmca) if each cell has the same sign vector. If the sign matrix W = (w uv ) is such that w uv = w vu for each pair of neighbors u, v then the corresponding signed majority CA is called symmetric. If the condition w uv = -w vu holds for any pair of neighbors then the CA is called anti-symmetric. A signed majority CA which is not symmetric nor anti-symmetric is called asymmetric, usmca are classical cellular automata over state set Q = {-1, 1} and von Neumann neighborhood because the same local transition map is applied in each cell. In order to have a common formalism, we will also see the non-uniform signed majority CA (nsmca) as a classical cellular automaton over state set Q = Q 6 and von Neumann neighborhood where a cell not only stores its own state but also its sign vector: the dynamics consists in applying the signed majority locally according to the sign vector which stays unchanged during the evolution. Finally, we can also consider the symmetric nsmca through a single classical cellular automaton of state set Q still with with von Neumann neighborhood with the following modification: each cell u stores a sign vector (w uv ) v∈N [u] , but when applying the signed majority at u, we use the sign vector (w uv = w uv w vu ) v∈N [u] and hence the dynamics is guaranteed to correspond to a symmetric signed majority.

When considering a finite cell space (or equivalently a periodic initial configuration on the Z 2 lattice), the number of possible configurations is finite and thus the evolution eventually enters a cycle whose length is between 1 (fixed-point) and q N where q is the size of the alphabet and N the size of the cell space. The following theorem (which is a direct corollary of [START_REF] Goles-Chacc | Decreasing energy functions as a tool for studying threshold networks[END_REF][START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF][START_REF] Ch | Threshold networks and generalizations[END_REF]) illustrates an essential difference between symmetric and asymmetric cases.

Theorem 1 (Main theorem of [START_REF] Goles-Chacc | Decreasing energy functions as a tool for studying threshold networks[END_REF][START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF]). If F is a symmetric signed majority cellular automaton (uniform or not) and x is a periodic configuration of size n, then there exists t = O(n 2 ), such that either

F t (x) = F t+1 (x) (fixed-point) or F t (x) = F t+2 (x) (cycle of length 2).

Computational Complexity and Intrinsic Universality

In this paper we aim at analyzing the complexity of the behavior of the considered systems but also their ability to compute or simulate other systems. The two aspects are of course correlated and we will use various tools and notions to account for their complexity and universality. To measure the computational complexity we will use the standard classes: NC (polynomial circuits of polylogarithmic depth), P (deterministic polynomial time), PSPACE (polynomial space) through the corresponding classical truth table reductions (AC 0 , LOGSPACE, PTIME respectively). Moreover, we will consider the following canonical problems for each system F .

• prediction problem Pred for F input a finite partial input configuration c, a marked cell z , a time step

t
question what is the the value of F t (c) z if it is completely determined by c.

• f -cycle problem for F where f is a non-decreasing function such that

1 ≤ f (n) ≤ 2 O(n)
input an input periodic configuration c of period n × n question is the length of the temporal cycle reached from c strictly greater than f (n)?

It is well-known (see for instance [START_REF] Ch | Communication complexity and intrinsic universality in cellular automata[END_REF]) that for general cellular automata (even of dimension one) the first problem is always in P and can be Pcomplete, while the second is PSPACE when f is also PSPACE and can be PSPACE-hard. Interestingly, the prediction problem is in fact NC (or LOGSPACE) for a large class of CAs [START_REF] Moore | Quasilinear cellular automata[END_REF].

We now quickly review the basic concepts of intrinsic simulation theory for cellular automata (see [START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF][START_REF] Delorme | Bulking II: classifications of cellular automata[END_REF] for an in depth introduction). The general idea is to formalize a very strict notion of simulation (or reduction) between cellular automata that preserves computational complexity of various aspects of the CA and also many of its dynamical properties. In essence, F is simulated by G if some space-time rescaling of F can be embedded as a subsystem in some space-time rescaling of G. It therefore relies on two definitions: subsystem embedding and rescaling.

If F and G are CAs, we denote by F G the fact that F is obtained by restriction and projection of the states of G, formally:

∃π : Q ⊆ Q G → Q F surjective such that π • G = F • π where π : Q Z 2 → Q Z 2
F is the cell-wise application of π. is our notation for subsystem embedding.

Given a rectangular shape m = (m 1 , m 2 ) and any alphabet Q we define the following bijection from

Q Z 2 to Q m 1 m 2 Z 2 : B m (x)(z 1 , z 2 ) = x(z 1 , z 2 ), . . . , x(z 1 +m 1 -1, z 2 ), x(z 1 , z 2 +1), . . . , (z 1 +m 1 -1, z 2 +m 2 -1)
which just recodes any configurations by blocks of shape m 1 by m 2 . Now if t is a positive integer and z ∈ Z 2 , we define the rescaling of F of parameters m and t as the CA

F < m,t> = B m • F t • B -1 m .
We finally say that G simulates F , denoted F ≤ G, if there are parameters m,t, m and t such that F < m,t> G < m ,t > . We also say that G strongly simulates F if there are parameters m and t such that F G < m,t> . Then, a CA G is intrinsically universal1 if for any CA F we have F ≤ G. It can be shown that an intrinsically universal CA can in fact strongly simulate any CA [START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF].

This definition isn't an attempt to formalize the definitive notion of universality. It is rather a pragmatic choice: strict enough to allow us to prove negative results and separation of classes [START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF][START_REF] Delorme | Bulking II: classifications of cellular automata[END_REF], and natural enough to encompass many constructions of the literature [START_REF] Ollinger | Universalities in cellular automata[END_REF] and make intrinsic universality actually a common property [START_REF] Ollinger | Four states are enough![END_REF][START_REF] Boyer | On local symmetries and universality in cellular automata[END_REF]. This approach was also successfully adopted to study other systems like self-assembly tilings [START_REF] Doty | The tile assembly model is intrinsically universal[END_REF][START_REF] Demaine | The two-handed tile assembly model is not intrinsically universal[END_REF][START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF].

CAs vs. Circuits: Complexity and Universality Toolbox

In this section, we develop a formal toolbox to deal with circuit simulation in CA in great generality. In particular we define two modes of simulation that fundamentally differ in the hardness result they imply:

• in the re-usable mode, simulation of monotone gates (AND, OR) is equivalent to intrinsic universality even for a planar lattice, and in particular there is a generic solution to crossing of information;

• in the weaker mode (no re-usability), intrinsic universality is generally not guaranteed and crossing is essential to have P-completeness of prediction and Turing-universality.

This section considers 2D CAs in all generality. In the remainder of the paper we will show that, within the natural class of signed majority automata, we have examples for both modes, including ones that are provably not capable of re-usable simulation while able to simulate any circuitery in the weaker mode. This shows the interest of focusing on the simulation mode. Our framework is formalized in two steps: first, we consider the intermediate object of dynamical circuits which adds to classical Boolean circuits a dynamical aspect; second, we define how a dynamical circuit can be concretely embedded in a CA in a very generic way without any supposition on how information is encoded.

Dynamical circuit simulations

A dynamical circuit is a particular kind of Boolean network with a DAG structure and marked input/output nodes. Definition 2. A dynamical circuit is a directed acyclic graph where each node has in-degree at most 2. The input nodes are the nodes with in-degree 0. The output nodes are the nodes with out-degree 0. Moreover, each node v is labeled by some function f v : {0, 1} d i (v) → {0, 1}, where d i (v) denotes the in-degree of v. For each input node v, f v is the constant function equal to 0. The set of gates of a dynamical planar graph is the set of functions f v . At each time step t, each node v of the graph contains some Boolean information b v (t) ∈ {0, 1}. The (synchronous) dynamics of the graph defines the value of node v at time t + 1 by b

v (t + 1) = f v b v 1 (t), b v 2 (t)
where v 1 and v 2 are the incoming neighbors of v, and similarly for vertex with in-degree different from 2. If p is the number of input nodes and q the number of output nodes, the dynamical circuit computes the function f : {0, 1} p → {0, 1} q , defined by

f x 1 , . . . , x p ) = b v 1 (T ), . . . , b vq (T )
where T is the depth of the DAG (size of the longest directed path) and values on nodes are initialized by:

b v (0) = x i if v is the ith input node, 0 otherwise.
Finally, we say that a dynamical circuit is layer-synchronous if nodes of level i + 1 only have incoming neighbors of level i, where the level is defined by the DAG structure of the graph starting at level 0 for input nodes.

Remark 3. When the dynamical circuit is "layer-synchronous" then the computed function is exactly the same as the one computed by the classical Boolean circuit corresponding to the same DAG: indeed, the computation progresses level by level until it reaches the output gates synchronously. Besides, the condition on the input nodes functions ensures that the input is given as an "impulse": at time zero input gates receive the input bits, at time one they are reset to zero.

The interest of the definition above relies in the following which is to be compared to the well-known result [START_REF] Barrington | On monotone planar circuits[END_REF] in the classical circuit complexity setting.

Theorem 4. There is a planar dynamical circuit that realizes the crossing function χ(x, y) = (y, x)

using only monotone (AND,OR) gates, and such that inputs and outputs are on the outer face of the graph arranged in the order

X IN , Y IN , X OU T , Y OU T .
This implies that the functions computed by monotone dynamical circuits can be computed by monotone planar dynamical circuits. Moreover the dynamical planar monotone circuit value problem is P-complete.

Proof. First, by chaining either AND or OR gates, we can make "delayed" wires that transmit the information but in a given number of steps. Second, using again the wire toolkit, we can make new variants of the OR and AND gates were the inputs come to any pair of sides.

Then we can realize the following kind of planar dynamical graphs with arbitrarily chosen length of wires, depicted in Figure 1. Two segments with different length on the drawings can be transformed into wires with different delays): If a signal comes at X IN it will duplicate, arrive at A and B at the same time, then at C and D at the same time and then the AND gate at the bottom will be triggered and send a signal to X OU T .

The same is true for transmission from Y IN to Y OU T . By monotonicity of all gates of the gadget the X IN → X OU T transmission is not affected by the presence of any signal from a potential Y IN → Y OU T transmission. And the same is true for Y with respect to X. So, to complete the proof that this gadget realizes crossing, it is sufficient to check that a X IN → X OU T transmission never triggers the AND gate which outputs to Y OU T (symmetrically for Y with respect to X OU T ). This AND gate is triggered if and only if at some time both gates B and D output an electron. By choosing horizontal/vertical lengths in the gadget such that AB = CD = 2BD = 2AC, the evolution can be characterized by the following successive configurations concerning presence of electrons in different parts of the ABCD rectangle:

X IN X OU T Y IN Y OU T ∨ ∨ ∨ ∨ ∧ ∧ A B C D long long short short
A A → B A → C B B → D C C → D D 1 0 0 0 0 0 0 0 0 2 1 0 0 1 0 0 0 0 3 0 1 1 0 1 0 0 0 4 0 1 0 0 0 1 0 1 5 0 1 0 0 0 0 1 0 6 0 0 0 1 0 0 1 0 7 0 0 0 0 1 0 1 0 8 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0
We can check that the simultaneous presence of an electron in B and D never occurs, and deduce that when a signal comes only from X IN it never triggers Y OU T .

From the existence of a crossing gadget we deduce P-completeness of the dynamical planar monotone circuit value problem using the classical encoding used for P-completeness of monotone circuit value problem: each Boolean value b is represented by a positive copy b and a negative copy ¬b; then negation is realized by swapping b and ¬b (wire crossing) and the AND/OR gates are realized together with NAND/NOR using De Morgan's laws.

We now describe two modes of simulation of a set of gates by a cellular automaton. In the first one, the gates can be used only once and hence it can only simulate layer-synchronized circuits. The second one asks for each gate to be re-usable and hence is able to simulate any dynamical circuit. Both modes require the simulation to work in constant time.

The basic simulation mechanism works by using square blocks concatenated in a grid-like fashion that represent parts of the circuit (either a node or an edge). The definition doesn't require any specific way of building this blocks or representing information shared inside. They communicate information with their four neighbors (north, east, south, west) in such a way that each one implements a Boolean function with at most 2 inputs and at most 2 outputs. In the sequel any building block we consider will compute one of the following functions (we represent them using type {0, 1} 4 → {0, 1} 4 in order to make explicit the position of inputs and outputs among the neighbors in the order north, east, south, west): AND(x, * , * , y) = 0, min(x, y), 0, 0 OR(x, * , * , y) = 0, max(x, y), 0, 0 CROSS(x, * , * , y) = 0, y, x, 0 NOP( * , * , * , * ) = 0, 0, 0, 0

MULTIPLY( * , * , * , x) = 0, x, x, 0 WIRE i,o c ∈ {0, 1} 4 = k ∈ {0, . . . , 3} → c(i) if k = o 0 else
for any i = o ∈ {0, . . . , 3}. Note that any function f above is such that f (0, 0, 0, 0) = (0, 0, 0, 0). We denote by Img(f ) the set of 4-uple that can be obtained as an image of f . The WIRE i,o functions are just all the possible ways to read a bit on one side and transmit it to another side. Together with the NOP and MULTIPLY function they represent the basic planar wiring toolkit denoted W below. The NOP gate is special in that one considers it has 4 inputs and 4 outputs.

In this paper, in order to simplify statements, we only discuss gates which are not part of the wiring toolkit W because we always assume that gates from W are available in any simulation considered. The following definition of simulation of a gate set G by a CA precisely requires the considered CA to actually simulate all gates from the set G ∪ W .

Definition 5 (Simulating a gate set). Let G ⊆ {AND,OR,CROSS} be a set of gates. Let F be a CA with states set Q and N > 0 be an integer. Consider a set V ⊆ Q N ×N of patterns, the valid blocks, each of which as a type f u where f ∈ G ∪ W and u ∈ Img(f ) and such that, for any f u , there is some block of V of type f u . If a block B ∈ V has type f (a,b,c,d) for some f , we say it has north value a, east value b, south value c and west value d. Finally let ∆ > 0 be some constant. A configuration is valid if it is a concatenation of valid blocks where output sides of a block must face input sides of its corresponding neighbors. Given a block B ∈ V of type f u in a valid configuration, we say that it makes the correct transition if it becomes a block of type f v after ∆ steps where v = f (n, e, s, w) is the output of f on the input read from surrounding blocks, precisely: the block at the north of B has south value n, the block at the east of B has west value e, etc.

Weak simulation. We say that F simulates the set of gates G with delay ∆ and valid blocks V if for any valid configuration c, the configuration F ∆ (c) is valid and for any f ∈ G ∪ W , any block of type f (0,0,0,0) in c makes the correct transition.

Re-usable simulation. The simulation is re-usable if any block in any valid configuration makes the correct transition. Remark 6.

• Each block of V has a type f (n,s,e,w) but the definition does not specify the way information is encoded inside blocks: for instance, the 'north value' n is not necessarily determined by the value of a particular cell in the block, it could be encoded as the parity of the number of occurrences of some state in the whole block, or as the i th binary digit of π where i is a sum of some states in the whole block, etc;

• The fact that several valid blocks can have the same type allows some redundancy in the information encoding; the necessity of this redundancy in block encodings is an open problem in the context of intrinsic universality (open problem 6 of [START_REF] Delorme | Bulking II: classifications of cellular automata[END_REF]); in our context it can be understood intuitively as follows: in general, several contexts can force a block to evolve to the same type f (n,s,e,w) after ∆ steps, but the information flow and the computation happening inside the block can leave traces of this context inside the block;

• The positions of inputs and outputs around a block to simulate a gate is not strict for OR, AND and MULTIPLY gates since we can rewire without crossing to any choice of positions thanks to the symmetry of this gate; for the CROSS gate, it is sufficient to respect the fact that inputs and outputs are not interleaved.

In the above definition, blocks are used to simulate gates with at most 2 inputs and at most 2 outputs. We naturally want to concatenate these blocks in complicated ways to compute more general Boolean functions with many inputs and outputs. The following lemma says that doing this we are able to realize any function computable by dynamical circuits corresponding to the set of gates and the simulation mode. Said differently, the grid layout and synchronization by wire lengths can be solved in a generic way.

We first formalize how we derive the simulation of functions computed by circuits from the simulation of their gate set. The intuition is that by concatenation of valid blocks we can build meta-blocks that have the desired input/output relation.

Definition 7 (Simulating a Boolean function). Let F be any CA that simulates a set of gates G with delay ∆ and valid blocks V and consider some finite function φ : {0, 1} p → {0, 1} k . We say that F simulates φ if there are integers m ≥ max(p, k) and T , and a collection V of m × m valid patterns of blocks from V indexed by outputs of φ

V = v∈Img(φ) B v
where B v ⊆ V m×m , and such that 1. in each block B ∈ B v , the k V -blocks starting from the upper-right corner and going downwards must produce the sequence of bits v when reading their east value;

2. a block B ∈ B (0,...,0) , when in a valid configuration, becomes B ∈ B φ(u) after T steps where u is the input of p bits read in the initial configuration on the left side of B starting from the top.

The simulation is re-usable if the second condition above is also true for any block from V.

Lemma 8 (Grid layout and synchronization lemma). Let F be any CA that simulates a set of gates G with delay ∆ and valid blocks V (Definition 5). We have: Proof. We proceed by a sequence of transformations of a given circuit that preserve the computed function. It is important to note that we don't need any bound on the size of the final simulation. Moreover we have, by definition 5, the existence of wires that allows to draw arbitrary discrete paths on the plane. These two aspects make the proof rather straightforward, without any technical difficulty. Given a dynamical circuit C with the corresponding hypothesis in each case, we proceed like this:

• if {AND, OR} ⊆ G then F can
• first, in the case of re-usable simulation, we can suppose that C is planar by theorem 4.

• we then add as many OR gates with 1 input and out-degree 2 to ensure out-degree 2 for each gate of C. While doing this we pad when necessary by useless OR gates (1 input, 1 output) so that there is a constant k such that each arc in C is encoded as a directed path of length k in the new circuit C . In particular C is layer synchronous if C is, and both compute the same function;

• then, we consider a grid layout of the graph of C : nodes are positioned at points of Z 2 and arcs are polygonal lines. Note that in any case, we position inputs and outputs on the outer face without interleaving. By multiplication of the grid step (embedding Z 2 into (kZ) 2 ), we can choose the minimal distance between two point of interest (node or crossing between lines) to be as large as we need without changing the ratio between length of arcs. In particular, we can ensure that the minimal distance D between two points of interest is much larger than the ratio α between the longest encoded arc and the shortest encoded arc; Moreover, we can ensure that each node is on the grid (2Z) 2 so that the • 1 -distance between any two nodes is even;

• then, we transform each Euclidean arc by a Z 2 -path and at each crossing (if any) we put a crossing gate. To do this while ensuring that all Euclidean arcs are represented by Z 2 -paths of the exact same Z 2length (number of steps on the Z 2 grid), we use 'fast' (almost) minimal Z 2 -paths for long Euclidean arcs, and 'slow' zig-zag Z 2 -paths for short Euclidean arcs (see Figure 2). The remarks above ensure that we can do it because:

1. the worst case we have to deal with is a discrete path of length α times the Euclidean length of its corresponding arc: choosing D >> α ensure that we can make zig-zags of sufficient width without collisions;

2. the fine-tuning of distances is possible because everything is even and we can replace a path of length 2 by a path of length 4 with same in and out points. Moreover, the Euclidean arcs were chosen long enough so that we can modify their corresponding zig-zag locally on a negligible fraction of their length to implement this fine tuning.

After this process we get a partial labeling of Z 2 with gates from the set G ∪ W . To show formally that the function computed by the circuit C is simulated by F it remains to complete a big square containing this partial labeling with NOP gates and rewire inputs and outputs so that they are horizontally aligned. The rewiring is possible even without crossing gate since inputs and outputs are on the outer face without interleaving.

In the next section, we give an example of a threshold-like CA that can realize such simulations. Before this, we derive various consequences of the existence of each kind of simulation.

Three flavors of circuit simulation, three levels of complexity

We are now going to deduce various hardness results using the existence of some circuit simulation. First, the simple fact of simulating wires in the weakest mode already almost gives NC 1 -hardness if one thinks about grid graph reachability problems. The difficulty is that wires alone do not provide any means of keeping trace of some passage of information. We therefore add a FUSIBLE gate, aimed at linking the presence of a signal on a wire at any time, to the prediction problem Pred of a cell's state at some precise time. Indeed, in the particular case of the following AC 0 reduction, the time window during which the signal we wish to predict may arrive is unbounded, though the reduction allows only constant time computation. FUSIBLE i (x ∈ {0, 1} 4 ) = (0, 0, 0, 0) is a gate that contains a particular cell z such that

F t (c) z =      1 for all t ≥ t 0 + ∆ -1 for all t < t 0 ±1 otherwise
, where t 0 is the first time at which x(i) = 1. Proposition 9. If a 2D CA F can simulate WIRE i,o , NOP and FUSIBLE i for all i, o then its prediction problem Pred is NC 1 -hard under AC 0 reductions.

Proof. The in-degree-one-out-degree-one grid graph reachability problem (11GGR) has been proven to be NC 1 -hard under AC 0 reductions in [START_REF] Allender | Planar and grid graph reachability problems[END_REF]. We prove the proposition by constructing an AC 0 reduction of 11GGR to our prediction problem. Since the composition of two AC 0 algorithms is an AC 0 algorithm, the result will hold.

Let us first formally define 11GGR. A directed grid graph is a directed graph whose vertices are a subset of N × N, and all edges are of the form (i, j) → (i + b, j) or (i, j) → (i, j + b) with b ∈ {-1, 1}. The 11GGR problem is the following. Given a directed grid graph G of size n × m with in-degree and out-degree at most 1, and two vertices s and t of G, does there exists a directed path from s to t in G?

Given such a directed grid graph, the idea of the reduction is straightforward: every directed path is encoded by an analogue wire using WIRE i,o gates, s is encoded by a 1 impulse, and t is encoded by a FUSIBLE gate, all this on a background of NOP gates. More precisely, the reduction maps every vertex to a gate as follows (see Figure 3 for an illustration):

• s is encoded by a valid block with value 1 on every side;

• t is encoded by a FUSIBLE i gate with i the side of the arc whose head is t;

• any other vertex v having in-degree and out-degree 1 is encoded by a WIRE i,o gate, where i is the side of the arc whose head is v, and o is the side of the arc whose tail is v;

• any other point of the n × m rectangle is encoded by a NOP gate; The instance of Pred asks for the state of the distinguished cell of the unique FUSIBLE gate at time (nm + 1)∆, which corresponds to the length of the longest possible path plus one additional delay for the fusible to melt. This reduction can be computed in parallel (each gate separately) on a CREW-PRAM, using a constant time and nm processors. It can therefore be implemented by a family of circuits in the AC 0 class (polynomial size and bounded depth circuits), according to the time-processors/depth-size correspondance presented in [START_REF] Greenlaw | Limits to parallel computation: P-completeness theory[END_REF].

When doing circuit simulations in the weak mode one cannot expect information processing to happen in a fixed region of space since gadget simulating gates are potentially destroyed after their first use. However, it is perfectly possible to handle unbounded one-dimensional computations by having a one-dimensional computation front that progresses in the 2D lattice during the evolution and therefore fires each gadget at a given position only once. For instance, the computation front can be diagonal so that the value of cell z ∈ Z at time t of the 1D computing process is read in the block (t + z, tz) at some time O(t) in the 2D simulating CA. With AND, OR and crossings gates, it is possible to organize arbitrary computations in that way.

Proposition 10. If a 2D CA F can simulate a {AND, OR, CROSS} circuitry then it can simulate any 1D CA with a constant time slowdown, and therefore it is Turing-universal and its prediction problem Pred is P-complete.

Proof. Consider any finite set Q and any local function f : Q 2 → Q. There is some k and some encoding φ : Q → {0, 1} k such that φ is injective and Img(φ) does not contain two comparable strings of bits for the componentwise order ≺ (e.g. 10 ≺ 11 but 01 ≺ 10). Therefore there is a monotone function f : {0, 1} k × {0, 1} k → {0, 1} k that simulates f up to the recoding φ, i.e.

• u 1 ≺ v 1 and u 2 ≺ v 2 ⇒ f (u 1 , u 2 ) ≺ f (v 1 , v 2 ); • ∀q 1 , q 2 ∈ Q, φ(f (q 1 , q 2 )) = f φ(q 1 ), φ(q 2 ) .
Then there is a monotone layer-synchronous dynamical circuit that computes f (because there is a classical circuit that does) so, by Lemma 8, f is computed by F using valid blocks of the circuit simulation. Moreover, using wires and crossings and the constructions of Lemma 8, we can construct a valid meta-block that receives inputs x and y on its west and south sides (respectively) and produces f (x, y) both on its north and east sides (see figure 4). Using zig-zag wiring techniques as in lemma 8 we can ensure that all logical connections are realized by paths of the same length so that both outputs of the meta block are produced at the same time when inputs come in synchronously. Since f simulates f through the encoding φ, we can associate a set of meta blocks B q to each q ∈ Q. Then, starting from any configuration C : Z 2 → Q representing a concatenation of aligned meta blocks on a meta Z 2 grid (meta block of type B C(z) at position z ∈ Z 2 ), the CA F simulates on each diagonal the 1D CA with two neighbors and local transition function f . Formally, it can be expressed at the meta block level by

X Y f (X, Y ) Lemma 8 X f (X, Y ) f (X, Y ) Y
F T (C) (i,j) ∈ B f (C (i-1,j) ,C (i,j-1) )
where T is the time constant common to all meta blocks. Choosing f and Q appropriately we deduce Turing-universality of F (it is straightforward to build a 1D CA with 2 neighbors that simulates a given Turing machine).

Choosing f and Q so that the corresponding 1D CA has a P -complete prediction problem we deduce P -completeness of the prediction problem of F . For instance, we can take the 2-block recoding of elementary CA 110 which is P-complete [START_REF] Neary | P-completeness of cellular automaton rule 110[END_REF], i.e. Q = {0, 1} 2 and f such that:

f (x 0 , x 1 ), (x 2 , x 3 ) = f 110 (x 0 , x 1 , x 2 ), f 110 (x 1 , x 2 , x 3 ) .
The reduction of the prediction problem of this 1D CA to the prediction problem of F is a truth table reduction done as follow: to an input (w, t, z) for the prediction problem in the 1D CA made of a 1D word w ∈ Q * of size n a time t and a position z ∈ Z we associate the finite set of input (W, T t, z j ) j where

• W is a n × n pattern of meta blocks which are all the same B q 0 except on the diagonal where B w i is at position (i, -i);

• z j = (K(z + T t), -Kz) + j where K is the size of the meta blocks and

{ j } = [0, K -1] × [0, K -1]
are all the finite positional offsets needed to visit all cells of the meta block.

The simulation by diagonals ensures that the reduction is correct: knowing the entire meta-block at meta-position (z + T t, -z) at time T t allows to know its type and therefore the value of cell z after t iteration of the 1D CA on input w. This reduction is also clearly logspace computable (the size and complexity of meta blocks is just a constant in the reduction).

The next proposition formalizes what has been present informally in the literature since a long time [START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Ollinger | Universalities in cellular automata[END_REF]: for 2D CA, intrinsic universality is equivalent to the ability to simulate a rich enough re-usable circuitry. Using Theorem 4, we can state it in a stronger way where only monotone gates are required.

Proposition 11. A 2D CA F can simulate in a re-usable way the gates {AND, OR} if and only if it is intrinsically universal. In that case its prediction problem is P-complete and its f -cycle problem is PSPACE-hard for any f with

1 ≤ f (n) ≤ 2 O(n) .
Proof. First, if F is intrinsically universal then it is strongly intrinsically universal [START_REF] Delorme | Bulking II: classifications of cellular automata[END_REF], so in particular it can strongly simulate any CA which is well known for its ability to simulate AND OR gates in a re-usable way, for instance the CA of Banks [12] which has 2 states and von Neumann neighborhood, or the well-known "Game of Life" [START_REF] Berlekamp | Winning ways : For your mathematical plays[END_REF]. The ability to simulate a set of gates is preserved by strong simulation (the simulating CA does if the simulated CA does).

For the other direction, consider some F that simulates gates {AND, OR} in a re-usable way. We proceed in a similar way as in proof of Proposition 10, except that all simulations here are re-usable. Consider any finite set Q and any φ : Q 4 → Q. It can be encoded into a monotone function φ : {0, 1} k 4 → {0, 1} k which can be computed by a dynamical monotone circuit because it can be computed by a classical monotone circuit. Then, using lemma 8, we know that F can simulate in a re-usable way φ using valid blocks. From that construction we can obtain, by rewiring and crossing (lemma 8 actually implies that a re-usable crossing meta block is constructible), a meta block that receive one input from each side encoding a state of Q, computes φ on this 4-uple and sends the result to each side (see Figure 5). Since φ simulates f through the encoding φ, we can associate a set of meta blocks B q to each q ∈ Q. Then, starting from any configuration C : Z 2 → Q representing a concatenation of aligned meta blocks on a meta Z 2 grid (meta block of type B C(z) at position z ∈ Z 2 ), the CA F simulates the CA with von Neumann neighborhood and local transition function f .

Formally, it can be expressed at the meta block level by

F T (C) (i,j) ∈ B f (C (i+1,j) ,C (i,j+1) ,C (i-1,j) ,C (i,j-1) )
where T is the time constant common to all meta blocks. Choosing f to be intrinsically universal, we deduce that F is intrinsically universal. Now consider a 2D CA F with the following properties:

• its states set allows to form structured N × N patterns, where some O(N ) part encodes an instance of the quantified Boolean formula problem (QBF) (see for instance [START_REF] Kozen | Theory of Computation[END_REF]), some O(N ) part is reserved to all the necessary computation to test the existence of a solution to the problem, and a Ω(N × N ) part allows to encode a binary counter of length Ω(N × N );

• starting from a valid pattern as above, it starts to search (by brute force) for a solution to the QBF problem;

• if it doesn't find any solution, it erases everything with a spreading state, so that it reaches a fixed point;

• if it finds a solution, it start to increment the binary counter at each step forever (the counter restart to 0 when its maximal value is reached), so that it enters a temporal cycle of length Ω(2 N ×N ).

It is straightforward to design such a CA F with a simple enough structure so that the f -cycle problem of F is PSPACE-complete for any f with 1 ≤ f (n) ≤ 2 O(n) . Indeed, the CA F converges to a cycle of length 1 (hence no larger than f (n)), or a cycle of length Ω(2 N ×N ) (hence strictly larger than f (n) for large enough n) depending on whether the QBF instance has a solution or not. The fact that QBF is PSPACE-hard (see for instance [START_REF] Kozen | Theory of Computation[END_REF]) allows us to conclude.

Uniform Signed Majority Cellular Automata

In this section we will study usmca both in their dynamical properties and their complexity. Recall that usmca are signed majority cellular automata where each cell has the same sign vector.

There are 32 possible sign vectors, hence 32 different usmca. However, from those 32 usmca only 12 are different up to rotation. We subdivide these Name Sign vector Group (w c , w n , w e , w s , w w )

F 1 (+1, +1, +1, +1, +1) Symmetric F 1 (-1, -1, -1, -1, -1) Symmetric F 2 (+1, -1, -1, -1, -1) Symmetric F 2 (-1, +1, +1, +1, +1) Symmetric F 3 (+1, -1, +1, -1, +1) Symmetric F 3 (-1, +1, -1, +1, -1) Symmetric F 4 (+1, +1, -1, -1, +1) Antisymmetric F 4 (-1, -1, +1, +1, -1) Antisymmetric F 5 (+1, +1, -1, +1, +1) Asymmetric F 5 (-1, -1, +1, -1, -1) Asymmetric F 6 (+1, -1, -1, -1, +1) Asymmetric F 6 (-1, +1, +1, +1, -1) Asymmetric
Table 1: List of the six Symmetric, two Antisymmetric, and four Asymmetric usmcawith their respective sign vectors.

12 usmca into the following three groups, according to the symmetries of the sign matrix W = (w uv ) u,v∈Z 2 . We say that a usmca is symmetric if W is a symmetric matrix, i.e. w uv = w vu for each pair of cells u, v. On the other hand, we say that a usmca is antisymmetric if W satisfies that w uv = -w vu for each pair of cells u, v. When the usmca is neither symmetric nor antisymmetric, we say that it is asymmetric. There are six Symmetric, two Antisymmetric, and four Asymmetric usmca, shown in Figures 6, 7 and 8, respectively. Some rules are equivalent under simple transformations of configurations and these transformations preserve their ability to simulate gates sets. One could imagine a lot of simulation-preserving transformations, but the following will be sufficient for our purpose. A block permutation is a bijective transformation of Q Z 2 which consists in partitioning the space into n × n blocks in a Z 2 -regular way, applying a common permutation π of Q n×n on each n × n block of the configuration. Such a transformation is given by n, π and the alignment of blocks. Two CAs F and F are block conjugate if there is a block permutation Φ such that F • Φ = Φ • F . The following lemma shows that block-conjugacy preserves simulation of gate sets. The informal intuition of this fact is very simple: if F is block-conjugate to F via Φ and can simulate a gate set using a set of valid blocks V , then F simulates the same gate set using the blocks obtained by applying Φ to the blocks of V . However there is a technical complication: if the size of blocks of V and the size of blocks used by Φ are multiplicatively independent then several alignments occur. This is solved by expanding blocks of V to a convenient size which is always possible thanks to the freedom allowed in Definition 5.

Lemma 12. If two CAs F and F are block-conjugate then they can simulate the same sets of gates under the same mode.

Proof. Let Φ be the block permutation giving the conjugacy F • Φ = Φ • F and denote by n 0 the size of blocks it uses. Suppose that F can simulate a set of gates with valid blocks V F of size N × N and delay ∆. For each block B ∈ V F (supposing that B has outputs at north and east, other cases are similar) we define the corresponding block B of size n 0 N × n 0 N as follows:

B ↑ . . . ↑ → • • • →
where arrows correspond to wires (with input/output positions indicated by the arrows) and the blank part is filled with NOP blocks. We get a set V F of blocks and it is straightforward to check that F simulates the same set of gates with blocks V F and delay n 0 ∆ (the type given to B is the type of B). Now let B be the block obtained by applying Φ to B with the correct alignment (the lower-left corner of B coincides with the lower-left corner of a block of Φ). We get a set V F of blocks of size n 0 N × n 0 N with the following property: any concatenation of blocks of V F is the image under Φ of the corresponding concatenation of blocks of V F and, after n 0 ∆ steps of F and F respectively, this correspondence is preserved between images. We deduce that F simulates the set of gates under the same mode. The lemma follows because block-conjugacy is a symmetric relation.

The following lemma shows that there are only 3 essentially different rules up to block-conjugacy. Lemma 13. Let F be a symmetric (resp. antisymmetric, resp. asymmetric) usmca then F is block-conjugate to F 1 (resp. F 4 , resp. F 5 ).

Proof. Let α : {-1, 1} Z 2 → {-1, 1} Z 2 be defined as α(x) = -x. We begin showing that for every i ∈ {1, 2, 3, 4, 5, 6}, any configuration x ∈ {-1, 1} Z 2 and any t ≥ 0, we have that

F t i = α t • F t i .
Indeed, notice that if W is the sign matrix of rule F i and W is the sign matrix of rule F i , then W = -W . This implies that for every v ∈ Z 2 u∈N (v)

w uv x u = - u∈N (v) (-w uv )x u ⇒ F i (x) = -F i (x)
and inductively,

u∈N (v) w uv (F t i (x)) u = u∈N (v) w uv • (-1) t • (F t i (x)) u = (-1) t+1 u∈N (v) (-w uv ) • (F t i (x)) u ⇒ F t+1 i (x) = (-1) t+1 F t+1 i (x) = α t+1 (F t+1 i (x)).

Consider now the function

β : {-1, 1} Z 2 → {-1, 1} Z 2 such that β(x) (i,j) = -x (i,j) if i + j is even, x (i,j) if i + j is odd. Then F t 1 = β • F t 2 • β and F t 1 = β • F t 2 • β.
Indeed, let W = (w uv ) u,v∈Z 2 be the sign matrix of F 1 (respectively F 1 ) and W = (w uv ) u,v∈Z 2 be the sign matrix of F 2 (respectively F 2 ). Notice that for every u = v we have that w uv = -w uv . Then for every v = (i, j) ∈ Z 2 if we write u∈N (v)

w uv x u =            -   u∈N (v),u =v (-w uv ) • x u + w vv (-x v )   if i + j is even, u∈N (v),u =v (-w uv ) • (-x u ) + w vv x v if i + j is odd. we obtain F 1 (x) = β((F 2 (β(x))) and F 1 (x) = β((F 2 (β(x))). Since β •β = id, then for any t ≥ 0, F t 1 = β • F t 2 • β and F t 1 = β • F t 2 • β. Consider finally the function γ : {-1, 1} Z 2 → {-1, 1} Z 2 such that γ(x) (i,j) = -x (i,j) if i is even x (i,j) if i is odd Then F t 1 = γ • F t 3 • γ, F t 1 = γ • F t 3 • γ, F t 5 = γ • F t 6 • γ and F t 5 = γ • F t 6 • γ. Indeed, let F = F 1 (resp. F 1 , F 5 , F 5
) and F = F 3 (resp. F 3 , F 6 , F 6 ), let W = (w uv ) u,v∈Z 2 be the sign matrix of F and W = (w uv ) u,v∈Z 2 the sign matrix of F . Clearly for any (i, j), we have that w c = w c , w e = w e and w w = w w , while w n = -w n and w s = -w s . If we write for v = (i, j),

u∈N (v) w uv x u =        -[w c (-x v ) + (-w n )x vn + w e (-x ve ) +(-w s )x vs + w w (-x vw )] if i is even, w c x v + (-w n )(-x vn ) + w e x ve +(-w s )(-x vs ) + w w x vw if i is odd.
Then clearly F = γ • F • γ, and since γ • γ = id, we conclude that

F t = γ • (F ) t • γ
Theorem 14. Any symmetric rule can simulate planar monotone layersynchronous dynamical circuit, and has a NC 1 -hard prediction problem. However, it cannot simulate re-usable monotone circuitry and is not intrinsically universal.

Proof. Figure 9 presents how F 1 can simulate planar monotone layer synchronous dynamical circuit (Lemma 8): W , AND and OR gates. Thanks to the additional FUSIBLE gate, Proposition 9 allows to conclude the NC 1 hardness of F 1 , hence of all symmetric rules (Lemma 13). Concerning the second part of the statement, Theorem 1 implies that the f -cycle problem is trivial for symmetric rules when f is constant equal to 3. By proposition 11 these rules cannot be intrinsically universal and cannot simulate re-usable AND OR circuitry.

The symmetric rules are limited due to their trivial behavior on limit cycles. The following theorems show that antisymmetric and asymmetric rules are not as trivial concerning the limit cycles.

Theorem 15. Any antisymmetric signed majority cellular automaton can exhibit limit cycles of length Ω(N ), where N is the number of sites.

Proof. From Lemma 13 we know that it is enough to prove the result for rule F 4 . Let n ≥ 16 be such that (n -12)/4 is even, and consider the following configuration in a grid of size n × n: in the first line of the grid repeat (n -12)/4 times the pattern (1, 1, -1, -1). Then, in the 12 remaining cells, repeat twice the pattern (1, 1, -1, -1, -1, -1). Then, in the consecutive (a) A wire is constantly blinking (left top) and transmits a signal by being consumed (left bottom). A turn (center left). An obstructor prevents a signal (center). A multiplier (center right). These gadgets can straightforwardly be composed to simulate a wiring toolkit W . Plus a diode (right). × (b) OR (left), AND (center) and FUSIBLE (right, with a distinguished cell) gates. These gates have a particular feature: the four sides are undifferentiated inputs/outputs. For example, the AND gates waits for any two signals to arrive, and then sends a signal to the two remaining sides. One can easily transform them into classical gates using diodes. lines, copy the pattern of the previous line and shift the pattern one cell to the west. Finally, pick a special line i, and in the two locations of the line i with four consecutive sites in state -1, replace (-1, -1, -1, -1) by (-1, -1, 1, -1), call this line a perturbation. In Figure 10 there is an example for n = 20. This configuration satisfies that the perturbation is shifted two sites to the north and two sites to the west every 2n steps. Therefore, a limit cycle of length N = n 2 is obtained. Theorem 16. Any asymmetric signed majority cellular automaton can exhibit limit cycles of super-polynomial length.

Proof. From Lemma 13, it is enough to show long limit cycles just for rule F 5 . We start showing how to build a cycle gadget with k perturbations, which in a finite periodic configuration of size 8 × n exhibits limit cycles of length n if k = 0 and limit cycles of length n(n/2 + k) if k > 0. Figure 11 shows the cycle gadget with zero perturbation: a particle moves through a wire: a straight horizontal line of cells initially in state -1. In the top of this line, there is a series of straight lines of three cells alternating states. In the bottom, another series of straight lines alternating in inverse order. In the middle line two consecutive cells in state 1 form a particle, which in each step moves one cell to the east.

A perturbation corresponds to change the state from 1 to -1 to a cell in the top line of the wire, and k perturbations correspond to change the same changes to k consecutive cells in the top line of the wire (see Figure 12). Each perturbation delays the particle by two time steps compared to the case without perturbation. Moreover, each time that the particle passes through a perturbation, the configuration shifts two cells to the west. For a cycle gadget with k > 0 perturbations, we obtain limit cycles of length n/2(n + 2k) = n(n/2 + k).

We can compose several cycles gadgets with different numbers of perturbations, as shown on Figure 13. Notice that the dynamics of one cycle gadget do not affect the others. The length of the composition's limit cycle is then the least common multiple of the limit cycles of each cycle gadget.

Let π(n) be the number of prime numbers in (n/2, n). Consider the composition of every cycle gadget with perturbation in {p 1n/2 . . . , p π(m)n/2}, such that {p 1 . . . , p π(m) } are all the prime numbers in (n/2, n). We obtain a periodic configuration of size N = n × m, where m = O( n log n ), and with a limit cycle of length n • lcm(p 1 , . . . , p π(m) ) = 2 Ω(n) = 2 Ω(N 1/3 ) (which can be deduced from the Prime Number Theorem [START_REF] Hardy | An introduction to the theory of numbers, other prints with corrections[END_REF]). Proof. From Lemma 13 we know that it is enough to prove the result for rule F 5 . In Figures 16 and17 we present the elements required to apply Proposition 10. Given the intrinsic asymmetry of this rule, different gadgets are required to transmit information in the different orientations. In Figure 16 are presented the 12 possible wires, while in Figure 17 we present the gate gadgets. Remark that we do not present explicitly the CROSS gadget, but enough tools in order to build it. Indeed, we present the following functions:

(¬west)And(north)(x, * , * , y) = (0, (1y)x, 0, 0), (west)And(¬north)(x, * , * , y) = (0, (1x)y, 0, 0), from which we can compute a xor gate gadget using the formula.

(P )xor(Q) = (P ∧ ¬(P ∧ Q)) ∨ (Q ∧ ¬(P ∧ Q)).
We simulate the CROSS gate using the gadgets on Figures 14 and15 ). The diamond numbered 5 represent an OR gate (with two outputs using a MULTIPLY gadget). Finally, the circular shaped nodes are wires (Figure 16). stay unchanged. Therefore, in the following, we give only the core of the gadgets and denote by B the sides of cells that must be connect to the invariable background to ensure the correctness of the construction.

• the wire element:

- It is important to point out that C. Moore's conjecture [START_REF] Moore | Majority-vote cellular automata, ising dynamics, and pcompleteness[END_REF], which states that the Pred for the majority rule is in NC (all positive weights), is not true for non-uniform signed majority (since we proved that is P-Complete). However, if the conjecture is true for the majority rule, then it will be for all uniform symmetric signed majority rules.

We think that this work calls for the following future research or questions:

• look for other widgets, especially in anti-symmetric rules where we have few results;

• use decreasing energy or potential techniques to prove structural results on the kind of configurations that can embed computation;

• use communication complexity to possibly prove upper bounds on some rules that would contradict the existence of a specific circuit simulation;

• what is the prediction complexity of the symmetric majority rule? is it Turing universal in at least some weak sense?

Figure 1 :

 1 Figure 1: Crossing gadget for planar dynamical circuits with monotone gates.

Figure 2 :

 2 Figure 2: Compensating for the difference between Euclidian lengths by making zig-zags: the two paths have the same Z 2 -length but the Euclidian distances between starting and ending positions are clearly different.

Figure 3 :

 3 Figure 3: Reduction from 11GGR to the prediction problem on a dynamical circuit with WIRE i,o , NOP and FUSIBLE i gates. Wires are indicated by arrows, 1 is a valid block with value 1 on every side (corresponding to s), F is the FUSIBLE gate whose input is pointed, and 0 are NOP gates.

Figure 4 :

 4 Figure 4: A block simulating the local transition function of a 1D CA.

φFigure 5 :

 5 Figure 5: A block simulating in a re-usable way the local transition function of a 2D CA.

Figure 6 :Figure 7 :Figure 8 :

 678 Figure 6: The six Symmetric usmca are called, from left to right in the first line F 1 , F 2 , F 3 and F 1 , F 2 , F 3 in the second line.

Figure 9 :

 9 Figure 9: F 1 simulates planar monotone layer-synchronous dynamical circuit. Animations are presented on Appendix A.

Figure 10 :

 10 Figure 10: Example of a pattern of size n×n for n = 20, that exhibits a limit cycle of length n 2 when updated according to the antisymmetric rule F 4 . In the figure are represented steps 0, 10, 20, 30 and 40, from left to right. Note that at step 40 the configuration has shifted two sites to the north and two sites to the west.

Figure 11 :

 11 Figure 11: Example of 5 steps of cycle gadget with zero perturbations, for n = 8. The state 1 (resp. -1) is represented as a black cell (resp. white cell). The moving particle takes n steps to return to the initial configuration.

Figure 12 :

 12 Figure12: Examples of perturbations in the cycle gadgets for rule F 5 . The first line represents the dynamics of a cycle gadget of size n = 8 with one perturbation, notice that the limit cycle reached in this case has period n(n/2+1). On the second line is represented the first 5 steps in the dynamics of the cycle gadget with two perturbations, reaching a cycle of length n(n/2 + 2).

Figure 13 : 2 ) 17 .

 13217 Figure 13: Composition of three cycle gadgets with zero, one, and two perturbations. The length of the limit cycle in this case is n • lcm(n/2 + 1, n/2 + 2)

  .

Figure 14 :

 14 Figure14: Representation of a xor gate. Diamonds numbered 1 represent a MULTI-PLY gate, the diamond numbered 2 represent a AND gate (with two outputs using a MULTIPLY gadget). The diamonds numbered 3 and 4 represent (¬west)And(north) and (west)And(¬north) gates, respectively (Figure17(b)). The diamond numbered 5 represent an OR gate (with two outputs using a MULTIPLY gadget). Finally, the circular shaped nodes are wires (Figure16).

Figure 15 :

 15 Figure 15: CROSS gate. Diamonds 1 represent MUTLIPLY gates. The diamonds numbered 2 and 3 represent a xor gadgets.

  (a) AND (left) and OR (right) gates. The inputs are from north and west, and the outputs at east. (b) (¬west)And(north) and (west)And(¬north) gates. These gates receive inputs from north and west, and output to the east.(c) MULTIPLY gadgets, with inputs from the north and west sides.

Figure 17 :

 17 Figure 17: Gates for the rule F 5 . The state 1 (resp. -1) is represented as a black (resp. white) cell. CROSS gadget can be constructed using the gadgets presented on Figure 17b. Animations are presented on Appendix C.

  simulate (Definition 7) any function computed by a planar monotone layer-synchronous dynamical circuit with inputs and outputs placed on the outer face in a non-interleaved way (inputs on one half, outputs on the other half );

• if {AND, OR, CROSS} ⊆ G then F can simulate (Definition 7) any function computed by a monotone layer-synchronous dynamical circuit;

• if {AND, OR} ⊆ G and the simulation is re-usable then F can simulate in a re-usable way (Definition 7) any function computed by a monotone dynamical circuit.

  c) WIRE n,s (d) WIRE s,nFigure 16: Wires for the rule F 5 (asymmetric). Recall that WIRE x,y is a wire from direction x to direction y with x, y ∈ {n (north), e (east), s (south), w (south)}. The state 1 (resp. -1) is represented as a black (resp. white) cell. Subfigures 16a to 16d represent the block during its evolution after a bit 1 arrived to the corresponding side. The other subfigures show the block in its initial state before any information arrives. Animations are presented on Appendix B.

	(e) WIRE s,e	(f) WIRE w,s	(g) WIRE n,w	(h) WIRE e,n
	(i) WIRE e,s	(j) WIRE n,e	(k) WIRE w,n	(l) WIRE s,w

  We now give the impulse response of the gadget: the B elements are supposed invariable during all the evolution, IN denotes what is received from IN by the gadget, OUT denotes what is sent to OUT from the gadget. Moreover, we assume that the cell at position OUT stays in state 1 during the evolution. As this it is not a square block of cells as required by definition 5 (in particular the B blocks are of size 2 × 2). However, it is straightforward to repeat it and pad with B blocks and all-+ This paper gives new hardness and universality results for the class of signed majority cellular automata. Apart from their use in various models arising in physics, they proved to be an interesting class of cellular automata to illustrate different levels of complexity and universality related to different kinds of circuit simulation. Results are summarized in the following tables:

	6. Conclusion
					B			time IN OUT
	IN Uniform Rules Complexity of problem Pred	+ Symmetric OUT -B N C 1 -Hard (Theorem 14) + +	t t + 1 Antisymmetric 0 1 t + 2 0 t + 3 0 ?	0 0 Asymmetric 1 0 P -Complete (Theorem 17)
	Complexity of f -Cycle problem	PTIME if f = 1, (Theorem 1) trivial else	?		?
	Universality		Not Intrinsically Universal (Theorem 14)	?		Turing Universal (Theorem 17)
	Maximun cycle						2	at least quadratic	super-polynomial
	length				(Theorem 1)	(Theorem 15)	(Theorem 16)
	• the OR element:
			IN2			time IN1 IN2 OUT
	IN1	+ +	-B	+	-	OUT	t t + 1 t + 2 t + 3	0 a 0 0	0 b 0 a ∨ b 0 0 0 0
	• the AND element:
			IN2			time IN1 IN2 OUT
	IN1	+ +	-B	+ +	OUT	t t + 1 t + 2 t + 3	0 a 0 0	0 b 0 a ∧ b 0 0 0 0

Table 2 :

 2 Summary of the complexity results for the uniform rules, classified in Symmetric, Antisymmetric and Asymmetric.

	Nonuniform Rules	Symmetric	Antisymmetric Asymmetric
	Complexity of problem Pred	P-Complete (Theorem 19)	?	P -Complete (Theorem 18)
	Complexity of f -Cycle problem	PTIME if f = 1, trivial else (Theorem 1)	?	PSPACE-hard (Theorem 18)
		Turing Universal,
		but not		Intrinsically
	Universality	Intrinsically	?	Universal
		Universal		(Theorem 18)
		(Theorem 19)
	Maximun cycle	2	at least quadratic	exponential
	length	(Theorem 1)	(Theorem 15)	(Theorem 18)

Table 3 :

 3 Summary of the complexity results for the non-uniform rules, classified in Symmetric, Antisymmetric and Asymmetric.

In the standard definition, the possibility to compose F or G with translations is added to the definition of rescaling: we remove this aspect from this paper to simplify and thus get a less general notion of intrinsic universality. However, everything can also be done up to translation everywhere.

Acknowledgements

Some of the authors would like to thank CONICYT-Chile under the grants FONDECYT 1140090 (E.G.), BASAL-CMM (DIM, U. Chile) (E.G.), ECOS C12E05 (E.G. and K .P) and Conicyt Becas Chile-72130083 (P.M.).

Non-Uniform Signed Majority Cellular Automata

In the non-uniform case we are able to prove that intrinsic universality can be achieved in general, but that the symmetry hypothesis prohibits it while still permitting Turing universality and P-completeness of the prediction problem.

Theorem 18. The non-uniform signed majority cellular automaton can simulate {AND,OR} circuitry in a re-usable way. It is therefore intrinsically universal by Proposition 11. Proof. The whole construction assumes that cells are in state 1 by default, which will represent the Boolean value 0. The Boolean value 1 is represented by cells in state -1, and these -1 values move along the circuit like sparse electrons. The movement of these electrons is controlled by the local sign matrix on each cell. The key point is to guarantee that cells go back to state -1 after the passage of these electrons.

In all the blocks gadgets given below the value on each side is simply given by a cell at a specific position. Therefore we only show the version of gadgets with all sides representing value 0. In each case we give the "impulse reponse" of the gadget showing that the desired value in computed at the output(s) at a precise time and that the gadget goes back to its initial state after the passage of electron thus ensuring re-usability.

• the background element:

The value of the cells in this block stay unchanged whatever the context. Moreover, we can aggregate cells with all-positive signs to these blocks to pad our gadgets to a common global square shape: an all-positive signed cell stays unchanged as soon as it is connected to 2 cells that

• the multiply element:

Theorem 19. The non-uniform symmetric signed majority cellular automaton can (weakly) simulate {AND,OR,CROSS} circuitry. It is therefore Turinguniversal and has a P-complete prediction problem. However, it cannot simulate {AND,OR} circuitry in a re-usable way and it is not intrinsically universal.

Proof. For the second part of the proof (impossibility to simulate re-usable monotone circuitry and non intrinsic universality) we proceed like in the proof of Theorem 14: by symmetry of the rule, Theorem 1 implies that the f -cycle problem is trivial when f is constant equal to 3. Therefore by proposition 11 these rules cannot be intrinsically universal and cannot simulate re-usable {AND,OR} circuitry. Figure 18 presents the elements required to apply Proposition 10. As in the asymmetric case, the CROSS gate is constructed using (¬west)And(north) and (west)And(¬north) gadgets.