Olivier Bournez
email: bournez@lix.polytechnique.fr

Daniel S Graça
email: dgraca@ualg.pt

Emmanuel Hainry
email: emmanuel.hainry@loria.fr

Computation with perturbed dynamical systems

Keywords: Dynamical systems, reachability, robustness, computational power, verification

This paper analyzes the computational power of dynamical systems robust to infinitesimal perturbations.

Previous work on the subject has delved on very specific types of systems. Here we obtain results for broader classes of dynamical systems (including those systems defined by Lipschitz/analytic functions).

In particular we show that systems robust to infinitesimal perturbations only recognize recursive languages. We also show the converse direction: every recursive language can be robustly recognized by a computable system. By other words we show that robustness is equivalent to decidability.

Introduction

Recently there has been a surge of interest on the field of computer aided verification. In particular, a topic that has deserved much attention is concerned with computer aided verification of hybrid/continuous systems [START_REF]Hybrid Systems: Computation and Control: 7th International Workshop (HSCC 2004)[END_REF]. The idea is to get an "as automatic as possible" procedure such that, having as input the description of a system, it could tell in finite time if the system satisfies a given property.

A property which has been addressed by many authors is the reachability problem, which is concerned with the long term behavior of the system. Briefly, this problem can be stated as follows: "given as input a region A and a point x 0 determine whether the trajectory starting on x 0 will eventually reach A."

