Stefano Galatolo

Mathieu Hoyrup

Cristóbal Rojas

Statistical properties of dynamical systemssimulation and abstract computation

We survey an area of recent development, relating dynamics to theoretical computer science. We discuss some aspects of the theoretical simulation and computation of the long term behavior of dynamical systems. We will focus on the statistical limiting behavior and invariant measures. We present a general method allowing the algorithmic approximation at any given accuracy of invariant measures. The method can be applied in many interesting cases, as we shall explain. On the other hand, we exhibit some examples where the algorithmic approximation of invariant measures is not possible. We also explain how it is possible to compute the speed of convergence of ergodic averages (when the system is known exactly) and how this entails the computation of arbitrarily good approximations of points of the space having typical statistical behaviour (a sort of constructive version of the pointwise ergodic theorem).

Introduction

The advent of automated computation led to a series of great successes and achievements in the study of many natural and social phenomena which are modeled by dynamical systems. The use of computers and simulations allowed to predict the behavior of many important models and, on the other hand, led to the discovery of important general aspects of dynamics. This motivated the huge amount of work that was made by hundreds of scientists to improve practical simulation and computation techniques. It also motivated the study of the theoretical limits of simulation and computation techniques, and the theoretical understanding of related problems.

In this paper we shall focus on some of these theoretical aspects related to rigorous computation and simulation of (discrete time) dynamical systems.

The simulation and investigation of dynamical systems started with what we call the naive approach, in which the user just implements the dynamics without taking rigorous account of numerical errors and rounding. Then the user simply sees what happens on the screen.

Evidently, the sensitivity to initial conditions and the typical instability of many interesting systems (to perturbations on initial conditions but also on the map generating the dynamics) implies that what is beeing observed on the computer screen could be completely unrelated to what was meant to be simulated. In spite of this, the naive approach turns out to work almost unreasonably well in many situations and it is even today the most commonly used approach in simulations. The theoretical reasons of why this method works and what are its limits, are in our opinion yet to be understood (some aspects have been investigated in [39], [START_REF]Miernowski Discrétisations des homéomorphismes du cercle[END_REF], [START_REF] Grüne | Asymptotic behavior of dynamical and control systems under perturbation and discretization Lect[END_REF] [START_REF] Blank | Pathologies generated by round-off in dynamical systems[END_REF]8], [START_REF]Lanford III Informal Remarks on the Orbit Structure of Discrete Approximations to Chaotic Maps Exp[END_REF] e.g.).

Opposite to the naive approach, there is the "absolutely rigorous" approach, which will be the main theme of this paper. Here the user seeks for an algorithm able to produce a description up to any desired precision of the object x which is meant to be computed. In case such an algorithm exits, we say that the object x is computable (suitable precise definitions will be given below).

For example, in this approach the constant e is a computable number because there is an algorithm that is able to produce a rational approximation of e at any given accuracy (for instance by finding the right m and calculating

m 1 1 n!
such that the error is smaller than requested).

In an "absolutely rigorous" simulation (computation), both the initial point (or initial distribution) and the transition map are supposed to be computable, and the question arises if interesting objects related to the dynamics (e.g. invariant sets or invariant measures) can be computed from the description of the system (or perhaps by using some additional information).

In this paper we shall survey a number of results related to these computational aspects, some of which are updated with new information. We will see that in many cases the objects of interest can indeed be computed, but there are some subtleties, and cases where the interesting objects cannot be computed from the description of the system, or cannot be computed at all. In other words, these results provide theoretical limits to such computations. In particular, we shall recall some examples where this non-computability phenomenon appears, in the case of invariant measures and Julia sets.

Computing invariant measures. An important fact motivating the study of the statistical properties of dynamical systems is that the pointwise long term prediction of a chaotic system is not possible, whereas, in many cases, the estimation or forecasting of averages and other long term statistical properties is. This forecasting procedure, often corresponds in mathematical terms to the computation of invariant measures or to the estimation of some of their properties -measures contain information on the statistical behavior of the system (X, T ) and on the potential behavior of averages of observables along typical trajectories of the system (see Section 3).

An invariant measure is a Borel probability measure µ on X such that for each measurable set A it holds that µ(A) = µ(T -1 (A)). They represent equilibrium states, in the sense that probabilities of events do not change in time.

To rigorously compute an invariant measure means to find an algorithm which is able to output a description of the measure (for example an approximation of the measure made by a combination of delta measures placed on "rational" points) up to any prescribed precision.

We remark that once an interesting invariant measure is computed, this information is useful for the computation of other dynamical properties: Lyapunov exponents, entropy, escape rates, etc... For example, in dimension one, once an ergodic invariant measure µ has been approximated, the Lyapunov exponent λ µ can be estimated using the formula λ µ = 1 0 log 2 T dµ, where T denotes the derivative of the map generating the dynamics. In higher dimensions, similar techniques can be applied (see e.g. [START_REF] Froyland | Extracting dynamical behaviour via Markov models n[END_REF] for more examples of derivation of dynamical quantities from the computation of the invariant measure and similar objects).

Before giving more details about the computation of invariant measures, we remark that, since there are only countably many "algorithms" (computer programs), whatever we mean by "approximating a measure by an algorithm"would imply that only countable many measures can be computed. In general, however, a dynamical system may have uncountably many invariant measures (usually an infinite dimensional set). So, a priori most of them will not be algorithmically describable. This is not a serious problem because we should put our attention on the most meaningful ones. An important part of the theory of dynamical systems is indeed devoted to the understanding of physically relevant invariant measures. Informally speaking, these are measures which represent the asymptotic statistical behavior of many (positive Lebesgue measure) initial conditions (see Section 3 for more details).

The existence and uniqueness of physical measures is a widely studied problem (see [START_REF] Young | What are SRB measures, and which dynamical systems have them?[END_REF]), which has been solved for some important classes of dynamical systems. These measures are some of the good candidates to be computed. Other measures of particular interest in certain cases, as we shall see below, are the maximal entropy ones.

The computation of interesting invariant measures (in more or less rigorous ways) is the main goal of a significant part of the literature related to computation in dynamics. An important role here is played by the transfer operator induced by the dynamics. Indeed, the map T defining the dynamics, induces a transition map L T on the space of probability measures over X, L T : P M (X) → P M (X). L T is called the transfer operator associated to T (definition and basic results about this are recalled in Section 3). Invariant measures are fixed points of this operator. The main part of the methods which are used to compute invariant measures deals with suitable finite dimensional approximations of this operator. In Section 3 we will review briefly some of these methods, and give some references. We then consider the problem from the abstract point of view mentioned above, and give some general results on rigorous computability of the physical invariant measure. In particular we will see that the transfer operator is computable up to any approximation in a general context (see Thm 16). The corresponding invariant measure is computable, provided we are able to give a description of a space of "regular" measures where the physical invariant measure is the only invariant one (see Thm 17 and following corollaries).

We will also show how the measure can be obtained from a description of the system in a class of examples (piecewise expanding maps) by using the Lasota-Yorke inequality.

