*Mathematical Structures in Computer Science* (MSCS),

Cambridge Univ. Press, G. Longo editor, special issue on

**Developments of the concepts of randomness,
statistic, and probability**

**PREFACE
BY THE EDITORS**

In a more or less
definite manner and no matter what verbal expressions might have been used, the
concept that we nowadays designate by the word ÔprobabilityÕ must have acquired
form in the mind of human beings since the dawn of thought, as a nuance added
to the idea of unpredictability: random, but not entirely. For at any time
throughout history it must have been felt that unpredictability can be more or
less radical. And starting from some later time it must have been remarked that
what we now qualify as ÔstatisticalÕ and Ôstatistically stableÕ drifts away
from ÔhazardÕ and brings closer to something else that has been baptized
ÔprobabilityÕ and has been fuzzily conceived as being virtual and ÔidealÕ in
some sense.

During
a very long time the idea tied with the word ÔprobabilityÕ has conserved this
nascent conceptual status of just an unrealized potentiality spread around the
concepts of radical unpredictability – ÔhazardÕ – and partial
predictability (what we now call ÔstatisticalÕ), moving without a definite
contour along the dimension vaguely sketched out by these two concepts inside
the magma of current thought.

Only starting
from the 17th century did this idea begin to acquire some inner structure,
first via a work of Blaise Pascal (1654), but mainly by Jacob BernoulliÕs well
known concept of ÔlawÕ of large numbers (1690, published in 1715). Later
Richard von Mises clarified further the very peculiar relation, inside this
ÔlawÕ, between a just posited real number called the probability of an event
from a given collection of events, and the sequence of rational numbers that
express the evolving relative frequencies of the outcomes of this event when
the involved random experiment is repeated: In the view of Bernoulli and of von
Mises these relative frequencies determine – but in a probabilistic sense
– the numerical value of the probability of the considered event.

Finally,
in 1933 Kolmogorov endowed us with a genuine mathematical syntax of the concept
of probability. Inside the general mathematical theory of measures, he has
fully worked out a particular syntactic entity that he named a probability
space founded upon a universe of elementary events on which an algebra of
events is defined, on which a probability ÔmeasureÕ is posited to ÔexistÕ: thus
everything becomes both subtle and entirely definite from a formal point of
view. KolmogorovÕs framework is a calculus with random events: they are
assumed, but not defined. And this calculus is expressed in the terms of the
theory of sets, whereby, likely in order to insure maximal generality, it
introduces minimal logical and semantic specifications.

In
this way came into being a paradigmatic case of the problem – that is far
from having been solved – of the optimality, for a given pragmatic aim,
of the relations between semantic and syntax. This problem however was ignored,
and it continues to be ignored. The probabilistic syntax constructed by
Kolmogorov has been considered to be able to host and to quite satisfactorily
organize formally any particular factual probabilistic problem. Nearly nobody
seemed to be troubled by the fact that, in any given factual probabilistic
situation, in order to calculate predictions one has to specify numerically the
individual probability of each event involved in that particular factual
situation, whereas KolmogorovÕs theory of probabilities contains exclusively
general constraints on a probability measure, quite independent of any
particular probabilistic situation. So the modalities of applicability of
KolmogorovÕs theory of probabilities remained non specified.

During
the '60s, Kolmogorov – as yet another of his contributions to the theory
of computability – proposed a notion of ÒincompressibleÓ (finite) string,
that shares many natural properties of the intuitive notion of Òrandom stringÓ: a
universal Turing machine cannot produce that string with an input shorter than
the string itself. He then conjectured that an infinite sequence could be
defined to be random if all its (finite) prefixes are incompressible. In the
'65, Martin-Lšf proposed a notion of infinite (algorithmic) random sequence,
which started the novel discipline of Algorithmic Information Theory. He also
proved that KolmogorovÕs program to define a random sequence by the
incompressibility of its prefixes cannot work with KolmogorovÕs definition of
incompressibility. Independently, around the same time, Chaitin proved that, by
using a universal prefix-free Turing machine (instead of a universal Turing machine), one
could recover KolmogorovÕs intuition: an infinite sequence is Martin-Lšf random
if and only if its prefixes are incompressible by a universal prefix-free
Turing machine. Surprisingly enough, till now these two areas initiated by
Kolmogorov have little bridging results: algorithmic randomness characterizes
asymptotically randomness as a strong form of undecidability and remains within
the realm of theories of effective computability, while general measure theory
(theory of integration) incorporated the work on probability measures. And both
theories seem to have little or no interaction with physically generated
randomness, in particular, quantum randomness.