The majority of results that appear in the literature tend to classify this problem as undecidable [START_REF] Moore | Unpredictability and undecidability in dynamical systems[END_REF], [START_REF] Branicky | Universal computation and other capabilities of hybrid and continuous dynamical systems[END_REF], [START_REF] Asarin | Achilles and the tortoise climbing up the arithmetical hierarchy[END_REF], [START_REF] Bournez | Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy[END_REF], [START_REF] Koiran | Closed-form analytic maps in one and two dimensions can simulate universal Turing machines[END_REF], [START_REF] Graça | Computability with polynomial differential equations[END_REF] (several references are given, since each one deals with a particular class of systems). The reason is simple: many systems are known to simulate Turing machines (e.g. simple classes of linear hybrid automata [START_REF] Henzinger | What's decidable about hybrid automata?[END_REF] or piecewise constant derivative systems [START_REF] Asarin | Reachability analysis of dynamical systems having piecewise-constant derivatives[END_REF]) and one can encode the Halting problem as a reachability problem. However, these simulations usually use exact real numbers, and thus infinite precision is required to get the previous undecidability results.

Due to the use of exact simulations, some authors have questioned the meaningfulness of such results, arguing that this undecidability is due to nonrobustness, sensitivity to initial values of the systems, and that it never occurs in "real systems" [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF]. For example, Martin Fränzle writes in [START_REF] Fränzle | Analysis of hybrid systems: An ounce of realism can save an infinity of states[END_REF] "Hence, on simple information-theoretic grounds, the undecidability results thus obtained can be said to be artifacts of an overly idealized formalization. However, while this implies that the particular proof pattern sketched above lacks physical interpretation, it does not yield any insight as to whether the state reachability problem for hybrid systems featuring noise is decidable or not. We conjecture that there is a variety of realistic noise models for which the problem is indeed decidable."

Several attempts were made to understand if the reachability problem becomes decidable in the presence of noise. This appears not to be clear and to deeply depend on the considered notion of noise: it was previously known that this problem was decidable for some classes of models, such as Timed Automata [START_REF] Alur | Automata for modeling real-time systems[END_REF] (independent to the issue of noise). However, it was also proved in [START_REF] Henzinger | Robust undecidability of timed and hybrid systems[END_REF] that small perturbations of the trajectory still yields undecidability for timed and hybrid systems. In opposition, using a different model for noise (infinitesimal perturbations), it was shown [START_REF] Fränzle | Analysis of hybrid systems: An ounce of realism can save an infinity of states[END_REF] that the reachability problem is decidable for a certain model of hybrid systems. This has been extended to several models [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF].

In [START_REF] Asarin | Noisy Turing machines[END_REF] it is shown that Turing machines exposed to small stochastic noise can decide the Halting problem, since its computational power when the error converges to 0 is ≈ Π 0 2 . The effect of noise was also studied in the context of neural networks. In [START_REF] Maass | Analog neural nets with gaussian or other common noise distributions cannot recognize arbitrary regular languages[END_REF] it is shown that analog neural net subjected to gaussian or other common noise distributions cannot recognize arbitrary regular languages. In [START_REF] Siegelmann | On the computational power of neural networks[END_REF] (see [START_REF] Siegelmann | Neural Networks and Analog Computation: Beyond the Turing Limit[END_REF] for a more throughout discussion) the authors show that some types of neural networks can simulate Turing machines. If arbitrary (possibly non-recursive) reals are authorized, it has been shown by same authors in [START_REF] Siegelmann | Analog computation via neural networks[END_REF] that any arbitrary language can be recognized by a neural network in exponential time, and that languages recognized in polynomial time correspond to non-uniform polynomial time, that is to say to languages recognized by circuits of polynomial size.

In this paper we will continue the work done in [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF], in which the authors consider several classes of widely used models of dynamical systems: Turing machines, piecewise affine maps, linear hybrid automata, and piecewise constant derivative systems. They introduce a notion of "perturbed" dynamics for each of these classes and then establish the computational power required to solve the reachability problem. Their idea is to use the reachability relation R: given two points x and y in the state space, they are in relation (denoted by xRy) if there is a trajectory from x to y. Then they perturb this relation in the following manner: given an ε > 0, xR ε y if there is a ε-perturbed trajectory from x to y (the precise definition depends if the system is discrete-time or continuoustime). Taking the limit (intersection) of the relations R ε when ε → 0, one obtains the relation R ω . They call the system robust if R = R ω . By other words, a system is robust if its reachability relation does not change under infinitesimal perturbations of the dynamics.

This idea of infinitesimal robustness has a close resemblance with the notion of "structural stability" for dynamical systems: a system A is structurally stable if, roughly, ε-perturbed systems converge to A as ε → 0, a concept widely studied in the dynamical system theory see e.g. [START_REF] Guckenheimer | Nonlinear Oscillations, Dynamical Systems, and Bifurcation of Vector Fields[END_REF], [START_REF] Hirsch | Differential Equations, Dynamical Systems, and an Introduction to Chaos[END_REF].

It is proved in [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF] that for Turing machines, piecewise affine maps, linear hybrid automata, and piecewise constant derivative systems, the relation R ω belongs to the class Π 1 0 (it is co-recursively enumerable), and moreover, any Π 1 0 relation can be reduced to a relation R ω of a perturbed system: any complement of a recursively enumerable set can be semi-decided by an infinitesimally perturbed system. This result shows that robustness implies decidability. Indeed, the reach set is recursively enumerable and if the system is robust, the complement of the reach set must be recursively enumerable, from which it follows that the reach set must be recursive for robust systems.

In short, the results of [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF] give a partial answer to the above mentioned conjecture: the reachability problem is decidable for certain classes of robust systems, if the notion of robustness is the one considered in [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF]. By other words, undecidability of verification arises only when non-robust systems are considered.

The aim of this paper is to extend the results of [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF] for the case of Lipschitz/analytic and computable (in the sense of recursive analysis [START_REF] Weihrauch | Computable Analysis: an Introduction[END_REF]) systems. This class of systems is very broad including any C k -system for k ≥ 1 (e.g. any system defined using the usual functions of analysis -polynomials, exponential, trigonometric functions, etc. -is Lipschitz). We present both continuous-time and discrete-time versions of our results. We therefore seek to strengthen the results of [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF]: verification of the reachability problem is decidable for robust systems considered in classical mathematics and computer science. These results suggest that undecidability of verification is really a by-product of nonrobustness, even if the system does not have the dynamics of Turing machines, piecewise affine maps, linear hybrid automata, and piecewise constant derivative systems as in [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF].

In a more provocative way, undecidability of verification for safety properties seems to be an artifact of modelization for very general and natural classes of systems.

The present paper is an extended journal version of preliminary results presented at the conference MFCS 2010 [START_REF] Bournez | Robust computations with dynamical systems[END_REF]. In particular, this paper differs from the conference version on the following points: first, the proofs of the results are fully detailed (and a minor correction is stated); second, we study both acceptance and recognition; third, results are extended for the case where the state space may be unbounded, sometimes at the price of more subtle arguments.

Since this paper deals with recognized/accepted languages in bounded/unbounded domains using discrete/continuous-time, each basic result will have several variants, depending on which hypothesis is being used. Since all these cases may yield some confusion, next we provide a small guide for the main results.

Overall, we have two main results in the paper: robustness implies recursiveness and its converse result. The results which show that robustness implies recursiveness are: Theorem 16 (bounded domain and discrete/continuous-time), Theorem 17 (unbounded domain, discrete-time), Theorem 18 (unbounded domain, continuous-time). For the converse result we have: Theorem 20 (unbounded domain, continuous-time), Theorem 21 (unbounded domain, discretetime), Theorem 22 (bounded domain, continuous-time), and finally Theorem 23 (bounded domain, discrete-time).

Throughout the paper we use the following assumptions: (i) unperturbed systems acting as language acceptors or recognizers are deterministic; (ii) words to be inspected for language membership are encoded by initial states rather than inspected sequentially by a dynamical system.

For the result stating that recursiveness implies robustness we use a particular coding of words into initial states. Albeit being restricted to this particular coding, we conjecture that our results can be extended to more general types of encodings.

We should also note that our results for bounded domains assume nonuniform robustness: the amount of robustness depends on the initial state. This is natural since we are coding infinitely many words as initial states in a bounded space and therefore the infimum of robustness (distance between initial states) over all (permissible, i.e. word encoding) initial states must be zero.

Notice that this paper discusses continuous time and discrete time dynamical systems in a uniform way, but separately. Some of the constructions then carry to hybrid systems, that is, to systems with continuous and discrete dynamics: on the one hand, it is possible to embed discrete time dynamical systems and continuous dynamical systems in well chosen classes of hybrid systems, and on the other hand it is possible to extend some of our constructions to approximate trajectories for continuous systems to hybrid systems. For succinctness, we do not fully discuss in this paper hybrid systems and refer instead the reader to [START_REF] Collins | Computability of finite-time reachable sets for hybrid systems[END_REF], [START_REF] Collins | Semantics and computability of the evolution of hybrid systems[END_REF].

Preliminaries

Computable analysis

In this paper we will deal with computable systems in the sense of computable analysis. This section briefly introduces some basic material from computable analysis.

The theory of computation can be rooted in the seminal work of Turing, Church, and others, which provided a framework in which to achieve computation over discrete identities or, equivalently, over the integers.

However, this definition was not enough to cover computability over continuous structures, and was then developed by other authors such as Turing himself [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF], Grzegorczyk [START_REF] Grzegorczyk | On the definitions of computable real continuous functions[END_REF], or Lacombe [START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles III[END_REF] to originate computable analysis (also known as recursive analysis).

The idea underlying computable analysis to compute over a set A is to encode each element a of A by a countable sequence of "simple" elements, called a name. Each sequence (name) can encode at most one element of A.

The more elements we have from a sequence encoding a, the more precisely we can pinpoint a. From this point of view, it suffices to work only with names when performing a computation over A. To compute with names, we use oracle Turing machines as in [START_REF] Ko | Computational Complexity of Real Functions[END_REF]. See [START_REF] Pour-El | Computability in Analysis and Physics[END_REF] or [START_REF] Weihrauch | Computable Analysis: an Introduction[END_REF] for other equivalent approaches to computable analysis.

In the present work we will encode a real number α by a sequence of dyadic rational number, i.e. by numbers with the format k/2 n , where k, n ∈ Z. In turn, each dyadic rational can be encoded by three natural numbers p, q, r ∈ N satisfying k 2 n = p -q 2 r and these three natural numbers can be encoded in just one number via wellknown polynomial-time computable bijections •, •, • : N 3 → N [START_REF] Odifreddi | Classical Recursion Theory[END_REF].

Formally (see [START_REF] Ko | Computational Complexity of Real Functions[END_REF]), let ν Q : N → Q be the following representation (many other natural representations of rational numbers can be chosen: they still yield the same class of computable functions -see [START_REF] Weihrauch | Computable Analysis: an Introduction[END_REF][START_REF] Ko | Computational Complexity of Real Functions[END_REF]) of dyadic rational numbers by integers: ν Q ( p, q, r ) → p-q 2 r , where •, •, • : N 3 → N is a polynomial-time computable bijection. Let us now introduce the notion of computable real point.

Definition 1. A sequence of integers (x i ) i∈N ∈ N N converges quickly toward x (denoted by (x i ) i∈N x) if |ν Q (x i ) -x| < 2 -i for all i ∈ N. Definition 2. A point x = (x 1 , . . . , x d ) ∈ R d is called computable if for all j ∈ {1, . . . , d}, there is a computable sequence (x i ) i∈N ∈ N N (i.e. a computable function a : N → N such that x i = a(i) for all i ∈ N) satisfying (x i ) i∈N x j .
We can also define computable functions.

Definition 3. Let X ⊆ R d . A function f : X ⊂→ R is called computable if there exists some d-oracle
Turing machine M such that, for all x = (x 1 , . . . , x d ) ∈ X and all sequences (x j i ) i∈N x j , M computes in finite time a value x i such that (x i ) i∈N f (x), provided M is given as input a value i ∈ N and as oracles the d sequences ( 1. An open set E ⊆ R n is called recursively enumerable (r.e. for short) open if there are computable sequences

x 1 i ) i∈N , . . . , (x d i ) i∈N . A function f : X ⊂ R d → R k is said computable if all its projections are.
{a i } i∈N ,{r i } i∈N of inte- gers such that E = ∪ ∞ k=0 B(ν Q (a k ), ν Q (r k )). where B(a, r) = {x ∈ E : x -a < r}. 2. A closed subset A ⊆ R n is called r.e. closed if there exist computable se- quence of integers {b j i } i∈N , for j = 1, . . . , n such that {(ν Q (b 1 i ), . . . , ν Q (b n i ))} i∈N is dense in A. A is called co-r.e. closed if its complement A c is r.e. open.
A is called computable (or recursive) if it is both r.e. and co-r.e.

An open set

E ⊆ R n is called computable (or recursive) if E is r.e. open
and its complement E c is r.e. closed.

Dynamical systems

In its essence a dynamical system is a pair consisting of a state space where the action occurs and a function f which defines the evolution of the system along time. Formally it can be defined as follows [START_REF] Hirsch | Differential Equations, Dynamical Systems, and Linear Algebra[END_REF]. Let S be the space of states and T the space of times (in general T needs only be a monoid, although usually T = Z -discrete-time systems -or T = R -continuous-time systems). Definition 5. A dynamical system is a triple (T , S, φ), where S is a set, T is a monoid, and φ : T × S → S is a function satisfying (we write φ t (x) = φ(t, x) for t ∈ T ):

1. φ 0 : S → S is the identity function, i.e. φ 0 (x) = x 2. φ t • φ s = φ t+s for every t, s ∈ T .

In this paper we will be concerned with systems defined on a continuous state space, i.e. where S ⊆R n is an open set. We will only consider discretetime (T = Z) and continuous-time systems (T = R). In the latter case, it can be shown [START_REF] Hirsch | Differential Equations, Dynamical Systems, and Linear Algebra[END_REF] that if φ is a C 1 function, then the continuous-time dynamical system can be written as a differential equation

x = f (x).
For this reason we will model continuous-time dynamical systems as ordinary differential equations and just say that (S, f ) is a continuous-time dynamical system. From Definition 5, it is also not difficult to infer that, for discrete-time dynamical systems, we can reconstruct φ just knowing g = φ 1 since (for t > 0. A similar reasoning applies for the other cases)

φ t (x) = g(g(• • • g t times (x) • • • ).
For this reason we will just say that (S, g) is a discrete-time dynamical system. Now we can introduce the notion of trajectory. Definition 6. Let S ⊂ R d , and consider some function f : S → S. Then a trajectory associated to the dynamical system (S, f ) is:

• A sequence of points {x 0 , x 1 , ...} ∈ S N , satisfying f (x i+1 ) = x i for all i ∈ N, for discrete-time dynamical systems.

• A solution of the differential equation ẋ = f (x), x(0) = x 0 ∈ S for continuous-time dynamical systems

In this paper we consider dynamical systems as recognizers of languages. Let Σ denote the alphabet Σ = {0, 1} and Σ * denote the set of words over this alphabet. To recognize a language with a dynamical system, we need to encode words of Σ * as points of S. Here we use a variation of the encoding defined in [START_REF] Graça | Robust simulations of Turing machines with analytic maps and flows[END_REF], [START_REF] Graça | Computability with polynomial differential equations[END_REF]. In this latter paper a word w = w 0 . . . w n ∈ Σ * can be encoded as an integer y = w 0 + w 1 2 + . . .

+ w n 2 n . (1)
In this paper we will consider two cases: (i) the state space is compact (bounded) and (ii) the state space is R n (unbounded). For the latter case one can consider the encoding [START_REF]Hybrid Systems: Computation and Control: 7th International Workshop (HSCC 2004)[END_REF]. For the compact case we consider, without loss of generality, that S =[-1, 1]. We can then encode a word w ∈ Σ * in the state space S using the encoding v : Σ * → S defined by

v(w) = 2 π arctan(w 0 + w 1 2 + . . . + w n 2 n ). (2)
In order to avoid pathological behaviour which may trivially lead to noncomputability, we assume that computation in a dynamical systems setting has the following property: the computation is carried out in a region V compute and, when the computation should finish, it diverges to regions V accept and V reject (depending on if the word should be accepted or rejected). We assume that the (Hausdorff) distance between these 3 regions is non-zero so that we can distinguish them in finite time. This assumption is done to avoid trivial undecidability due to the impossibility of distinguishing two reals in the recursive analysis setting.

We can now put all pieces together to obtain the following definition.

Definition 7 (Considering a dynamical system as a language recognizer).

Let Σ be an alphabet, H a discrete/continuous-time dynamical system over space S. Let V compute , V accept , V reject ⊆ S be computable sets and σ : Σ * → V compute be a map satisfying the following requirements:

1. The Hausdorff distance between any pair of sets from the following: V compute , V accept , V reject is non-zero; 2. There is a connected open set A which overlaps V compute and V accept , but such that A ∩ V reject = ∅ (by other words, there are paths which go from V compute to V accept , without crossing V reject ). 3. There is a connected open set B which overlaps V compute and V reject , but such that B ∩ V accept = ∅.

4.

Once a trajectory reaches V accept or V reject , it stays there.

We say that H accepts a language L ⊂ Σ * (or that L is the language of H), if the following holds: for all w ∈ Σ * , w ∈ L if the trajectory of H starting from σ(w) reaches V accept . If w ∈ L, we require that the corresponding trajectory always stays in V compute or goes to V reject .

We say that H recognizes a language L ⊂ Σ * (or that L is decided by H), if the following holds: for all w ∈ Σ * , if w ∈ L then the trajectory of H starting from σ(w) reaches V accept ; if w ∈ L then the trajectory of H starting from σ(w) reaches V reject .

We finish this section by recalling the notion of Lipschitz function.

Definition 8. A function f : X ⊆ R m → R k is said Lipschitz over a set if there is some K > 0 such that for all x, y ∈ X one has f (x) -f (y) ≤ K x -y .
(3)

A function f : E → R m , E ⊆ R l , is said to be locally Lipschitz on E if it satisfies a Lipschitz condition on every compact set V ⊆ E.
In particular it is well known that C 1 functions are locally Lipschitz over R n , which imply that they are Lipschitz over a compact set X ⊆ R m . In [START_REF] Graça | Computability, noncomputability and undecidability of maximal intervals of IVPs[END_REF] a notion of effectively Lipschitz function was presented, which will be used on what follows.

Definition 9. Let E = ∪ ∞ n=0 B(a n , r n ) ⊆ R l ,
f (x) -f (y) ≤ K n x -y whenever x, y ∈ B(a n , r n ).
In particular, it can be shown [START_REF] Graça | Computability, noncomputability and undecidability of maximal intervals of IVPs[END_REF] that any C 1 computable function on R l is effectively Lipschitz.

Robustness

Before proceeding with our results, we recall the notion of robustness from [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF], based on an idea of [START_REF] Puri | Dynamical properties of timed automata[END_REF]. This will be the notion of robustness used throughout this paper.

Definition 10 (ε-perturbation). Consider a discrete/continuous-time dynamical system H = (X, f ). Given ε > 0, its ε-perturbation H ε is the discrete/continuous-time system H ε defined over the same space X, where:

1. (x 0 , x 1 , ...) is a (ε-perturbed) trajectory of H ε , in the case where H is discrete-time, if x i+1 -f (x i ) ≤ ε for all i ∈ N; 2. φ : R + 0 → X is a (ε-perturbed) trajectory of H ε , in the case where H is continuous-time, if φ(0) ∈ X and φ (t) -f (φ(t)) ≤ ε for all t ∈ R + 0 .
Notice that the system H ε is not, in general, deterministic. Since we are interested in robust recognition of languages by a system, our next goal is to introduce an appropriate definition of robust recognition. Some care is needed, since it may happen that a perturbed system has trajectories which go to V accept and to V reject . Definition 11. Let H ε be a perturbed system.

1. The language L ε ⊆ Σ * accepted by the system H ε is formed by all words w ∈ Σ * such that there is an ε-trajectory starting from σ(w) which reaches V accept . 2. The language K ω is formed by all words w ∈ Σ * with the property that, for each w ∈ K ω , there is an ε > 0 such that all trajectories of H ε with origin in σ(w) vanish in V reject .

The language K ω can be seen as the set of words "easy to reject".

Definition 12 (Robustness).

A dynamical system H is said to have robust recognition if the language L it recognizes has the following properties:

(i) if w ∈ L then w ∈ L ε for every ε > 0; (ii) if w / ∈ L then w ∈ K ω .

Main results

We are now ready to present the main results of our paper. Section 3.1 shows that, for bounded domains, any language which can be robustly recognized is recursive. Section 3.2 shows a similar result, but for unbounded domains. Then in Section 3.3 we show the converse result: any recursive language can be robustly recognized by some system.

Bounded domain

Before presenting the main result of this section, let us present an auxiliary result, first for discrete-time systems, and later for continuous-time systems.

Theorem 13. Let H = ([-1, 1] d , f ) be a discrete-time system, where f is Lipschitz and computable. Then the set K ω is recursively enumerable.

Proof. Let n ∈ N\{0} and S = [-1, 1] d . One can decompose S in d- dimensional hypercubes V 1 , ..., V s of size 1
n . Using this decomposition we build a finite automaton A n , whose states are V 1 , ..., V s , that roughly recognizes L 1 n . To complete the description of this automaton we need to define two things: (i) the set of accepting states and (ii) the transition rule δ n . The set of accepting states consists of those hypercubes which overlap V accept . These hypercubes can easily be identified since the set V accept is computable (since we are only dealing with accepted languages, there is no need to consider V reject ). Now let us present the transition rule of A n . The following construction is depicted in Fig. 1. Let V j be some hypercube. Then pick its central point x j (this is an easily computable rational) and compute a rational approximation f (x j ) of f (x j ) with precision 1 n . Because f is Lipschitz, there will be some Lipschitz constant K > 0 satisfying condition (3) for all x, y ∈ X. Then, if x ∈ V j is another point of the same hypercube and y is an ε-perturbed image of f (x), with ε = 1/n, we have

f (x) -y ≤ 1 n ⇒ (4) f (x j ) -y ≤ f (x j ) -f (x j ) + f (x j ) -f (x) + f (x) -y ≤ K + 2 n .
By other words, if y is an ε-perturbed image of a point of V j , then this point will be within distance K+2 n of f (x j ). We use this fact in what follows. We use the following algorithm to show that K ω is r.e. First compute a rational approximation f (x j ) of f (x j ) with precision 1 n . After computing f (x j ), determine all the hypercubes which are within distance ≤ (K +2)/n of this point (in Fig. 1 this corresponds to all hypercubes covered by the ball of center f (x j ) and radius (K + 2)/n). This can be done algorithmically, in finite time, since it is only necessary to check which are the hypercubes (which are finitely many) that have vertices within distance ≤ (K + 2)/n of f (x j ). Let W 1 , ..., W i be these hypercubes. Then we define the transition rule over the hypercubes as follows: δ(V j ) = {W 1 , ..., W i }. This defines the automaton A n . Now we say that a point x ∈ X is accepted by A n if it lies in an accepted hypercube. Let L 1 n be the language accepted by A n . It is easy to conclude that the dynamics of A n includes those of the 1 n -perturbed system H 1 n . Hence L 1 n ⊆ L 1 n . On the other side, using (4), it is not difficult to see that the dynamics of A n are included in those of H K+3 n (here we suppose that x = x ∞ = max 1≤i≤n |x i |. However, a similar result holds for other norms since all norms are equivalent in a finite-dimensional space). Therefore

L 1 n ⊆ L 1 n ⊆ L K+3 n ⇒ ∩ ∞ n=1 L 1 n = ∩ ε>0 L ε = L ω .
Let us now show that K ω is recursively enumerable. Let w ∈ K ω . We notice that if w belongs to K ω , then there will be some n 0 ∈ N such that for all n ≥ n 0 , w / ∈ L 1 n . Reciprocally, if w / ∈ L 1 n for some n ∈ N, then w ∈ K ω . Moreover we can decide in finite time, using the automaton A n , whether w ∈ L 1 n . All these facts can be used to show that the following algorithm accepts words which belong to K ω in finite time: i=0 Repeat i++ Simulate A i with input ν X (w) Until ν X (w) vanishes in V reject using the dynamics of A i Accept w This algorithms accepts in finite time exactly those words which belong to K ω . By other words, it shows that K ω is r.e., as required.

Next we present a similar result for continuous-time systems. This result can be obtained by using a construction presented in [START_REF] Puri | Epsilon-approximation of differential inclusions[END_REF].

Theorem 14. Let H = ([-1, 1] d , f
) be a continuous-time system, where f is Lipschitz and computable. Then the set K ω is recursively enumerable.

Proof. The proof of this theorem is essentially the main result from [START_REF] Puri | Epsilon-approximation of differential inclusions[END_REF]. There the authors show that given a differential inclusion x ∈ f (x) (case where f can be multivalued) one can compute an arbitrary over-approximation of the flow for this differential inclusion, with error bounded by input > 0, by means of polygons. Therefore, if f is just a "normal" function (not multivalued), and f (x) = [f (x)-, f (x)+ ], we can over-compute the flow , x(t 0 ) = x 0 , x ∈ f 1 n (x) with precision 1 n . Since we are on a compact, we can decide in finite time whether this polygonal over-approximation A n vanishes entirely in V reject or not. If w ∈ K ω , then for some over-approximation A n0 (and all over-approximations A n , with n ≥ n 0 ), the trajectory starting on (the coding of) w will vanish in V reject . Reciprocally, if all the trajectories starting in (the coding of) w vanish entirely in V reject using the dynamics of some over-approximation A n0 , then w ∈ K ω . Now consider the following algorithm: i=0 Repeat i++ Compute A i for input ν X (w) Until ν X (w) vanishes in V reject using the dynamics of A i Accept w This algorithm accepts in finite time exactly those words which belong to K ω . By other words, it shows that K ω is r.e., as required.

The following result is a corollary from the results of [START_REF] Collins | Continuity and computability of reachable sets[END_REF], [START_REF] Collins | Effective computability of solutions of differential inclusions -the ten thousand monkeys approach[END_REF]: one can compute any trajectory of H. Therefore one can semi-decide if a trajectory finishes in V accept , and thus semi-decide L.

Corollary 15. Let L be the language accepted by a (continuous-time or discretetime) system H = (S, f ), where f is Lipschitz and computable. Then L is r.e.

Proof. We recall that the trajectory of a dynamical system H is computable for all times [START_REF] Collins | Effective computability of solutions of differential inclusions -the ten thousand monkeys approach[END_REF]. Moreover, by hypothesis, the Hausdorff distance between V compute , V accept and V reject is non-zero and bounded by below by some rational δ > 0. The following algorithm accepts w in finite time iff w ∈ L (φ(t, x) gives the point of the trajectory starting at point x for t 0 = 0, for time t -see Definition 5):

i=0 Repeat i++ Compute φ(i, ν X (w)) with precision δ/2 Until φ(i, ν X (w)) ∈ A Accept w where A is a finite over-approximation of V accept (which can be computed in finite time) satisfying dist(V accept , A) < δ/2. If w / ∈ L, then φ(i, ν X (w)) ∈ V reject ∪ V compute
for all i∈ N and the algorithm will never reach the set A and thus will run forever. If w ∈ L, there will be some i∈ N such that φ(i, ν X (w)) ∈ V accept and thus its δ/2-estimate will reach A and stay there. Therefore this algorithm shows that L is r.e.

Since a set is recursive (computable) if it is r.e. as well as its complement (see for example [START_REF] Odifreddi | Classical Recursion Theory[END_REF]), it follows trivially that a robust system must compute recursive languages.

Theorem 16 (Robust acceptation => recursive ). Assume that language L is robustly accepted by a system H = ([-1, 1] d , f ), where f is Lipschitz and computable. Then L is recursive.

Proof. L is r.e. by Corollary 15. Moreover, because the system is robust, the complement of L is K ω , which is r.e. by Theorems 13 and 14. Hence L must be recursive.

Unbounded domain

We now present similar results to those of Section 3.1, but with the difference that they are valid for unbounded domains. Note that the proof of Theorem 13 is only valid for bounded domains, so it must be adapted to deal with unbounded domains. Here the hypothesis of recognition will be important.

Theorem 17 (Robust recognition => recursive I). Let L be a language robustly recognized by a discrete-time system H = (R d , f ), where f is effectively locally Lipschitz and computable. Then L is recursive.

Proof. If w ∈ L then, for ε small enough, any ε-perturbed trajectory will enter in a time T the accepting region (if w / ∈ L these trajectories will enter in a time T the rejecting region). Then all ε-perturbed trajectories (for an input w) will stay inside some compact set A, where a Lipschitz condition holds, with some Lipschitz constant K which can be computed since f is effectively Lipschitz. Then proceeding as in the proof of Theorem 13, substituting A for [-1, 1] d , one gets the result.

A similar proof shows the following theorem.

Theorem 18 (Robust recognition => recursive II). Let L be a language robustly recognized by a continuous-time system H = (R d , f ), where f is effectively locally Lipschitz and computable. Then L is recursive.

Recursiveness implies robustness

We now want to prove that any recursive language can be recognized by a robust system. By other words, we want to show the converse direction of Theorem 16 (and its unbounded variants, Theorems 17 and 18). This equals to show that every Turing machines can be simulated robustly by a (effectively) Lipschitz and computable system. We will analyze the cases in which the state space is (i) unbounded and (ii) bounded. The former case is an immediate consequence of the following theorem from [START_REF] Graça | Computability with polynomial differential equations[END_REF].

Theorem 19. Given some Turing machine M , there is an analytic and computable ODE y = g M (y) defined over R 6 which robustly simulates M using the encoding (1), and which is robust to perturbations ε ≤ 1/4.

In particular this theorem yields the following corollary, which shows the converse direction of Theorem 18:

Theorem 20 (Recursive => robust recognition). Let M be a Turing machine. Let L be the language recognized by M. Then for the system y = g M (y) of Theorem 19 one has L = L ε for ε ≤ 1/4. Moreover, any ε-perturbed trajectory starting in (a coding of ) w / ∈ L will vanish in V reject for ε ≤ 1/4. In particular the complement of L is K ω i.e. there is a computable and effectively Lipschitz system y = g M (y) which robustly recognizes L.

In [START_REF] Graça | Computability with polynomial differential equations[END_REF], the proof of Theorem 19 is obtained by first defining a map that simulates a Turing machines robustly to errors using the encoding (1), and which is robust to perturbations ε ≤ 1/4. Using this map instead of the differential equation, we can obtain the discrete-time counterpart of the previous theorem. Theorem 21. Let M be a Turing machine. Let L be the language recognized by M . Then there is a discrete-time system H = (R 3 , f ), where f is computable and effectively Lipschitz, which robustly recognizes L.

For the bounded version of this result (or, more correctly, a variant of it), we need to look at more detail how the simulation of the Turing machine M is achieved by the system y = g M (y). Basically, the first component of this system will be used to store the left side of the tape (using the encoding (1)), the second component will be used to store the right side of the tape, and the third component is used to store the state coded as an integer. Without loss of generality, the TM can be supposed to have only two final states, one accepting and another rejecting. We can also suppose that the states are coded into integers {1, . . . , m}, where 1 is the rejecting state, m is the accepting state, and 2 is the initial state. Once a trajectory reaches a final state (point), it stays there (modulo ε -see below).

The last 3 components of y = g M (y) are used as memory for the main simulation. This simulation is robust to errors in the sense that for any 0 < ε < 1/4, one can perturb any of these trajectories up to an amount ε and still be able to simulate M . Now we use the previous construction to simulate M on a compact set X = (-1, 1) 6 . If φ is a solution of y = g M (y) simulating M on R 6 , we can pick

φ 1 = 2 π arctan φ (and hence φ = tan φ1π 2
) as the corresponding simulation of M on (-1, 1) 6 . In general

φ 1 = ( 2 π arctan φ) = 2 π 1 1 + φ 2 φ = 2 π 1 1 + φ 2 g M (φ) =⇒ (5)
φ 1 = 2 π 1 1 + φ 2 g M (φ) = 2 π 1 1 + tan 2 φ1π 2 g M tan φ 1 π 2 = f M (φ 1 ) where f M (x) = 2 π 1 1 + tan 2 xπ 2 g M tan xπ 2 .
Hence, the system y = f M (y) simulates M on X, with input w coded by v(w), where v is given by (2). Moreover, robustness among states still exists, and the simulation of M can be carried out if the states are not perturbed more than ε = arctan(m + ε) -arctan(m)

We now show that any recursive language can be robustly recognized by an analytic and computable system in a bounded set. Note that since the set is open (although bounded), the function defining the system is not necessarily Lipschitz. Indeed, it is conjectured that there are recursive languages which cannot be accepted by any analytic system defined on a compact, finite dimensional space through a reasonable input and output encoding [START_REF] Moore | Finite-dimensional analog computers: Flows, maps, and recurrent neural networks[END_REF]Conjecture 2]. By other words, if this conjecture holds, some recursive language can only be recognized by analytic systems on bounded non-closed sets, and that's the reason why we used an open set. Of course, the system is effectively Lipschitz over its state space though the question of knowing whether a Lipschitz and computable system can robustly recognize a given recursive language remains open.

Theorem 22 (recursive => robust recognition, bounded case). Let A be a recursive language. Then there is an analytic and computable continuous-time system over S = (-1, 1) 6 which robustly recognizes A.

Proof. Pick ε = 1/4 and let M be a Turing machine which recognizes language L. Consider the construction depicted above. From all of the above, we have a dynamical system H defined with an ordinary differential equation ( 5) which allows us to robustly simulate M on the compact space S. There will be a component of (5) (the third) which will give the state of M . The state is coded by the numbers arctan(1), arctan(2), . . . , arctan(m), where arctan(1) is the rejecting state and arctan(m) is the accepting state. The idea is to pick V compute as the region which overlaps the states arctan(2), . . . , arctan(m -1) modulo the allowed error ε given by [START_REF] Koiran | Closed-form analytic maps in one and two dimensions can simulate universal Turing machines[END_REF]. V accept and V reject are defined similarly. Then one simulates M with a system like [START_REF] Bournez | Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy[END_REF]. For each trajectory simulating a computation, the trajectory will remain in V compute until the computation accepts or reject. At this point the trajectory goes to V accept or V reject , respectively and stays there. Note that there is a gap between these sets, since their Hausdorff distance is δ = min{a -c, d -b} > 0. Remark also that, since L is recursive, the computation of M will always halt for a given input w ∈ Σ * and therefore the contents of the tape will not grow beyond a certain amount size(w) for a given input w (bigger words will be on the region 2 π arctan size(w), 1 ). Therefore, since the function g M is robust to errors, we will still be able to proceed the computation with some robustness, namely with errors less than or equal to γ = arctan(size(w) + ε) -2 π arctan size(w) (the amount of error depends on the input, but this is not a problem for us. The important is that there is robustness). Therefore, for all δ ≤ γ: (i) if w ∈ L, then w ∈ L δ (the δ-perturbed language of the system H), (ii) if w / ∈ L, then all δ-perturbed trajectories vanish in V reject . Therefore this system robustly recognizes L.

Proceeding similarly, but now using the robust map that simulates Turing machines from [START_REF] Graça | Computability with polynomial differential equations[END_REF] instead of the differential equation, one obtains the following result.

Theorem 23. Let L be a recursive language. Then there is an analytic and computable discrete-time system over S = (-1, 1) 6 which robustly recognizes L.

Conclusion

In this paper we showed that, on compact sets, robustness of dynamical systems in the sense of [START_REF] Asarin | Perturbed Turing machines and hybrid systems[END_REF] is equivalent to decidability. It would be interesting to know what happens at a more refined level, i.e. if from a complexity point of view.

Finally

  , we provide the notion of computable open and closed set (cf. [21], Definition 5.1.15).

Figure 1 :

 1 Figure 1: A figure depicting various elements used in the demonstration of Theorem 13.

Figure 2 :

 2 Figure 2: Computing regions for the proof of Theorem 22.More precisely, defineV compute = [a, b] × (-1, 1)5 where a, b are rationals satisfyingarctan 1 + ε < a ≤ arctan 2 -ε arctan(m -1) + ε ≤ b < arctan m -ε,where ε is given by (6), V reject = (-1, c]×(-1, 1) 5 where c is a rational satisfying arctan 1 + ε ≤ c < a, and V accept = [d, 1) × (-1, 1)5 , where d is a rational satisfying b < d ≤ arctan(m) -ε. These regions are represented in Fig.2. Note that there is a gap between these sets, since their Hausdorff distance is δ = min{a -c, d -b} > 0. Remark also that, since L is recursive, the computation of M will always halt for a given input w ∈ Σ * and therefore the contents of the tape will not

Acknowledgements. We would like to thank the anonymous referee for helpful corrections and suggestions which helped to improve the paper.

$ This work has been partially supported by the INRIA program " Équipe Associée" Com-putR. D. Graça was partially supported by Fundação para a Ciência e a Tecnologia and EU FEDER POCTI/POCI via SQIG -Instituto de Telecomunicações through the FCT project PEst-OE/EEI/LA0008/2011.


Edgard Ngaboyamahina

Hubert Cachet

Alain Pailleret

Eliane M M Sutter

Electrochemical impedance spectroscopy characterisation of conducting polymer / TiO 2 nanotube array hybrid structures

Keywords: EIS, titanium oxide, nanotube array, polypyrrole, PEDOT

est destinée au dépôt

Electrochemical impedance spectroscopy characterization of conducting polymer/TiO2 nanotube array hybrid structures

Introduction

Electronically Conducting Polymers (ECPs) are materials of increasing interest for application in fields such as supercapacitors, electrochromic devices, biosensors, electrocatalysts [1][2][3][4][5][6][7][8][9][10]. ECPs have been widely studied when deposited on usual electrode materials with metallic behaviours (platinum, gold, glassy carbon….) and electrochemical impedance spectroscopy (EIS) has been shown to be a convenient method for investigating the transport properties of these mixed ionic/electronic conductors [2,4,5,[11][12][13][14][15][16][17][18][START_REF] Garcia-Belmonte | Bisquert Electrochim[END_REF][20][21]. Several 1 Corresponding author : Email : eliane.sutter@upmc.fr Phone : +33 (0) 1 44 27 41 68 models have been suggested for describing the behaviour of ECPs on platinum. A complete model has been first suggested by Vorotyntsev et al [12] for a metal/ECP film/electrolyte system, taking into account the fluxes of electronic and ionic species at the different interfaces and in the polymeric film. Later on, Deslouis and co-workers [13,14] applied this model on conducting polymer films under different boundary conditions (electrolyte/film/electrolyte, metal/film/metal and metal/film/electrolyte) and determined interfacial and transport parameters in the case of a polypyrrole film on a flat platinum electrode in different electrolytes. At last fine theoretical works were developed by Vorotyntsev et al [15][16][17] taking into account both the capacitive charging effects and the mixed electron-ion exchange across the film/solution interface.

Attempts to deposit ECP films on a nanostructured 3D substrate have been recently described [18][START_REF] Garcia-Belmonte | Bisquert Electrochim[END_REF][20][21][22][23][24][25][26][27][28][29][30]. For instance, deposition of PPy or PEDOT on titanium oxide nanotube arrays (TiO 2 -NTAs) is expected to produce innovative 3D junctions with interesting characteristics and performances for applications in the fields of energy storage, photoelectric devices or solar cells [22,29]. Due to the semiconducting properties of TiO 2 , the rate of polymerization of the monomer has been shown to be enhanced by light excitation in the anodic potential range (electrophotopolymerization) [26,28,30,31].

The present paper shows preliminary results with the aim of verifying if the approximate theoretical model proposed in Ref. [14] can be extended to the case of an ECP film deposited on a semiconducting nanostructured substrate. It has been shown [30] that electrochemical or photoelectrochemical deposition of PPy on TiO 2 -NTAs provides an electroactive hybrid structure, but that the level of electroactivity depends on the electrolyte used during the deposition step, on the anodic potential and on the illumination conditions. EIS appears to be a convenient method for estimating the electronic and ionic conductivities of the hybrid structure, yet for need of comparison a single model is likely to be used, whatever the conditions of ECP formation. Since the model of ref [14] allows taking separately into account the contribution of diffusion-migration of ionic and electronic charge carriers inside the film, and charge transfer across substrate/ polymer and polymer/electrolyte interfaces, we will focus in this work on the modification of the conducting properties of the substrate in the presence of a PPy and of a PEDOT film. The model will be used to compare the behaviours of hybrid PPy/TiO 2 -NTA structures obtained under potential scan in two different electrolytes: sodium dodecylbenzenesulfonate (SDBS) in which PPy film is mainly a cation exchanger and lithium perchlorate in which PPy behaves like an anion exchanger film [32]. A particular emphasis is also placed on the role of UV light illumination during the electrochemical generation of PPy, since it has been shown that photoelectrodeposited films often leads to hybrid structures with higher conductivity [26,28]. Since previous studies [10,18,29] have shown the higher stability of PEDOT in comparison with PPy, the behaviour of a PEDOT-TiO 2 structure will also be investigated in LiClO 4 to check if the model suggested in [14] for PPy deposit is also valid for a PEDOT film photoelectrodeposited from an acetonitrile solution. The modification of the semiconducting characteristics of TiO 2 NTAs (anatase type) covered with either a PPy or a PEDOT film will be discussed and compared in this work.

Experimental part

Synthesis of TiO 2 -NTAs

Prior to anodic oxidation, titanium discs (thickness 2 mm, diameter 15 mm, purity 99.6 %, purchased from Goodfellow) were polished with silicon carbide abrasive paper (P1200), and then rinsed first with ethanol, and finally in water in an ultrasonic bath.

Thereafter the Ti discs were anodized in a 3 wt% NH 4 F solution in ethylene glycol containing 2 vol% deionised water using a large area platinum counter electrode in a two electrode setup.

The oxidation was performed at room temperature (21°C) under a constant potential of 20 V vs. Pt for 45 min.

Once anodized, samples were ultrasonically rinsed in ethanol and deionised water successively. At last, they were annealed at 525 °C for 2 h so as to convert the amorphous TiO 2 structure into a well crystallized anatase structure which has been thoroughly characterized [33]. Anodization of the Ti substrate led to dense and homogeneous TiO 2 -NTAs. Raman spectrometry and XRD spectrometry showed that anatase was the only component of the layer. The tubes exhibited smooth walls and were highly-ordered and vertically oriented as it can be seen on the FEG-SEM pictures in inset of Fig 1 . In our case, the flat surface of the samples (working electrode) exposed to the electrolyte, i.e. the geometric surface, S geo , equals 0.78 cm 2 . The internal and external radii of the nanotubes, are 21 and 31 nm respectively, the length is about 960 nm and the mean thickness of the walls about 10 nm.

Electropolymerization of the monomers

Fresh aqueous solutions of 0.1 M distilled pyrrole monomer were prepared in different 0.1 M supporting electrolytes, either sodium dodecylbenzenesulfonate (SDBS) or lithium perchlorate (LiClO 4 ). The resulting polymers are respectively named either PPy(DBS) or PPy(ClO 4 ). In the case of SDBS, the selected concentration value is much higher than the value of critical micellar concentration (CMC), which has been shown to be about 1.5 mM in aqueous solution [34]. It has to be underlined that PPy deposition performed in similar conditions led to poorly adherent layers on compact titanium oxide samples, whereas the layer on nanostructured oxide layers showed good adherence.

Poly(3,4-ethylenedioxythiophene) (PEDOT) films were obtained from 0.05 M EDOT solutions in as-received acetonitrile solution containing 0.1 M LiClO 4 . Electropolymerization was carried out on a TiO 2 -NTA used as a working electrode by cyclic voltammetry between -0.7 and 1.4 V vs. Ag wire, at a scan rate of 100 mV/s, and at room temperature (21 °C). All the polymer layers studied in this work were obtained after 40 consecutive scans. For UV assisted electropolymerization, i.e. photoelectropolymerization experiments the samples were illuminated with a 125 W mercury vapour lamp (HPR 125 W (Philips), wavelength range: 300-400 nm). The UV light source was placed at a distance of 25 cm from the working electrode and the UV beam was perpendicular to the working electrode surface.

Characterization

The morphology of the resulting hybrid structures was studied by FEG-SEM (Zeiss, Ultra 55) (Fig 1 a-c). A Jobin-Yvon (Labram 010) Raman spectrophotometer equipped with a He-Ne laser (wavelength 632.8 nm) was used to confirm the structure of the polymer films as well as their oxidation state. The thickness of the deposits was difficult to estimate precisely with SEM method but was estimated to be around 1 to 2 m in the different cases.

From the deposition charges, the average thickness estimated is also very approximate, since the deposit is not uniform, the coverage rate is uncertain, and the current measured under light exposure is partially due to water oxidation. Nevertheless, a very rough estimation taking a deposition area of 0.78 cm 2 , a density of 1.54 for the PPy film, would lead to a thickness of 0.4 m and 1.4 m in LiClO 4 , respectively in the dark and under UV light. In the same way, the thickness in SDBS would be close to 0.5 m under UV light, and negligible in the dark.

Electrochemical characterization of the polymer films obtained after 40 cycles was performed in the dark, in a three-electrode cell, performed in the same supporting electrolyte as that used for the syntheses but without Py or EDOT monomer. During characterization of the hybrid structure, the shape of the voltammogram changes in the course of cycling, reaching a steady response after a few cycles. For PPy deposits, all the potentials are referred to a saturated calomel reference electrode (SCE), whereas for PEDOT films, an Ag wire was used as reference. In a separate experiment, the potential of the pseudo-reference Ag in acetonitrile was measured against a SCE dipped in an aqueous solution, and we found E Ag = -0.03V /SCE. Thus all the potential values are given against the SCE throughout the manuscript. The counter-electrode was a platinum spiral wire. The electrochemical characterization was An electrochemical interface (Solartron SI 1287) and a frequency response analyzer (Solartron 1250) were used to perform electrochemical impedance spectroscopy (EIS). Measurements were performed at a potential value selected inside a potential range shown to encompass the oxidation/reduction (i.e. doping/undoping) process of the polymers. Thus the investigated potential range was between -1.0 and 0.5 V vs. SCE in the presence of PPy films and between -0.4 V and 0.8 V vs SCE in the presence of PEDOT films. EIS measurements were performed sequentially starting from the cathodic potential range towards the anodic range by 100 mV steps, over frequencies ranging from 10 kHz to 0.1 Hz, using a 10 mV (peak to zero) sinusoidal potential modulation. The different impedance parameters involved in the selected EIS model were obtained by a regression procedure based on a simplex strategy using the software SIMAD developed in our laboratory. (See Appendix)

Results and discussion

The EIS model

For the determination of quantitative transport and interfacial parameters of ECP/TiO 2 -NTAs hybrid structures, the theoretical expressions for the ac impedance were fitted to the experimental data. According to ref [14], the theoretical expressions of impedance Z for a PPy film on a metallic substrate are the following:

me s Z R Z   (1) With p Z C j Zi Z C j Z me Z Z i i e e e        1 1 (2)
where R s is the electrolyte resistance, Z e is the impedance at the substrate/polymer interface characterized by transfer resistance R e and interfacial double layer capacitance C e, Z i is the impedance at the polymer /electrolyte interface characterized by transfer resistance R i and interfacial double layer capacitance C i, and Z p is the impedance of the polymeric film with resistance R p Assuming that the diffusion coefficient of electrons D e is much higher than the diffusion coefficient of ions D i in the polymeric film, the expressions for Z e , Z i and Z p are:

             th D D R R Z i e p e e coth 8
(3)

             th D D R R Z i e p i i coth 8 (4)           th D D R R Z i e p p p 4 (5) i D d j 8 2 2    and i D d 8 2   ( 6
)
d is the polymer film thickness,  is angular frequency , j= 1  , and  is a time constant related to ion diffusion in the film.

Due to the presence of a semiconducting substrate, an additional impedance Z sc has to be taken into account, with

sc sc sc sc C R j R Z    1 (7)
where C sc is the space charge layer capacitance and R sc the internal resistance of the semiconductor. For most experiments Z sc and Z me are in series (scheme (a) in Fig. 2), corresponding to the case where the polymer film entirely covers the TiO 2 substrate. In the case of SDBS the previous model does not allow representing the experimental data. Thus in order to obtain parameter values with physical meaning, it was necessary to add a resistance in series with Z sc (scheme (b) in Fig. 2). This additional resistance R ad is attributed to a very thin poorly conductive PPy film deposited on some areas of the semiconductor which seem to be uncovered by SEM. Such PPy films were estimated by photocurrent measurements to be thinner than 50 nm [30]. Z me is the impedance of thicker PPy deposits, in parallel with the (R ad , Z sc ) branch, and is defined by equation [2].

According to [14] the resistance R inf in parallel with Z sc and Z me in scheme (a) is assumed to account for a non-ideally blocking film/electrolyte interface with an eventual faradaic process.

Such a parallel resistance is not necessary in scheme (b).

The adjustable parameters contained in equations ( 1) to ( 7) are:

, R s , R e , R i , R p , C e , C i , (R p D e ), R inf (or R ad ), D i , R sc , C sc .
eters to 10.

The parameter D e cannot be obtained independently and only the product (R p D e ) is accessible. D i was fixed at values provided by different authors, and R s was known from preliminary experiments, limiting the number of adjustable param From equations ( 5) and ( 6), the charging capacitance C o of the hybrid structure can then be estimated by the limit of the imaginary part of the film impedance Z i +Z e in the lower limit of the frequency range:

Limit of             coth 4 i e p i e i e D D R R R Z Z when  →0 is   2 1 4  i e p i e D D R R R  
and the capacitance C o is given by equation ( 8):

e p i D R 4D   o C (8)
C 0 would correspond to the vertical branch of the Nyquist diagram. It may be experimentally not observable if the parallel resistance R inf is too small (< 10 k in our experimental conditions) and/or the polymeric film presents some discontinuities due to not totally uniform deposition.

Results and discussion

In order to highlight the modifications of the characteristics of the semiconductor induced by the PPy deposit, R sc and C sc values determined for the hybrid structure are compared to those obtained for the unmodified electrode in the same electrolyte.

PPy in SDBS

PPy layers obtained in SDBS under UV light after 40 cycles were characterized in the dark.

During the scan towards more positive potentials, an oxidation peak observed at about -0.2 V vs. SCE can be reasonably attributed to polymer oxidation (or doping). During the reverse scan a wide reduction peak with a maximum at -0. Table I shows that the double layer capacitances C i and C e progressively increase when the potential gets more cathodic, simultaneously with the space charge capacitance.

According to equation ( 6), the diffusion length d diff could be estimated from determination of the time constant taking D i = 1.6x10 -6 cm 2 s -1 which corresponds to the diffusion coefficient of Na + in PPy given in ref [14]. 2 and3. As previously the focus were put on the modification of R sc and C sc values in the presence of PPy and on the variation of the diffusion length as a function of applied potential. solution. According to [35], the linear part of the curve (between -0.45V and 0V) describes the band bending variation which is supported by the tube walls under polarization, whereas the quasi plateau observed in the more anodic range, corresponds to the domain of complete depletion of the tube walls. In the present case due to the geometric parameters of the tubes, and the 10 nm thickness of the tube walls, the maximum width of the space charge layer supported by the tube walls would be 5 nm. When PPy is deposited on the TiO 2 -NTA substrate, it has to be noted that the capacitance values are only slightly modified within the explored potential range. In Tables 2 and3, C sc values decrease from about 440 to 32 F for the hybrid sample obtained in the dark and only from 44 to 14 F for the sample obtained under UV light, when applied potential is varied from -0.5V to +0.5V vs SCE. Such behaviour can be attributed to the presence of surface states at the interface between the semiconductor and the polymer, which lead to Fermi level pinning. This is more obvious when the hybrid was previously synthesized under UV light and is in close agreement with the ohmic junction described in ref [30] for the PPy-TiO 2 hybrid structure.

It has to be noted from Tables 2 and3 that the values of R inf are low, mainly in the anodic range, indicating that the interface between the hybrid structure and the electrolyte presents some non-ideal blocking behaviour. This could result from heterogeneous distribution of PPy islands giving rise to leakage currents between the islands.

The diffusion length d diff could be estimated from the determination of the time constant taking D i = 4x10 -7 cm 2 s -1 which corresponds to the diffusion coefficient of ClO 4 -inside PPy given in [14]. Fig 7 shows that in LiClO 4 solution, d diff varies between 0.3 and 3 m, with the higher values for the hybrid sample obtained under UV light. Since the thicknes the polymeric layer was estimated to be lower than 2 m, we must admit that the value of 4. 10 s of -7 cm 2 s -1 could be slightly overestimated. The variation of d diff with the applied potential is also surprising and can be attributed to two-dimensional transport of the anions , normal on one hand and radial between the islands on the other hand, as a consequence of inhomogeneity of the deposit. When the polymer was deposited in the dark, the diffusion length reaches a maximum at 0 V, but at 0.4V vs SCE when the deposit was performed und UV light, in agreement with the anodic peaks observed in the voltammogram of It is noticeable that in the present case we do not observe the usual three features characterizing ECP/metal structures, i.e. a high frequency loop, a Warburg domain in the intermediate frequency range, and a capacitive straight line in the low frequency range [12].

Moreover the overall impedance diagrams show a very flat shape which usually corresponds to heterogeneous surfaces with distributed properties over the surface. We suggest that the high frequency response is here spread over a wide frequency range, hiding the Warburg domain in the intermediate frequency range. From a physical point of view, it seem that in the present work the PPy layers are not continuous and therefore the model used in [14] for uniform polymeric films on flat metal substrates is formally applied in this case. It has to be noted that the diffusion parameters can be extracted with a good confidence interval. Though many other, sometimes empirical, models can be found in the literature [18][START_REF] Garcia-Belmonte | Bisquert Electrochim[END_REF][20][21], the model suggested in Ref [14] for PPy, was also used in the present case, to interpret the experimental impedance diagrams obtained at different applied potentials. In Fig. 3D, the diagrams in the potential range between -0.1 V and + 0.8V vs SCE show the usual three features: a high frequency loop, a Warburg domain in the intermediate frequency range, and a capacitive straight line in the low frequency range. According to [12], the width of the Warburg domain depends on the ratio between the diffusion coefficients, D i and D e , the former being generally smaller than the latter one. When D e /D i increases, the vertical line is shifted towards lower frequencies and the Warburg region widens.

PEDOT in

The adjusted parameters are reported in Table 4 The substrate is characterized by a flat band potential close to -0.25V vs SCE, indicating a more positive value in comparison with the LiClO 4 containing aqueous medium (-0.45 V/ SCE in Fig 6). Accordingly, acetonitrile [36] has been shown to be strongly adsorbed on anatase, thus modifying the conduction band level of the titanium oxide film. A negative shift is observed in the presence of a PEDOT layer, reaching -0.4 V/ SCE in Fig 9 after extrapolation of the capacitance values measured in the [0.2 to 0.6 V vs SCE] potential range.

The overall shape of the Mott Schottky plot in the presence of PEDOT is very different from that of the reference sample, since a jump of 1/C 2 is observed between 0 and 0.2 V vs SCE).

This can be attributed to electron trapping in the surface states of the semiconductor when the potential exceeds 0 V. Since this potential range merges with the domain of PEDOT oxidation (doping), we suggest that the trapped electrons result from the oxidation of the polymer. On the contrary with what happens with PPy, the PEDOT coating allows the band bending inside the TiO 2 substrate to be changed with the applied potential.

The evolution of the ionic diffusion length d diff as a function of the applied potential was estimated in Fig 10 . As mentioned previously the diffusion length is limited by the thickness of the deposit and is related to the diffusion coefficient of ClO 4 -and to the diffusional time constant by relation (6). In the literature, the data provided for the diffusion coefficient of ClO 4 -in PEDOT varies by several orders of magnitude, from 10 -5 to 10 -9 cm 2 s -1 . The higher value which is similar to diffusion coefficients measured in aqueous solutions corresponds to highly wetted porous films [4], whereas the lower value would correspond to very compact films [18,37]. It has also been shown that D values increase with film thickness. For example, in Ref [18] the diffusion coefficient of Cl -in PEDOT has been reported to vary from 10 -8 to 10 -7 cm 2 s -1 within the thickness range of 0.1 to 1.5 m. Given the diffusional time constants between 0.2 and 0.6 s determined by the present model and given the thickness of the film (between 1 and 2 m), a diffusion coefficient of 10 -8 cm 2 s -1 seems a reasonable value in the present work. m between 0 to 0.8V. It has to be noted that the R inf values in Table 4 are a few orders of magnitude higher than in the case of PPy in the presence of LiClO 4 (Tables 2 and3), indicating a more compact layer in the former case without any leakage in the film. Another significant difference between the two layers is the value of the resistance of the polymeric film (negligible in the case of PPy versus a few ohms in the case of PEDOT), indicating a lower diffusion coefficient for the electrons inside the PEDOT layer in comparison with the PPy layer. This remark is in agreement with the difference in shape of the EIS diagrams of

Conclusion

The present work shows that the model suggested by Deslouis, Tribollet and co-workers in the case of a PPy deposit on flat metals were used and applied for conducting polymers deposited on nanostructured titanium oxide. The model was successfully extended to PEDOT layers in non-aqueous solvents, indicating that the PEDOT layer on TiO 2 -NTA behaves like a continuous layer. The model was less efficient in the case of PPy/TiO 2 -NTA hybrid structures, since the usual Warburg line could not be clearly observed in the impedance diagrams. This could be due to a heterogeneous PPy deposit which generates a high distribution of properties at the surface of the hybrid structure. Nevertheless the samples studied in this work were not optimized for reaching the highest yield of charge storage or the highest capacitance, but were selected in order to prove that differences in the polymerisation conditions such as the nature of the solvent, the deposition rate or the nature of the polymer, induce different behaviours in the semiconducting oxide which can be highlighted by EIS.

The model here used provides a valuable tool for characterizing the interaction between a ECP and a semiconducting substrate in order to further optimize the experimental parameters and reach the expected performances for such a hybrid structure. Polymer deposits were analysed after 40 cycles of potential scans. 1: Adjusted parameters at some potential values (taking Di(Na + ) = 1.5 10 -6 cm 2 s -1 according to reference [14]) for the hybrid structure PPy-TiO 2 obtained in SDBS under UV. Fitting procedure follows scheme (b) of Fig. Table 2: Adjusted parameters at some potential values (taking Di = 4 10 -7 cm 2 s -1 according to reference [14]) for the hybrid structure PPy-TiO 2 obtained in LiClO 4 in the dark . Fitting procedure follows scheme (a) of Fig. Table 3: Adjusted parameters at some potential values (taking Di = 4 10 -7 cm 2 s -1 according to reference [14]) for the hybrid structure PPy-TiO 2 obtained in LiClO 4 under UV light. Fitting procedure follows scheme (a) of Fig. Table 4: Adjusted parameters at some potential values (taking Di = 1 10 -8 cm 2 s -1 according to reference [38]) for the hybrid structure PEDOT-TiO 2 obtained in acetonitrile + LiClO 4 in the dark. Fitting procedure follows scheme (a) of Fig. 2

CAPTIONS

  Fig 4A shows an impedance diagram in the Nyquist representation at -0.1V and +0.2V for the substrate and the PPy/TiO 2 hybrid structure obtained under illumination. Since the surface was only partially covered, scheme (b) was used for the fitting procedure, leading to a good agreement with the experimental data.

  Fig 4B and C compare impedance diagrams in the Nyquist representation at -0.1 and 0.2 V vs SCE respectively for the PPy/TiO 2 hybrid structures obtained in the dark and under illumination. Preliminary simulations of these diagrams using the same model as previously provided the best fits when Z me and Z sc are in series, indicating that PPy is deposited over the whole surface of TiO 2 -NTAs. According to scheme (a) in Fig 2, adjusted parameters are given at some potential values in Tables2 and 3. As previously the focus were put on the

Fig 5

 5 Fig 5 compares the variation of R sc as a function of the potential in LiClO 4 solution: in the presence of PPy, it appears that the values are lowered by a few orders of magnitude in comparison with the substrate, in the potential range positive to -0.2V, i.e. in the potential range where doping occurs. The lowering is about 3 orders of magnitude when the polymer deposition was performed in the dark and up to 5 orders of magnitude when the deposition was performed under UV light, for the same number of cycles. In the potential range negative

  Fig 3 B an C, due to doping of the polymer by ClO er d -anions.

4

 4

LiClO 4 Characterization

 4 of a hybrid structure made of PEDOT and TiO 2 -NTAs was performed in acetonitrile with 0.1 M LiClO 4 as supporting electrolyte. The voltammogram of Fig 3D shows the typical shape that is also observed on platinum (not shown) after 40 cycles, in the same experimental conditions.

  . The evolution of the parameters related to the semiconductor (R sc and C sc ) is shown in Fig 8 and 9. Considering the evolution of R sc with potential, two domains are obvious: at E>0 V vs SCE, R sc keeps a roughly constant value close to 40  followed by an increase when the potential reaches lower values. The low R sc values are thus observed in the domain of PEDOT doping, very similar to what was observed for the PPy(ClO 4 ) deposits in Fig 5. The 1/(C sc ) 2 variations are reported in Fig 9 in a Mott Schottky representation for the uncovered TiO 2 -NTA substrate and the PEDOT covered substrate in acetonitrile solution containing 0.1M LiClO 4 .

  Fig 10 shows a sharp increase of d diff when the potential reaches 0 V vs SCE, followed by a slight decrease in the more positive potential range, ranging from 2.1 m to 1.2

Fig 4 :

 4 Fig 4: the presence of a vertical line in the low frequency range for PEDOT (Fig 4D) indicates a D e /D i ratio lower than for PPy (Fig 4 B and C), in which the vertical line is likely to be shifted towards lower frequencies. The calculation of C o from the adjusted parameters of Table4is reported in the last column,

Figure 1

 1 Figure 1 FEG-SEM images of a TiO 2 -polymer junction after 40 scans a) and b)TiO 2 nanotubes partially filled by polypyrrole in SDBS, -top view (a) and sideview (b). Inset of Fig a: FEG-SEM image of a pristine TiO 2 -NTA c) TiO 2 nanotubes partially filled by PEDOT in LiClO 4 and acetonitrile.