Rational transformations of the Riemann Sphere are another interesting class where our methods can be applied. These complex dynamics are very well studied in the literature, and enormous attention has been addressed to the Julia sets associated to them, which have emerged as the most studied examples of fractal sets generated by a dynamical system. One of the reasons for their popularity is the beauty of the computer-generated images of such sets. The algorithms used to draw these pictures vary; the naïve approach in this case works by iterating the center of a pixel to determine if it lies in the Julia set. There exists also more sophisticated algorithms (using classical complex analysis, see [START_REF] Milnor | Dynamics in one complex variable[END_REF]) which work quite well for many examples, but it is well known that in some particular cases computation time will grow very rapidly with increase of the resolution. Moreover, there are examples, even in the family of quadratic polynomials, where no satisfactory pictures of the Julia set exist.

In the rigorous approach, a set is computable if, roughly speaking, its image can be generated by a computer with an arbitrary precision. Under this notion of computability, the question arise if Julia sets are always computable. In a series of papers ( [START_REF] Binder | On computational complexity of Siegel Julia sets[END_REF]4,[START_REF] Braverman | Non-computable Julia sets[END_REF][START_REF] Braverman | Computability of Julia sets[END_REF]) it was shown that even though in many cases (hyperbolic, parabolic) the Julia set is indeed computable, there exists quadratic polynomials which are computable (again, in the sense that all the trajectories can be approximated by an algorithm at any desired accuracy), and yet the Julia set is not.

So we can not simulate the set of limits points on which the chaotic dynamics takes place, but, what about the statistical distribution? In fact, it was shown by Brolin and Luybich that there exists a unique invariant measure which maximizes entropy, and that this measure is supported on the Julia set. The question of whether this measure can be computed has been recently solved in [START_REF] Binder | Computability of Brolin-Lyubich measure[END_REF], where it is proved that the Brolin-Lyubich measure is always computable. So that even if we can not visualize the Julia set as a spatial object, we can approximate its distribution at any finite precision. In Section 3.3 we shall briefly review the mentioned results on uncomputability of Julia sets, and explain how our method can be applied to show computability of the Brolin-Lyubich measure.

After such general statements one could conjecture that all computable dynamical systems should always have a computable invariant measure. We will see that, perhaps surprisingly, this is not true. Not all computable systems (the dynamics can be computed up to any prescribed approximation) have computable invariant measures (see Section 3.4). The existence of such examples reveals some subtleties in the computation of invariant measures.

Finally, to further motivate these results, we remark that from a technical point of view, computability of the considered invariant measure is a requirement in several results establishing connections between computation, probability, randomness and pseudo-randomness (see Section 5 and e.g. [START_REF] Bienvenu | Effective randomness for computable probability measures[END_REF]24,25,[START_REF] Galatolo | Effective symbolic dynamics, random points, statistical behavior, complexity and entropy[END_REF])

Computing the speed of convergence and pseudorandom points.

For several questions in ergodic theory the knowledge of the speed of convergence to ergodic behavior is important to deduce other practical consequences. In the computational framework, the question turns out to be the effective estimation of the speed of convergence in the ergodic theorems1 . From the numerical-practical point of view this has been done in some classes of systems, having a spectral gap for example. In this case a suitable approximation of the transfer operator allows to compute the rate of decay of correlations [23][40] and from this, other rates of convergence can be easily deduced.

Other classes of systems could be treated joining the above spectral approach, with combinatorial constructions (towers, see [START_REF] Luzzatto | Stochastic-like behaviour in non-uniformly expanding maps Handbook of Dynamical Systems[END_REF] e.g.), but the general case need a different approach.

In [START_REF] Avigad | Local stability of ergodic averages[END_REF] it was shown that much more in general, if the system can be described effectively, then the rate of convergence in the pointwise ergodic theorem can be effectively estimated (not only the asymptotical speed, but explicit estimates on the error).

We give in section 4 a very short proof of a statement of this kind (see Theorem 39 ) for ergodic systems, and show some consequences. Among these, a constructive version of pointwise ergodic theorem. If the system is computable (in some wide sense that will be described), then it is possible to compute points having typical statistical behavior. Such points could hence be called pseudorandom points of the system (see Section 5).

Since the computer can only handle computable initial conditions, any simulation can start only from these points. Pseudorandom initial conditions are hence in principle the good points where to start a simulation.

We remark that it is widely believed that naive computer simulations very often produce correct statistical behavior. The evidence is mostly heuristic. Most arguments are based on the various "shadowing" results (see e.g. [START_REF] Hasselblatt | Introduction to the Modern Theory of Dynamical Systems[END_REF] chapter 18). In this kind of approach (different from ours), it is possible to prove that in a suitable system every pseudo-trajectory (as the ones which are obtained in simulations with some computation error) is close to a real trajectory of the system. However, even if we know that what we see in a simulation is near to some real trajectory, we do not know if this real trajectory is typical in some sense. Another limitation of this approach is that shadowing results hold only in systems having some strong hyperbolicity, while many physically interesting systems are not like this. In our approach we consider real trajectories instead of "pseudo" ones and we ask if there exists computable points which behaves as a typical point of the dynamics.

Acknowledgement 1

We would like to thank The Abdus Salam International Centre for Theoretical Physics (Trieste, IT) for support and hospitality during this research.

Computability on metric spaces

To have formal results and precise assumptions on the computability (up to any given error) of continuous objects, we first need to introduce some concepts. In particular, we shall introduce recursive versions of open and compact sets, and characterize the functions which are well suited to operate with those sets (computable functions). In this section, we try to explain this theory as simple and self contained as possible. Other details and different approaches to the subject can be found in the introductory texts [9] and [START_REF] Weihrauch | Computable Analysis. An Introduction[END_REF].

Computability

The starting point of recursion theory was the introduction of a mathematical definition making precise the intuitive notions of algorithmic or effective procedure on symbolic objects. Several different formalizations have been independently proposed (by Church, Kleene, Turing, Post, Markov...) in the 30's. They all turned out to be be equivalent: they compute the same functions from N to N. The class of functions thus defined is now called the class of recursive functions. As an algorithm is allowed to run forever on an input, these functions may be partial, i.e. not defined everywhere. The domain of a recursive function is the set of inputs on which the algorithm eventually halts. A recursive function whose domain is N is said to be total.

We now recall an important concept from recursion theory. A set E ⊆ N is said to be recursively enumerable (r.e.) if there is a (partial or total) recursive function ϕ :

N → N enumerating E, that is E = {ϕ(n) : n ∈ N}. If E = ∅,
ϕ can be effectively converted into a total recursive function ψ which enumerates the same set E.

Algorithms and uniform algorithms

Strictly speaking, recursive functions only work on natural numbers. However, this can be extended to the objects (thought as "finite" objects) of any countable collection, once a numbering of its elements has been chosen. We will use the word algorithm instead of recursive function when the inputs or outputs are interpreted as finite objects. The operative power of algorithms on the objects of such a numbered set obviously depends on what can be effectively recovered from their numbers.

