Abstract:
The first of our two main goals is investigating the relation between the notions of algorithmic
randomness and dynamical typicalness. The former express the “algorithmic unpredictability”
of individual infinite sequences with respect to a given probability measure
and is modeled with the tools of computability theory. The latter, usually modeled in the
framework of ergodic theory/dynamical systems, express the “physical plausibility” of an
initial condition with respect to its evolution under some dynamics (a physically plausible
point should follow the “expected” or “typical” behaviour of the system). Roughly, the
motivation is the following: absolutely complete knowledge of the state of a physical system
is unattainable (for many reasons). Now, supposing we access the physical world by “algorithmic
means” (measurements are always finite approximations possibly elaborated later
in computers) then it makes sense to modelize a “physical” point as being “algorithmically
unknownable”. To study this, it is essential to develop algorithmic tools adapted to the
usual context in which ergodic theory takes place and this is what the entire first part of
this thesis is devoted to. Then we consider two notions of algorithmic randomness due to
Martin-Löf and Schnorr and prove three main results, thus establishing the relationship
with typicality. i) In any computable metric space with an arbitrary probability measure μ,
there always exists a universal uniform Martin-Löf-randomness test; ii) If μ is computable,
then the trajectory of a Martin-Löf random point under any computable ergodic dynamics
always follow the typical statistical behaviour of the system; iii) A point is Schnorr random
if and only if its trajectory follows the typical behaviour of any computable mixing
dynamics. As a second goal we study from a highly theoretical point of view the problem
of simulating randomness or typical statistical behaviours on a computer, with a particular
interest in the ergodic behaviour of dynamical systems. We prove that for several classes of
dynamical systems having a single “physically relevant” invariant measure, i) this measure
is computable and ii) there exist computable points (the only ones we have access in computer
simulations) following the typical behaviour of the system. As a direct application we
obtain the existence of computable reals which are Borel-normal with respect to any base.