Figure 2

 2 Figure 2 Equivalent circuits used to characterize the electrochemical behaviour (a) for hybrid structures PPy-TiO 2 obtained in LiClO 4 aqueous solution and PEDOT-TiO 2 obtained in LiClO 4 acetonitrile solution. (b) for hybrid structures PPy-TiO 2 obtained in SDBS aqueous solution.

Figure 3

 3 Figure 3 Voltammograms for polymer/TiO 2 -NTA structures A): PPy deposited under UV in SDBS B) PPy deposited in the dark in LiClO 4 C) PPy deposited under UV in LiClO 4 D) PEDOT deposited in the dark in acetonitrile + LiClO 4 . v = 10 mV/s Polymer deposits were analysed after 40 cycles of potential scans.

Figure 4

 4 Figure 4 Impedance diagrams and corresponding fitted curves in the oxidation potential range for polymer/TiO 2 -NTA structures A): PPy deposited under UV in SDBS B) PPy deposited in the dark in LiClO 4 C) PPy deposited under UV in LiClO 4 D) PEDOT deposited in the dark in acetonitrile + LiClO 4 .

Figure 5

 5 Figure 5 Variations of R sc with applied potential for TiO 2 NTA (substrate) and for the PPy-TiO 2 -NTA hybrid structures obtained in LiClO 4 and SDBS solutions.