More precisely, let X and Y be numbered sets such that the numbering of X is injective (it is then a bijection between N and X). Then any recursive function ϕ : N → N induces an algorithm A : X → Y . The particular case X = N will be much used.

For instance, the set Q of rational numbers can be injectively numbered Q = {q 0 , q 1 , . . .} in an effective way: the number i of a rational a/b can be computed from a and b, and vice versa. We fix such a numbering: from now on the rational number with number i will be denoted by q i . Now, let us consider computability notions on the set R of real numbers.

Definition 2 Let x be a real number. We say that:

• x is lower semi-computable if the set {i ∈ N : q i < x} is r.e. • x is upper semi-computable if the set {i ∈ N : q i > x} is r.e.
• x is computable if it is lower and upper semi-computable.

It is worth noticing that a real number is computable if and only if there exists an algorithmic enumeration of a sequence of rational numbers converging exponentially fast to x. That is:

Proposition 3 A real number is computable if there is an algorithm A : N → Q such that |A(n) -x| ≤ 2 -n for all n.
We remark that the notion of computable real number was already introduced (in a different but equivalent way) by Turing in [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF].

Uniformity. Algorithms can be used to define computability notions on many classes of mathematical objects. The precise definitions will be particular to each class of objects, but they will always follow the following scheme:

An object O is computable if there is an algorithm A : X → Y which computes O in some way.
Each computability notion comes with a uniform version. Let (O i ) i∈N be a sequence of computable objects:

O i is computable uniformly in i if there is an algorithm A : N × X → Y such that for all i, A i := A(i, •) : X → Y computes O i .
For instance, the elements of a sequence of real numbers (x i ) i∈N are uniformly computable if there is a algorithm

A : N × N → Q such that |A(i, n) -x i | ≤ 2 -n for all i, n.
In other words a set of objects is computable uniformly with respect to some index if they can be computed with a "single" algorithm starting from the value of the index.

In each particular case, the computability notion may take a particular name: computable, recursive, effective, r.e., etc. so the term "computable" used above shall be replaced.

Computable metric spaces

A computable metric space is a metric space with an additional structure allowing to interpret input and output of algorithms as points of the metric space. This is done in the following way: there is a dense subset (called ideal points) such that each point of the set is identified with a natural number. The choice of this set is compatible with the metric, in the sense that the distance between two such points is computable up to any precision by an algorithm getting the names of the points as input. Using these simple assumptions many constructions on metric spaces can be implemented by algorithms.

Definition 4 A computable metric space (CMS) is a triple X = (X, d, S), where (i) (X, d) is a separable metric space.

(ii) S = {s i } i∈N is a dense, numbered, subset of X called the set of ideal points.

(iii) The distances between ideal points d(s i , s j ) are all computable, uniformly in i, j (there is an algorithm A :

N 3 → Q such that |A(i, j, n) -d(s i , s j )| < 2 -n ).
Point (iii) says that the information that can be recovered from the numbers of the numbered set S is their mutual distances.

The algorithms involved in the following definitions (up to Definition 9) are assumed to be total.

Definition 5

We say that in a metric space (X, d), a sequence of points (x n ) n∈N converges recursively to a point x if there is an algorithm

D : Q → N such that d(x n , x) ≤ for all n ≥ D( ). Definition 6 A point x ∈ X is said to be computable if there is an algorithm A : N → S such that (A(n)) n∈N converges recursively to x.
We define the set of ideal balls to be B := {B(s i , q j ) : s i ∈ S, 0 < q j ∈ Q} where B(x, r) = {y ∈ X : d(x, y) < r} is an open ball. We fix a numbering B = {B 0 , B 1 , . . .} which makes the number of a ball effectively computable from its center and radius and vice versa. B is a countable basis of the topology. Obviously, an uniform intersection of effective G δ -sets is also an effective

G δ -set. Let (X, S X = {s X 1 , s X 2 , ...}, d X ) and (Y, S Y = {s Y 1 , s Y 2 , ...}, d Y ) be com- putable metric spaces. Let also B X
i and B Y i be enumerations of the ideal balls in X and Y . A computable function X → Y is a function whose behavior can be computed by an algorithm up to any precision. For this it is sufficient that the pre-image of each ideal ball can be effectively enumerated by an algorithm.

Definition 9 (Computable Functions

) A function T : X → Y is com- putable if T -1 (B Y i ) is an effective open set, uniformly in i. That is, there is an algorithm A : N × N → B X such that T -1 (B Y i ) = n A(i, n) for all i. A function T : X → Y is computable on D ⊆ X if there are uniformly effective open sets U i such that T -1 (B Y i ) ∩ D = U i ∩ D.
Remark 10 Intuitively, a function T is computable (on some domain D) if there is a computer program which computes T (x) (for x ∈ D) in the following sense: on input > 0, the program, along its run, asks the user for approximations of x, and eventually halts and outputs an ideal point s ∈ Y satisfying d(T (x), s) < . This idea can be formalized, using for example the notion of oracle computation. The resulting notion coincides with the one given in the previous definitions.

Recursive compactness is an assumption which will be needed in the following. Roughly, a compact set is recursively compact if the fact that it is covered by a finite collection of ideal balls can be tested algorithmically (for equivalence with the -net approach and other properties of recursively compact set see [27]).

Definition 11 A set K ⊆ X is recursively compact if it is compact and there is a recursive function ϕ : N * → N such that ϕ(i 1 , . . . , i p ) halts if and only if (B i1 , . . . , B ip ) is a covering of K.
3 Computability of invariant measures

Invariant measures and statistical properties

Let X be a metric space, T : X → X a Borel measurable map and

µ a T - invariant Borel probability measure. A set A is called T -invariant if T -1 (A) =
A (mod 0). The system (X, T, µ) is said to be ergodic if each T -invariant set has total or null measure. In such systems the famous Birkhoff ergodic theorem says that time averages computed along µ-typical orbits coincides with space average with respect to µ. More precisely, for any f ∈ L 1 (X, µ) it holds

lim n→∞ S f n (x) n = f dµ, (1)
for µ almost each x, where

S f n = f + f • T + . . . + f • T n-1
. This shows that in an ergodic system, the statistical behavior of observables, under typical realizations of the system is given by the average of the observable made with the invariant measure.

We say that a point x belongs to the basin of attraction of an invariant measure µ if (1) holds at x for each bounded continuous f . In case X is a manifold (possibly with boundary), a physical measure is an invariant measure whose basin of attraction has positive Lebesgue measure (for more details and a general survey see [START_REF] Young | What are SRB measures, and which dynamical systems have them?[END_REF]). Computation of such measures will be the main subject of the first part of this section.

The transfer operator

A function T between metric spaces naturally induces a function L T between probability measure spaces. This function L T is linear and is called transfer operator (associated to T ). Measures which are invariant for T are fixed points of L T .

Let us consider a computable metric space X and a measurable function T : X → X. Let us also consider the space P M (X) of Borel probability measures on X.

