Transcript Laplce’s predictibility

Randomness and Determination, from
Physics and Computing towards
Biology
Giuseppe Longo
LIENS, CNRS – ENS, Paris
http://www.di.ens.fr/users/longo
Classical dynamical determinism and
unpredictability
• A physical system/process is deterministic when we have or
we believe that it is possible to have a set of equations or an
evolution function ‘describing’ the process;
i.e. the evolution of the system is ‘fully’ determined
by its current states and by a ‘law’.
Classical/Relativistic systems are State Determined Systems:
randomness is an epistemic issue
Classical dynamical determinism and
unpredictability
1. Classical and Relativistic Physics are deterministic: randomness is
deterministic unpredictability (in chaotic systems)
2. Quantum Mechanics is not deterministic
(intrinsic/objective role of probabilities in constituting the theory
– the measure; entanglement, no hidden variables)
Recent survey/reflections: [Bailly, Longo, 2007], [Longo, Paul, 2008]
Early confusion in Computing:
A “non-deterministic” Turing Machine is a classical deterministic
device (ill-typed), unless a “non-classical” physical process (which
one?) specifies/implements the branching
Deterministic unpredictability
Classical (dynamical) deterministic unpredictability:
a relation between
1. a formal-mathematical system (equations, evolution functions…)
2. a physical process, measured by intervals (the access).
By the mathematical system one cannot predict (over short, long
time) the evolution of the physical process:
e. g.: 1. describing/modelling 2. is non linear:
a. Mixing (a weak chaos) = decreasing correlation of observables:
(|Cn(fi, fj)| ≤ ci,j/nα for all n ≥ 1),
b. Chaotic = sensitivity, topological transitivity, density of periodic
points… pure Mathematics
(decreasing knowledge about trajectories, increasing ‘entropy’)
 Randomness
Randomness as deterministic
unpredictability
Classical (epistemic) randomness
is defined by
deterministic unpredictability (short, long time)
Examples: dies, coin tossing, a double pendulum, the Planetary
System (Poincaré, 1890; Laskar, 1992)… finite (short and long)
time unpredictability
(the dies, a SDS, ‘know’ where they go: along a geodetics, determined
by Hamilton’s principle).
Laplace:
1. infinitary demon: OK (over space-time continua);
2. determination  predictability (except singularities): Wrong!
Part I: Classical Dynamical Systems and Computing
Dynamical vs. Algorithmic Randomness
Generic (point/trajectory) in Dynamics
Objects are ‘generic’ in Physics: they are experimental and
theoretical invariants (chose any falling body, gravitating
planets…)
A Methodological Aim:
in a deterministic dynamical system (D,T,):
« Pick a generic point in D, ‘at random’ » (randomize)
replaced by « pick a random (as generic) point in D »
Mathematically:
« a probabilistic property P holds for almost all points»
replaced by
« the set of random points has measure 1 and P holds
for all random points »
Birkhoff randomness in Dynamical Systems
Given (D, T, ), dynamical system, a point x is generic (or
typical, in the ergodic sense) if, for any observable f,
Limn (f(x) + f(T(x)) +…+ f(Tn(x)))/n = ∫ f d
That is, the average value of the observable f along the trajectory
x, T(x),… Tn(x) …
(its time average)
is asymptotically equal to the space average of f (i.e. ∫ f d).
A generic point is a (Birkhoff) random point for the dynamics.
It is a purely mathematical and limit notion, within physicomathematical dynamical systems, at asymptotic time.
 ML-randomness