Figure 6

 6 Figure 6 Variations of (1/C sc ) 2 with applied potential for TiO 2 NTA (substrate) and for the PPy-TiO 2 -NTA hybrid structures obtained in LiClO 4 and SDBS solutions.

Figure 7

 7 Figure 7 Comparison between diffusion lengths with applied potential for PPy-TiO 2 NTA hybrid structures obtained in SDBS and LiClO 4 solutions.

Figure 8 4 Figure 9 4 Figure 10 Figure 1 Figure 2

 84941012 Figure 8 Evolution of Rsc as a function of applied potential for a TiO 2 -NTA substrate and the hybrid structure with PEDOT in LiClO 4

Figure

  Figure 10

  Table 4 is reported in the last column, at different potentials, leading to a mean value of 1.9 mF, which is close to the capacitance value which can be estimated from the voltammogram in Fig 3D(about 3mF). This agreement validates the use of the model for describing the behaviour of the PEDOT-TiO 2 NTA hybrid structure.

Table

	Pot V/SCE	R s 	10 5  s	R i 	R e k	C i µF	C e µF	R p 	R sc k	C sc µF	R ad k	cm 2 /s 10 5 R p d	S.D.
	0.5	1162	1.00.1	820250 7020	150.8	8.30.5 (10 -10)	37.42.3 3.00.8 22.53.1 2.00.1	0.80
	0.3	1162	2.00.2	500150 5918	191.0	12.50.7 (10 -10 )	29.61.9 5.31.4 13.81.9 2.00.1	0.81
	0.1	1162	3.00.3	650200 7221	361.9	191.1	(10 -10 )	22.41.3 133.4	15.82.2 2.00.1	0.81
	-0.1	1162	7.00.3	37110 459	661.3	272.4	(10 -10 )	4.30.5 354.4	7.40.5	2.00.1	0.59
	-0.3	1162	40020	210070 11422 1032	24622 (10 -10 )	4.30.5 21226 1.60.1	7.00.3	0.48
	-0.5	1162	28015	116040 23540 1864	20718 (10 -10 )	4.20.5 22828 0.350.03 7.00.3	0.36
					10

  2

	Pot V/SCE	R s 	10 4  s	R i k	R e 	C i µF	C e µF	R p 	R sc k	C sc µF	R inf k	cm 2 /s 10 6 R p d	S.D.
	0.5	1504 92	1.200.20	8050	244	6120	4.42	1.630.12 322	2.140.3 133	0.74
	0.3	1512 324.	2.310.20	17040 271	5010	32	1.700.10 695	3.800.25 335	0.65
	0.1	1504 253.	0.950.14	8830	504	6520	4.2.5	2.940.14 432	3.160.50 223.	0.72
	-0.1	1513 7020	11.86.0	31070 16013 9313	1.24	2.580.15 542.3	7.071.00 5311	0.81
	-0.3	1512 1.51	0.540.12	7120	12810 9212	34	1.830.17 1528	12.01.4 3.10.2 0.69
	-0.5	1512 1.00.1	0.740.35	6130	48040 29430 0.51	7.233.2 44323 39.020	1.20.1 0.68

  2

	Pot V/SCE	R s 	10 4  s	R i k	R e 	C i µF	C e µF	R p 	R sc 	C sc µF	R inf 	cm 2 /s 10 6 R p d	S.D.
	0.5	1502	33265	(0.13)	720230 (2500)	20030 0.63	355	14.45	31520	23030	0.76
	0.3	1502	42060	(0.95)	945200 1830 1000	17018 (0)	285	238	52025	30025	0.72
	0.1	1502	15430	0.980.22 28560 15915 13620 1.13	355	196	74040	9310	0.71
	-0.1	1502	13020	1.260.20 32045 17120 12912 (0)	335	256	114050 7010.	0.64
	-0.3	1502	14010	1.210.10 31530 1668	1268	(0)	554	324	165060 756	0.46
	-0.5	1502	192	2.820.37 12622 674	396	(0)	47035 443	4530300 374	0.73

  2

	Pot V/SCE	R s 	 s	R i 	R e 	C i µF	C e µF	R p 	R sc 	C sc µF	R inf k	10 6 R p d cm 2 /s	S.D.	C 0 mF
	0.8	3604	0.200.02 2829 857	3.50.3 4.30.8 2.83	445	1.60.5 7.52	5.20.2	0.38	1.7
	0.6	3604	0.240.02 2819 857	3.50.3 3.80.6 3.03	365	1.60.5 8.12.1 5.70.2	0.38	1.7
	0.4	3604	0.290.01 2718 997	4.30.4 3.90.6 3.43	365	1.80.6 14.45	6.20.2	0.40	1.9
	0.2	3604	0.340.02 27110 1519	7.10.7 4.50.6 4.63.5	396	2.00.7 14.55	7.60.3	0.44	1.7
	0	3605	0.500.06 39125 50234 8.70.8 304	6.35	4210 4.82.8 15.5	171	0.68	2.2

Acknowledgements:

Mrs F. Pillier is warmly acknowledged for her expertise in FEG-SEM experiments.

Appendix

Calculation of the impedance parameters by the regression procedure used by the SIMAD software and estimation of the confidence intervals.

Regression

Experimental spectra were fitted using a simplex procedure by means of an in-house software.

The program minimized the 2

Where n f is the number of frequencies, the standard deviation for the measurement was assumed to be = 0.01Z and the carat refers to the model value. The expression used for  corresponds to an assumption that the standard deviation for the impedance measurement was equal to one percent of the modulus.

For a complex regression, the fitting quality was determined by the standard deviation q 2 q   

Where  is the degree of freedom for the regression, i.e., the number of observations 2n f minus the number of adjustable parameters. A good fit should correspond to a value q =1.

A smaller value of q means that a priori error was overestimated.

Confidence intervals

Confidence intervals for the fitted parameters were estimated empirically from the change in a single parameter value yielding an increase by a factor 1.5 of the standard deviation q characterizing the fit quality, the other parameters staying fixed to their optimal value.