Let us define the linear function L T : P M (X) → P M (X) by duality in the following way: if µ ∈ P M (X) then L T (µ) is such that

f dL T (µ) = f • T dµ for each bounded continuous f .
The computation of invariant measures (and many other dynamical quantities) very often is done by computing the fixed points (and some other spectral information) of this operator in a suitable function space. The most applied and studied strategy is to find a suitable finite dimensional approximation of L T (restricted to a suitable function space) so reducing the problem to the computation of the corresponding relevant eigenvectors of a finite matrix.

An example of this is done by discretizing the space X by a partition A i and replacing the system by a (finite state) Markov Chain with transition probabilities

P ij = m(A i ∩ A j ) m(A i )
where m is the Lebesgue measure on X (see e.g. [START_REF] Froyland | On Ulam approximation of the isolated spectrum and eigenfunctions of hyperbolic maps[END_REF][22] [START_REF] Liverani | Rigorous numerical investigations of the statistical properties of piecewise expanding maps-A feasibility study[END_REF]). Then, taking finer and finer partitions it is possible to obtain in some cases that the finite dimensional model will converge to the real one (and its natural invariant measure to the physical measure of the original system). In some cases there is an estimation for this speed of convergence (see eg. [START_REF] Froyland | Extracting dynamical behaviour via Markov models n[END_REF] for a discussion), but a rigorous bound on the error (and then a real rigorous computation) is known only in a few cases (piecewise expanding or expanding maps, see [START_REF] Liverani | Rigorous numerical investigations of the statistical properties of piecewise expanding maps-A feasibility study[END_REF], [29]). Similar approaches consists of applying a kind of Faedo-Galerkin approximation to the transfer operator by considering a complete Hilbert base of the function space and truncating the operator to the action on the first elements (see [START_REF] Weber | P Seba Resonances of the Frobenius-Perron operator for a Hamiltonian map with a mixed phase space[END_REF] ).

Another approach is to consider a perturbation of the system by a small noise. The resulting transfer operator has a kernel. This operator can then be approximated by a finite dimensional one (again by the Faedo-Galerkin method for instance) and the relevant eigenvectors can be thus calculated (see e.g. [18][17]). This method is useful in cases where it is possible to prove that the physical measure of the original system can be obtained as the limit when the size of the noise tends to zero (this happens, for example, for uniformly hyperbolic systems).

Variations on the method of partitions are given in [START_REF] Ding | High order approximation of the Frobenius-Perron operator[END_REF][START_REF] Ding | The projection method for computing multidimensional absolutely continuous invariant measures[END_REF], while in [START_REF] Pollicott | Computing invariant densities and metric entropy[END_REF] a different method, fastly converging, based on periodic points is exploited for piecewise analytic Markov maps. Another strategy to face the problem of computation of invariant measures consist in following the way the measure µ can be constructed and check that each step can be realized in an effective way. In some interesting examples we can obtain the physical measure as limit of iterates of the Lebesgue measure µ = lim n→∞ L n T (m) (recall that m is the Lebesgue measure). To prove computability of µ the main point is to explicitly estimate the speed of convergence to the limit. This sometimes can be done using techniques related to decay of correlations ([25]).

Concluding, if the goal is to rigorously compute an invariant measure, most of the results in modern literature are partial. Indeed, besides of being applied to restricted classes of systems, they usually need additional information in order to compute the measure. For example, the calculation of the finite dimensional approximations is often not done Turing-rigorously, or the rate of convergence of the approximations is computed up to some constants (depending on the system) which are not estimated.

In the remaining part of this section we present some general results, mainly from [27] and [START_REF] Binder | Computability of Brolin-Lyubich measure[END_REF], and explain how they can be applied to rigorously compute invariant measures. These results have the advantage of being simple and quite general with all the needed assumptions made explicit. On the other hand, they are not well suited for a complexity (in time or space) analysis, so it is not clear if they can be implemented and used in practice.

The rigorous framework in which they are proved, however, allows to see them as a study about the theoretical limits of (Turing-)rigorous computation of invariant measures and, in fact, also negative results can be obtained. In particular, we present examples of computable systems having no computable invariant measures.

Computability of measures

In this section we explain precisely what we mean by computing a measure, namely to have an algorithm able to approximate the measure by "simple measures" up to any desired accuracy.

Let us consider the space P M (X) of Borel probability measures over X. Let C 0 (X) be the set of real-valued bounded continuous functions on X. We recall the notion of weak convergence of measures:

Definition 12 µ n is said to be weakly convergent to µ if f dµ n → f dµ for each f ∈ C 0 (X).
Let us introduce the Wasserstein-Kantorovich distance between measures. Let µ 1 and µ 2 be two probability measures on X and consider:

W 1 (µ 1 , µ 2 ) = sup f ∈1-Lip(X) f dµ 1 -f dµ 2
where 1-Lip(X) is the space of functions on X having Lipschitz constant less than one. The distance W 1 has the following useful properties Proposition 13 (see [START_REF] Ambrosio | Gradient flows: In metric spaces and in the space of probability measures[END_REF] Prop 7.1.5) 1. W 1 is a distance and if X is bounded, separable and complete, then P M (X) with this distance is a separable and complete metric space.

2. If X is bounded, a sequence is convergent in the W 1 metric if and only if it is convergent for the weak topology.

3. If X is compact then P M (X) is compact with this metric.

Item (1) has an effective version: P M (X) inherits the computable metric structure of X. Indeed, given the set S X of ideal points of X we can naturally define a set of ideal points S P M (X) in P M (X) by considering finite rational convex combinations of the Dirac measures δ s supported on ideal points s ∈ S X . This is a dense subset of P M (X). The proof of the following proposition can be found in ( [START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF]).

Proposition 14 If X is bounded, then (P M (X), W 1 , S P M (X) ) is a computable metric space.

A measure µ is then computable if there is a sequence µ n ∈ S P M (X) converging recursively fast to µ in the W 1 metric (and hence in the weak topology).

Computable invariant "regular" measures

Here we describe a general method to compute invariant measures, that can be applied in several situations. We start by illustrating the method in its simplest form, namely to show that Proposition 15 If a computable system T : X → X is uniquely ergodic, then its invariant measure is computable.

Proof. The method is based on the following very simple and well-known fact: the singleton set {x 0 } is recursively compact if and only if its unique element x 0 is a computable point. The idea is then to show that the set {µ} ⊂ P M (X), where µ is the unique invariant measure, is recursively compact. This is done in the following way: first we observe that the set of probability measures P M (X) is recursively compact (since X is). Second we observe that the set P M T (X) c of probability measures which are NOT invariant under T is recursively open (here it is essential that T is an everywhere computable map). Finally we use the general fact that a recursively compact set minus a recursively open set is always recursively compact. In our case: P M (X) -P M T (X) c = {µ} is recursively compact, as was to be shown.

The obstructions to extend this idea to more general situations come from two main facts: (i) when the map T is not everywhere computable and then the set P M T (X) of invariant measures is not (recursively) compact anymore and (ii) when the map T is not uniquely ergodic, the set P M T (X) is not a singleton, and it therefore does not need to contain computable points (even if recursively compact).