Algorithmic Randomness as strong undecidability
Algorithmic randomness (Martin-Löf, ‘65; Chaitin, Schnorr….)
(for infinite sequences in Cantor Space D = 2):
Def. , measure on D, an effective tatistical test is
an (effective) sequence {Un}n, with (Un)  2n
I.e. a statistical test is an infinite decreasing sequence of effective
open set in Cantor’s 2 (thus, it is given in Recursion Theory);
Def. x is random if, for any statistical test {Un}n, x is not in nUn,
(x passes all tests)
Random = not being contained in any effective intersection
= to stay “eventually outside any test” (it passes all tests)
Algorithmic randomness and undecidability
• Algorithmic randomness: a purely computational notion (a lot
of work by Chaitin, Calude… Gacs, Vyugin, Galatolo).
• An (infinite) algorithmic-random sequence contains no infinite
effectively generated (r.e., semidecidable) subsequence.
Thus: Algorithmic randomness is (strictly) stronger than
undecidability (non r.e., Gödel-Turing’s sense):
there exist non rec. enum. sequences which are not algorithmically random
(e.g. x1 e1 x2 e2 x3 … x algo-random, e effective)
Note: there is no randomness in finite time sequential computing!
At most uncompressibility (finite Kolmogoroff complexity)
Dynamical random = algorithmic random
(Hoyrup, Rojas Theses)
Dynamical random = algorithmic random
(Hoyrup, Rojas Theses)
Given a “mixing” (weakly chaotic) dynamics (D, T, ), with good
computability properties (the metric, the measure… are
effective), then
Main Theorem:
‘A point x in D is generic (Birkhoff random) for the dynamics iff it
is (Schnorr) algorithmically random’.
Note: at infinite time:
Dynamical randomness (a la Birkhoff) derives from Poincaré’s
Theorem (deterministic unpredictability)
Algorithmic randomness is a strong form of (Gödel’s)
undecidability
Q.E.D.
Towards Biology
The Physical Singularity of Life Phenomena
in terms of Dualities
The Physical Singularity of Life Phenomena
in terms of Dualities
• Physics: generic objects and specific trajectoires (geodetics)
Biology: generic trajectories (compatible/possible) and specific
objects (individuation)
[Bailly, Longo, 2006]
The Physical Singularity of Life Phenomena
in terms of Dualities
•
Physics: generic objects and specific trajectoires (geodetics)
Biology: generic trajectories (compatible/possible) and specific
objects (individuation)
[Bailly, Longo, 2006]
•
Physics: energy as operator Hf, time as parameter f(t, x);
Biology: time as operator, energy as parameter
Time given by (speed of) entropy production by all irreversile
processes; it acts as an operator on a state function (bio-mass
density)
Applications both in phylogenesis (long-time: Gould’s curb)
and ontogenesis (short-time: scalling factors in allometry):
F. Bailly, G. Longo. Biological Organization and Anti-Entropy,
in J. of Biological Systems, Vol. 17, n.1, 2009.
Randomness in Life Phenomena
Recall in Computing and Physics:
1. For infinite sequences:
(Birkhof) dynamical randomness = algorithmic randomness
2. In finite time:
determistic unpredictability ≠ (quantum) indetermination and
randomness
(epistemic vs. intrinsic; Bell inequalities)
Yet, in infinite time, they merge (semi-classical limit)!
[T. Paul, 2008].
Randomness in Life Phenomena
Physics: all within a given phase (reference) space (the possible states
and observables).
Biology: intrinsic indetermination due to change of the phase space,
in phylogenesis (ontogenesis?);
A proper notion of biological randomness, at finite short/long time?
Due to the entanglement of the two physical notions?
Randomness: Physics/Computing/Biology
1. Physics: 2 forms of randomness (different probability measures)
2. In Concurrency? In Computers’ Neworks? A lot of work…
3. Biology: the sum of all forms? What can we learn from the
different forms of randomness and (in-)determination?
Physical time vs. Randomness
General tentative approach to time as an irreversible
parameter (in Physical Theories)
Physical time vs. Randomness
Preliminary Remarks
1. There is no “irreversible time” in the mathematics of classical
mechanics (Euler-Lagrange, Newton-Laplace... equations are
time-reversible; also a linear field has “reverse determination”).
2. Classically, irreversible time appears in
2.1 Deterministic chaos, where randomness is unpredictability (an
action at finite time - short/long; decreasing knowledge);
2.2 Thermodynamics: increasing entropy (dispersion of
trajectories, diffusion of a gas, of heath… along random paths)
Notes: underlying a diffusion (e.g. energy degradation) there is
always a random path;
2.1 and 2.2: dispersion of trajectories (entropy increases in both)
Thesis: Irreversible Time is Randomness
(in Physical Theories)
Thesis 1: Irreversible Time implies Randomness
(in Physical Theories)
By the previous argument:
Classical Physics: the arrow of time is related (“implies”)
randomness (by deterministic unpredictability and random walks
in thermodynamics), in finite (not asymptotic) time.
But also, in Quantum Physics:
• +t and -t may be interchanged in Schrödinger equation, as -i is
equivalent to +i (time may be reversed)
• Irreversible time appears at the (irreversible) act of measure,
which gives probability values (intrinsic randomness, to the
theory)
Thus, if one wants (irreversible) time, one has randomness.
Conversely: Randomness implies
Irreversible Time
• Classical Physics: Randomness is (deterministic) unpredictability
But, unpredictability concerns predicting, thus the future, in
time (decreasing knowledge or no inverse map).
An epistemic issue, both in Dynamics and Thermodynamics
(increasing entropy)
• Similarly, the intrinsic randomness in Quantum Physics, concern
the irreversible act of measure, irreversible in time:
measure produces irreversible time, by a “before” and an “after”.
In conclusion, in Physics, by the “structure of determination”:
(irreversible) time and randomness are “related” (equivalent?)
What about Biology?
Life phenomena include:
1 - Irreversible thermodynamic processes (with their irreversible
time)
But also:
2.1 Darwinian Evolution (increasing phenotypic complexity, Gould
– number of tissue differentiations, of connections in networks)
2.2 Morphogenesis (embryogenesis and its opposite:
“disorganization” - death)
Evolution and Morphogenesis are setting-up of organization (the
opposite of entropy and its internal random processes)
Death is tissue disorganization and includes the randomness in
thermodynamic processes (entropy increase)
The ‘double’ irreversibility of Biological Time
•
Evolution, morphogenesis and death are strictly irreversible,
but their irreversibility is proper, it adds on top of the
physical irreversibility of time (thermo-dynamical)
•
It is due to a proper observable: biological organization
(integration/regulation between different levels of
organization in an organism)
•
This observable: anti-entropy:
F. Bailly, G. Longo. Biological Organization and Anti-Entropy, in J. of
Biological Systems, Vol. 17, n.1, 2009.
One reason for an intrinsic, proper Biological Randomness...
Some references (more on http://www.di.ens.fr/users/longo )
•
Bailly F., Longo G. Mathématiques et sciences de la nature. La singularité
physique du vivant. Hermann, Visions des Sciences, Paris, 2006.
•
M. Hoyrup, C. Rojas, Theses, June, 2008 (see http://www.di.ens.fr/users/longo )
•
Bailly F., Longo G., Randomness and Determination in the interplay between the
Continuum and the Discrete, Mathematical Structures in Computer Science, 17(2),
pp. 289-307, 2007.
•
Bailly F., Longo G. Extended Critical Situations, in J. of Biological Systems, Vol. 16,
No. 2, 1-28, 2007.
•
F. Bailly, G. Longo. Biological Organization and Anti-Entropy, in J. of Biological
Systems, Vol. 17, n.1, 2009.
•
G. Longo. From exact sciences to life phenomena: following Schrödinger on
Programs, Life and Causality, lecture at "From Type Theory to Morphological
Complexity: A Colloquium in Honour of Giuseppe Longo," to appear in Information
and Computation, special issue, 2008.
•
G. Longo, T. Paul. The Mathematics of Computing between Logic and Physics. Invited
paper, Computability in Context: Computation and Logic in the Real World,
(Cooper, Sorbi eds) Imperial College Press/World Scientific, 2008.