This
is another illustration of the fact that a syntax that has been conceived as a
form offered for hosting a basic concept active inside current scientific
conceptualization, can indefinitely remain devoid of an explicitly constructed
applicability to this basic concept.

Progressively
however – with remarkable slowness – under the pressure of the
requirements of effectiveness that stem from the theory of computation, it
became clear that the factual concept of probability inherited from Bernoulli
and von Mises which in KolmogorovÕs formalization has been incorporated just as
it stands, is not an effective concept. And so it became disturbing that up to
this very day no general effective method is available for defining the
distribution of the numerical probabilities of the events involved in a given
particular factual probabilistic situation. The strongest reaction was that of
Kolmogorov himself: During the decade 1980 he kept asserting that his Ôtheory
of probabilitiesÕ has to be considered as, exclusively, a chapter of the
mathematical theory of measures, devoid of factual applicability.

Meanwhile,
as it is well known, the quantum mechanical concept of probability exhibited
structural specificities that hinder its incorporation in KolmogorovÕs
classical formal concept. And recently, several authors tried to identify the
source from which the quantum probabilities could be derived instead of being
postulated, but without stressing the distinction between factual data and
formal ones. This amounts to a complexified version of the questions raised by
the classical concept of probability.

In
these circumstances it seemed useful to dedicate a special issue of MSCS
susceptible to bring forth a critical and constructive examination of the
present conceptual situation in the field of
randomness-statistic-probabilities. In order to favour the emergence of such a
result we called for any contribution making use of the concepts of hazard,
statistic and probability, in several domains; at the same time we announced
the possibility of a final debate permitting to draw global conclusions on the
general nowadays concept of probability, to be published at the end of this
special issue.

We
warmly thank the contributors for their collaboration and we hope that this
volume contains the germs of an improved and quite general concept of
probability.

Giuseppe Longo,
Editor-in-Chief of MSCS

Mioara
Mugur-SchŠchter, Guest editor of this special issue

**Workshop, debate:**

**on the present developmentS **

**of the concept of probability AND RANDOMNESS**

**28 oct. 2011 **

**Ecole Normale SupŽrieure, 45 ****rue d'Ulm, Žtage 1, Salle Actes**

**10h-12h and 14h-18h**

After a brief opening by G.
Longo, editor-in-chief of the journal, and an introduction by the guest editor,
M. MŸgur-Schachter, seven of the authors of a paper in the special issue:

Alastair A. Abbott, *Univ. of Auckland* ; Cristian S. Calude, *Univ. of Auckland*
; Leon Cohen, *City Univ.
of New York ; *Maria Luisa Dalla Chiara, *Univ. of Florence*; Roberto Giuntini, *Univ.
of Florence*; Annick Lesne, *Univ.
Paris 6*; David Miller, *Univ. of Warwick, UK*; Mioara Mugur-SchŠchter*,
CeSEF, Paris*; Christopher
Porter, *Notre Dame U. *; Giuseppe Sergioli, *Univ. of Florence*;
Karl Svozil, *Vienna Univ. of Technology*.

will expose briefly her or
his view on the present stage concerning the concepts of probability and
randomness, and in particular on
the questions proposed in the "invitation". These
presentations are meant to open a debate among the speakers and with the
audience on the theme of the meeting.