To overcome these difficulties, we essentially need to find a different recursively compact condition which would allow us to separate a distinguished invariant measure from the rest, while making use of T only on its domain of computability.

In the following, we present a general result which sets the requirements in order to accomplish this task. It will be convenient to spell the principle in a more equation solving way, namely as an abstract theorem allowing the computation of isolated fixed points (see [27] Corollary 2.4.3) of maps computable on a suitable subset. This result will be then applied to the transfer operator, and invariant measures will be found as fixed points that can be somehow distinguished by means of analytic or dynamical properties (as being physical or absolutely continuous, for example).

It will be therefore necessary to consider a space where the transfer operator is computable (this space hopefully will contain the distinguished invariant measure).

We remark that if T is not continuous then L T is not necessarily continuous (this can be realized by applying L T to some delta measure placed near a discontinuity point) and hence not computable. Still, we have that L T is continuous (and its modulus of continuity is computable) at all measures µ which are "far enough" from the discontinuity set D. This is technically expressed by the condition µ(D) = 0.

Proposition 16 Let X be a computable metric space and T : X → X be a function which is computable on X \ D. Then L T is computable on the set of measures P M D (X) := {µ ∈ P M (X) :

µ(D) = 0}. ( 2
)
From a practical point of view, this proposition provides sufficient conditions to rigorously approximate the transfer operator by an algorithm.

The above tools allow us to ensure the computability of L T on a large class of measures and obtain in a way similar to Proposition 15: Theorem 17 ([27], Theorem 3.2) Let X be a computable metric space and T a function which is computable on X \ D. Suppose there is a recursively compact set of probability measures V ⊂ P M (X) such that for every µ ∈ V , µ(D) = 0 holds. Then every invariant measure isolated in V is computable. Moreover the theorem is uniform: there is an algorithm which takes as inputs finite descriptions of T, V and an ideal ball in M (X) which isolates2 an invariant measure µ, and outputs a finite description of µ.

Remark 18 Notice that there is no computability condition on the set D. We also remark that unless T is uniquely ergodic, invariant measures are never isolated in P M (X), so the task is to find a (recursively compact) condition that only a single invariant measure would satisfy.

Clearly, Proposition 15 is now a trivial corollary of Theorem 17. As already said, the main difficulty in the application of Theorem 17 is the requirement that the invariant measure we are trying to compute be isolated in V . In general the space of invariant measures of a given dynamical system could be very large (an infinite dimensional convex subset of P M (X)) but there is often some kind of particular regularity that can be exploited to characterize a particular invariant measure, isolating it from the rest. For example, let us consider the following seminorm:

µ α = sup x∈X,r>0 µ(B(x, r)) r α .
If α and K are computable and X is recursively compact then

V α,K = {µ ∈ P M (X) : µ α ≤ K} (3)
is recursively compact ([27]). This implies Proposition 19 Let X be recursively compact and T be computable on X \ D, with dim H (D) < ∞. Then any invariant measure isolated in V α,K with α > dim H (D) is computable. Once again, this is uniform in T, α, K.

We recall that in the above proposition dim H denotes the Hausdorff dimension of a set. The above general proposition allow us to obtain as a corollary the computability of many systems having absolutely continuous invariant measures. For example, let us consider maps on the interval.

Proposition 20 Let X = [0, 1], T be computable on X \ D, with dim H (D) < 1 and suppose (X, T ) has a unique absolutely continuous invariant measure µ with bounded density, then µ is computable (starting from T and a bound for the L ∞ norm of the invariant density).

Similar results hold for maps on manifolds (again see [27]).

Computing the measure from a description of the system in the class of piecewise expanding maps

As it is well known, interesting examples of systems having a unique absolutely continuous invariant measure (with bounded density as required) are topologically transitive piecewise expanding maps on the interval or expanding maps on manifolds.

We show how to find a bound for the invariant density on piecewise expanding maps. This implies that the invariant measure can be calculated starting from a description of T .

Definition 21 A nonsingular function T : ([0, 1], m) → ([0, 1], m
) is said to be piecewise expanding if 31. There is a finite set of points

d 1 = 0, d 2 , ..., d n = 1 such that T | (di,di+1) is C 2 and can be extended to a C 2 map on [d i , d i+1 ].
2. inf(T ) > 1 on the set where it is defined.

3.

T is topologically mixing4 .

It is now well known that such maps have an unique ergodic invariant measure with bounded variation density.

Such a density is also the unique fixed point of the (Perron Frobenius )

operator 5 L : L 1 [0, 1] → L 1 [0, 1] defined by [Lf ](x) = y∈T -1 x f (y) T (y)
.

We now show how to find a bound for such a density, starting from the description of the system, and then compute the associated invariant measure.

The following proposition was proved in the celebrated paper [START_REF] Lasota | On the existence of invariant measures for piecewise monotonic transformations[END_REF] (Thm. 1 and its proof) and it is now called Lasota-Yorke inequality. We give a precise statement where the constants are explicited.

(| T (x) (T (x)) 2 |) inf x∈[0,1]-{d1,...,dn} | 1 T (x) | + 2 min(d i -d i+1 )
.

The following is an elementary fact about the behavior of real sequences

Lemma 23 If a real sequence a n is such that a n+1 ≤ la n + k for some l < 1, k > 0, then sup(a n ) ≤ max(a 0 , k 1 -l ).
Proposition 24 If f is the density of the physical measure of a piecewise expanding map T as above and λ > 2. Then

V ar(f ) ≤ B 1 -2λ
where B is defined as above.

Proof. (sketch) The topological mixing assumption implies that the map has only one invariant physical measures (see [48]). Let us use the above results iterating the constant density corresponding to the Lebesgue measure. Proposition 22 and Lemma 23 give that the variation of the iterates is bounded by B 1-2λ . Suppose that the limit measure has density f . By compactness of uniformly bounded variation functions in L 1 , the above properties give a bound on the variation of f (see [START_REF] Lasota | On the existence of invariant measures for piecewise monotonic transformations[END_REF] proof of Thm. 1).

The following is a trivial consequence of the fact that

||f || ∞ ≤ V ar(f ) + f dµ.
Corollary 25 In the above situation ||f || ∞ ≤ B 1-2λ + 1. The bound on the density of the invariant measure, together with Corollary 20 gives the following uniform result on the computation of invariant measures of such maps.

Theorem 26 Suppose a piecewise expanding map T and its first and second derivatives are computable on [0, 1]-{d 1 , ..., d n }. Suppose that also its extension to the closed intervalls [d i , d i+1 ] are computable. Then, the physical measure can be computed starting from a description of the system (the points d i and the programs computing the map and its derivatives).

