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.