Proof. (sketch) Since T and T are computable on each interval [d i , d i+1 ] we can compute a number λ such that 1 < λ ≤ inf(T ) (see [27] Proposition 3) If we consider the iterate T N instead of T the associated invariant density will be the same as the one of T , and if λ N > 2, then T N will satisfy all the assumptions needed on Proposition 24. In the same way it is possible to compute an upper bound for the related B 1-2λ . Then we have a bound on the density and we can apply Corollary 20 to compute the invariant measure.

Unbounded densities and non uniformly hyperbolic maps

The above results ensure computability of some absolutely continuous invariant measure with bounded density. If we are interested in situations where the density is unbounded, we can consider a new norm, "killing" singularities.

Let us hence consider a computable function f : X → R and

µ f,α = sup x∈X,r>0 f (x)µ(B(x, r)) r α .
If α and K are computable and X is recursively compact then

V α,K = {µ ∈ P M (X) : µ f,α ≤ K} (4)
is recursively compact, and Proposition 19 also hold for the seminorm . f,α .

If f is such that f (x) = 0 when lim r→0 µ(B(x,r)) r α = ∞ this can let the norm be finite when the density diverges.

As an example, where this can be applied, let us consider the Manneville Pomeau type maps on the unit interval. These are maps of the type x → x + x z (mod 1).

When 1 < z < 2 the dynamics has a unique absolutely continuous invariant measure µ z . This measure has a density e z (x) which diverges at the origin. Moreover, e z (x) x -z+1 and is bounded elsewhere (see [START_REF] Isola | On systems with finite ergodic degree[END_REF] Section 10 and [48] Section 3 e.g.). If we consider the norm . f,1 with f (x) = x 2 we have that µ z f,1 is finite for each such z. It follows that for each such z the measure µ z is computable.

Julia sets and the Brolin-Lyubich measure

Here we explain how our method can be applied to compute the measure of maximal entropy (or Brolin-Lyubich measure) associated to rational maps of the Riemann Sphere.

It is interesting to say that this measure is supported on the Julia set (associated to the rational map) which may happen to be uncomputable! For sake of completeness we now attempt to briefly introduce computability notions for invariant compact sets, and the main results on Julia sets.

Let K be a compact subset of the plane. Informally speaking, in order to draw the set K on a computer screen we need a program which is able to decide, given some precision , if pixel p has to be colored or not. By representing pixel p by a ball B(p, ) where (p, ) ∈ Q 2 , the question one would like to answer is: does B(p, ε) intersects K ? The following definition captures exactly this idea: Definition 27 A compact set K ⊂ R 2 is said to be computable if there is an algorithm A such that, upon input (p, ):

• halts and outputs " yes" if K ∩ B(p, ) = ∅,

• halts and outputs " no" if K ∩ B(p, ) = ∅,

• run forever otherwise.

We remark that if a compact set is computable under the definition above, then it is recursively compact in the sense of Definition 11. The converse is however false.

The question of whether Julia sets are computable under this definition has been completely solved in a series of papers by Binder, Braverman and Yampolsky. See [4,[START_REF] Binder | On computational complexity of Siegel Julia sets[END_REF][START_REF] Braverman | Non-computable Julia sets[END_REF][START_REF] Braverman | Computability of Julia sets[END_REF][START_REF] Braverman | Computability of Julia sets[END_REF]]. Here we review some of their results. For simplicity, we give the definition of the Julia set only for quadratic polynomials. Consider a quadratic polynomial

P c (z) = z 2 + c : C → C.
Obviously, there exists a number M such that if |z| > M , then the iterates of z under P will uniformly scape to ∞. The filled Julia set is the compact set defined by:

K c = {z ∈ C : sup n |P n c (z)| < ∞}.
That is, the set of points whose orbit remains bounded. For the filled Julia set one has the following result: Theorem 28 ([14]) The filled Julia set K c of a computable quadratic polynomials P c is always computable.

The Julia set can now be defined by:

J c = ∂K c ,
where ∂(A) denotes the boundary of A. The Julia set is the repeller of the dynamical system generated by P c . For all but finitely many points, the limit of the n-th preimages P -n c (z) coincides with the Julia set J c . The dynamics of P c on the set J c is chaotic, again rendering numerical simulation of individual orbits impractical. Yet Julia sets are among the most drawn mathematical objects, and countless programs have been written for visualizing them.

In spite of this, the following result was shown in [START_REF] Braverman | Non-computable Julia sets[END_REF].

Theorem 29 There exist computable quadratic polynomials P c (z) = z 2 + c such that the Julia set J c is not computable.

This phenomenon of non-computability is rather subtle and rare. For a detailed exposition, the reader is referred to the monograph [START_REF] Braverman | Computability of Julia sets[END_REF].

Thus, we cannot accurately simulate the set of limit points of the preimages (P c ) -n (z), but what about their statistical distribution? The question makes sense, as for all z = ∞ and every continuous test function ψ, the following holds

1 2 n w∈(Pc) -n (z) ψ(w) -→ n→∞ ψdλ,
where λ is the Brolin-Lyubich probability measure [START_REF] Brolin | Invariant sets under iteration of rational functions[END_REF][START_REF] Lyubich | The measure of maximal entropy of a rational endomorphism of a Riemann sphere[END_REF] supported on the Julia set J c . We can thus ask whether the the Brolin-Lyubich measure is computable. Even if J c = Supp(λ) is not a computable set, the answer does not a priori have to be negative. In fact, the following result holds: Theorem 30 ( [START_REF] Binder | Computability of Brolin-Lyubich measure[END_REF]) The Brolin-Lyubich measure of computable quadratic polynomial is always computable. This result essentially follows from Theorem 17 as well. The difficulty is once again to find a recursively compact condition which characterizes Brolin-Lyubich measure. This measure happens to be singular with respect to Lebesgue, so that the absolute continuity argument does not apply. The key property allowing the application of Theorem 17 in this case is balance: a probability measure µ on C is said to be balanced with respect to a rational function R (of degree at least 2), if for every set A ⊂ C on which R is injective, we have:

µ(R(A)) = d • µ(A),
where d denotes the degree of R.

Computation of the Brolin-Lyubich measure is then reduced to show that for probability measures, being balanced is a recursively compact condition. The proof of this fact is not very difficult, but it does require to overcome some problems like the fact that the function µ → µ(A) is not computable. For more details the interested reader is referred to ([6]).

Computable systems without computable invariant measures

We have seen several techniques to establish the computability of many important invariant measures. This raises naturally the following question: does a computable system necessarily have a computable invariant measure? What about ergodic physical measures?

The following is an easy example o a simple system for which the last answer is negative, showing that the general question of computing invariant measures has some subtlety.

Let us consider a system on the unit interval given as follows. Let τ ∈ (0, 1) be a lower semi-computable real number which is not computable. There is a computable sequence of rational numbers τ i such that sup i τ i = τ . For each i consider T i (x) = max(x, τ i ) and

T (x) = i≥1 2 -i T i (x).
The functions T i are uniformly computable so T is also computable. The system ([0, 1], T ) is hence a computable dynamical system. T is nondecreasing, and T (x) > x if and only if x < τ .

This system has a physical ergodic invariant measure which is δ τ , the Dirac measure placed on τ . The measure is physical because τ attracts all the interval at its left. Since τ is not computable then δ τ is not computable. We remark that coherently with the previous theorems δ τ is not isolated.

It is easy to prove, by a simple dichotomy argument, that a computable function from [0, 1] to itself must have a computable fixed point. Hence it is not possible to construct a system over the interval having no computable invariant measure at all (we always have the δ over the fixed point). With some more work one can construct such an example on the circle. Indeed the following can be established Proposition 31 There is a computable, continuous map T on the circle having no computable invariant probability measure.

For the description of the system and for applications to reverse mathematics see [27] (Proposition 12).

Computing the speed of ergodic convergence

As recalled before, the Birkhoff ergodic theorem tells that, if the system is ergodic, there is a full measure set of points for which the averages of the values of the observable f along its trajectory (time averages) coincides with the spatial average of the observable f . Similar results can be obtained for the convergence in the L 2 norm, and others. Many, more refined results are linked to the speed of convergence of this limit. And the question naturally arise, if there is a possibility to compute this speed of convergence in a sense similar to Definition 5.

In the paper [START_REF] Avigad | Local stability of ergodic averages[END_REF] some abstract results imply that in a computable ergodic dynamical system, the speed of convergence of such averages can be algorithmically estimated. On the other hand it is also shown that there are non ergodic systems where this kind of estimations are not possible. In [28] a very short proof of this result for ergodic systems was given. We present the precise result (Theorem 39) with its proof in this section.

Convergence of random variables

We first make precise what is meant by "compute the speed of convergence" in a pointwise a.e. convergent sequence.

Definition 32 A random variable on (X, µ) is a measurable function f : X → R.

Definition 33 Random variables f n effectively converge in probability to f if for each > 0, µ{x : |f n (x)-f (x)| < } converges effectively to 1, uniformly in . That is, there is a computable function n( , δ) such that for all n ≥ n( , δ), µ{|f n -f | ≥ } < δ.

Definition 34 Random variables f n effectively converge almost surely to f if f n = sup k≥n |f k -f | effectively converge in probability to 0. Definition 35 A computable probability space is a pair (X, µ) where X is a computable metric space and µ a computable Borel probability measure on X.

Let Y be a computable metric space. A function f : (X, µ) → Y is almost everywhere computable (a.e. computable for short) if it is computable on an effective G δ -set of measure one, denoted by domf and called the domain of computability of f .

A morphism of computable probability spaces f : (X, µ) → (Y, ν) is a morphism of probability spaces which is a.e. computable.

Remark 36 A sequence of functions f n is uniformly a.e. computable if the functions are uniformly computable on their respective domains, which are uniformly effective G δ -sets. Observe that in this case, intersecting all the domains provides an effective G δ -set on which all f n are computable. In the following we will apply this principle to the iterates f n = T n of an a.e. computable function T : X → X, which are uniformly a.e. computable.

Remark 37

The space L 1 (X, µ) (resp. L 2 (X, µ)) can be made a computable metric space, choosing some dense set of bounded computable functions as ideal elements. We say that an integrable function f : X → R is L 1 (X, µ)-computable if its equivalence class is a computable element of the computable metric space L 1 (X, µ). Of course, if f = g µ-a.e., then f is L 1 (X, µ)-computable if and only if g is. Basic operations on L 1 (X, µ), such as addition, multiplication by a scalar, min, max etc. are computable. Moreover, if T : X → X preserves µ and T is a.e. computable, then f → f • T (from L 1 to L 1 ) is computable (see [START_REF] Hoyrup | An application of Martin-Löf randomness to effective probability theory[END_REF]).

Let us call (X, µ, T ) a computable ergodic system if (X, µ) is a computable probability space where T is a measure preserving morphism and (X, µ, T ) is ergodic. Let ||f || denote the L 1 norm or the L 2 norm.

Proposition 38 Let (X, µ, T ) be a computable ergodic system. Let f be a computable element of L 1 (X, µ) (resp. L 2 (X, µ)).

The L 1 convergence (resp. L 2 convergence) of the Birkhoff averages

A n = (f + f • T + . . . + f • T n-1 )/n is effective. That is: there is an algorithm n : Q → N such that for each m ≥ n( ), ||A m -f dµ|| ≤ .
Moreover the algorithm depends effectively on T, µ, f . Proof. Replacing f with f -f dµ, we can assume that f dµ = 0. The sequence ||A n || is computable ( see Remark 37 ) and converges to 0 by the ergodic theorems.

Given p ∈ N , we write m ∈ N as m = np + k with 0 ≤ k < p. Then

The set of computable points in X (see Definition 6) being countable, is a very small (invariant) set, compared to the whole space. For this reason, a computable point could rarely be expected to be typical for the dynamics, as defined before. More precisely, the Birkhoff ergodic theorem and other theorems which hold for a full measure set, cannot help to decide if there exist a computable point which is typical for the dynamics.

A number of theoretical questions arise naturally from all these facts. Due to the importance of forecasting and simulation of a dynamical system's behavior, these questions also have some practical motivation.

Problem 44 Since simulations can only start with computable initial conditions, given some typical statistical behavior of a dynamical system, is there some computable initial condition realizing this behavior? How to choose such points? Such points could be called pseudorandom points, and a result showing its existence and their computability from the description of the system could be seen as a constructive version of the pointwise ergodic theorem.

Meaningful simulations, showing typical behaviors of the dynamics can be performed only if computable, pseudorandom initial conditions exist. Computable points are the only points we can use when we perform a simulation or some explicit computation on a computer.

Based on a sort of effective Borel-Cantelli lemma, in [25] the above problem was solved affirmatively for a class of systems which satisfies certain technical assumptions which includes systems whose decay of correlation is faster than C log 2 (time). Using the results on the estimation of the rate of convergence given in the previous section, it is possible to remove these technical assumptions on the speed of decay of correlations. It is also worth to remark that the result is uniform also in T and µ (the pseudorandom points will be calculated from a description of the system).

The following result ([25], Theorem 2 or [28]) shows that from a sequence f n which converges effectively a.s. to f and from its speed of convergence, it is possible to compute points x i for which f n (x i ) → f (x i ).

Theorem 45 Let X be a complete metric space. Let f n , f be uniformly a.e. computable random variables. If f n effectively converges almost surely to f then the set {x : f n (x) → f (x)} contains a sequence of uniformly computable points which is dense in Supp(µ). Moreover, the effective sequence found above depends algorithmically on f n and on the function n(δ, ) giving the rate of convergence Since by the results of the previous section n(δ, ) can be calculated starting from T , µ and f , we can directly apply the above Theorem to compute typical points for the dynamics. Indeed, the following holds (see [28] for the details) Theorem 46 If (X, µ, T ) is a computable ergodic system and f is L 1 (X, µ) and a.e. computable, then there is a uniform sequence x i of computable points which is dense on the support of µ such that for each i lim n→∞ 1 n f (T n (x i )) = f dµ.

Moreover this sequence can be computed starting from a description of T , µ and f .

The uniformity in f of the above result together with the existence of a r.e. collection of computable observables which is dense in the space of compactly supported continuous functions, imply the following (see again [28] for the details) Theorem 47 If (X, µ, T ) is a computable ergodic system then there is a uniform sequence x n of computable points which is dense on the support of µ such that for each n, x n is typical for µ. Moreover this sequence can be computed starting from a description of T and µ.

In particular, for the classes of systems where the interesting invariant measure can be computed by the description of the system (see Section 3.3.1, Theorem 26), we obtain that in turn the pseudorandom points can be computed starting from a description of the system alone.

Corollary 48 Each piecevise expanding map, with computable derivatives, as in the assumptions of Theorem 26 has a sequence of pseudorandom points which is dense in the support of the measure. Moreover this sequence can be computed starting from the description of the system.

These two statements can be seen as constructive/effective versions of the ergodic theorem.

Conclusions and directions

In this article we have reviewed some recent results about the rigorous computation of invariant measures, invariant sets and typical points. Here, the sentence rigorous computation means "computable (up to any required precision) by a Turing Machine". Thus, this can be seen as a theoretical study of which infinite objects in dynamics can be arbitrarily well approximated by a modern computer (in an absolute sense), and which cannot. In this line, we presented some general principles and techniques that allow the computation of the relevant objects in several different situations. On the other hand, we also presented some examples in which the computation of the relevant objects is not possible at all, setting some theoretical limits to the abilities of computers when used to simulate dynamical systems.

The examples of the second kind, however, seem to be rather rare. An important question is therefore whether this phenomenon of non-computability is robust or prevalent in any sense, or if it is rather exceptional. For example, one could ask whether the non-computability is destroyed by small changes in the dynamics or whether the non-computability occurs with small or null probability.

Besides, in this article we have not considered the efficiency (and therefore the feasibility) of any of the algorithms we have developed. An important (and more difficult) remaining task is therefore the development of a resource bounded version of the study presented in this paper. In the case of Julia sets, for instance, it has been shown in [START_REF] Braverman | Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable[END_REF][START_REF] Rettinger | A Fast Algorithm for Julia Sets of Hyperbolic Rational Functions[END_REF][START_REF] Braverman | Parabolic Julia Sets are Polynomial Time Computable[END_REF] that hyperbolic Julia sets, as well as some Julia sets with parabolics, are computable in polynomial time. On the other hand, in [START_REF] Binder | On computational complexity of Siegel Julia sets[END_REF] it was shown that there exists computable Siegel quadratic Julia sets whose time complexity is arbitrarily high.

For the purpose of computing the invariant measure form the description of the system, in section 3.3.1 we had to give explicit estimations on the constants in the Lasota Yorke inequality. This step is important also when techiques different from ours are used (see [START_REF] Liverani | Rigorous numerical investigations of the statistical properties of piecewise expanding maps-A feasibility study[END_REF] e.g.). Similar estimations could be done in other classes of systems, following the way the Lasota Yorke inequality is proved in each class (although, sometimes this is not a completely trivial task and requires the "effectivization" of some step in the proof). A more general method to have an estimation for the constants or other ways to get information on the regularity of the invariant measure would be useful.

Definition 7 (

 7 Effective open sets) We say that an open set U is effective if there is an algorithm A : N → B such that U = n A(n). Observe that an algorithm which diverges on each input n enumerates the empty set, which is then an effective open set. Sequences of uniformly effective open sets are naturally defined. Moreover, if (U i ) i∈N is a sequence of uniformly effective open sets, then i U i is an effective open set. Definition 8 (Effective G δ -set) An effective G δ -set is an intersection of a sequence of uniformly effective open sets.

Proposition 22

 22 Let T be a piecewise expanding map. Let f be of bounded variation in [0, 1] and let denote its variation by V ar(f ). Let d 1 , ..., d n be the discontinuity points of T . If λ = inf x∈[0,1]-{d1,...,dn} T (x). Then V ar(Lf ) ≤ 2λV ar(f ) + B||f || 1 where B = sup x∈[0,1]-{d1,...,dn}

Figure 1 :

 1 Figure 1: The map T .

Find a N such that 1 n f • T n differs from f dµ less than a given error for each n ≥,in some sense.

If the invariant measure is unique in V the isolating ball is not necessary.

For the sake of simplicity we will consider the simplest setting in which we can work and give precise estimations. Such a class was generalized in several ways. We then warn the reader that in the current literature, by piecewise expanding maps it is meant something slightly more general than the definition we give here.

A system is said to be topologically mixing if, given sets A and B, there exists an integer N , such that, for all n > N , one has f n (A) ∩ B = ∅.

Note that this operator corresponds to the above cited transfer operator acting on densities instead of measures.

Let > 0. We can compute some p = p( ) such that ||A p || < /2. Then we can compute some n( ) ≥ 2 ||f ||. The function m( ) := n( )p( ) is computable and for all m ≥ m( ), ||A m || ≤ .

Effective almost sure convergence

Now we use the above result to find a computable estimation for the a.s. speed of convergence.

Theorem 39 Let (X, µ, T ) be a computable ergodic system. If f is L 1 (X, µ)computable, then the a.s. convergence is effective. Moreover, the rate of convergence can be computed as above starting from T, µ, f . This will be proved by the following Proposition 40 If f is L 1 (X, µ)-computable as above, and ||f || ∞ is bounded, then the almost-sure convergence is effective (uniformly in f and a bound on ||f || ∞ and on T , µ ).

To prove this we will use the well known Maximal ergodic theorem:

The idea is simple: compute some p such that ||A f p || 1 is small, apply the maximal ergodic theorem to g := A f p , and then there is n 0 , that can be computed, such that

Proof of Proposition 40. Let , δ > 0. Compute p such that ||A f p || ≤ δ /2. Applying the maximal ergodic theorem to g := A f p gives:

23

Now, A g n is not far from A f n : expanding A g n , one can check that 5), we then derive

As n 0 can be computed from δ and , we get the result.

Remark 42 This result applies uniformly to a uniform sequence of computable L ∞ (X, µ) observables f n .

We now extend this to L 1 (X, µ)-computable functions, using the density of

Remark 43 We remark that a bounded a.e. computable function, as defined in Definition 35 is a computable element of L 1 (X, µ) (see [START_REF] Hoyrup | An application of Martin-Löf randomness to effective probability theory[END_REF]). Conversely, if f is a computable element of L 1 (X, µ) then there is a sequence of uniformly computable functions f n that effectively converge µ-a.e. to f .

Computing pseudorandom points, constructive ergodic theorem

In this section we show how the previous results on computation of invariant measures and speed of convergence allow to compute points which are statistically typical for the dynamics. Let X again be a computable metric space and µ a computable probability measure on it. Suppose X is complete. Points satisfying the above recalled pointwise ergodic theorem for an observable f , will be called typical for f .

Points which are typical for each f which is continuous with compact support are called typical for the measure µ ( and for the dynamics).