The goal of the talk is to try to give definitions of randomness in the terms of computability.

Let us consider infinite sequences of zeros and ones.

The classical probability theory fails to distinguish between random and non-random sequences. The first attempt to do that is due to von Mises (1919) but it suffered some vagueness. The theory of algorithms contributed new ideas to the task of defining what an individual random sequence is.

In fact, a random sequence has at at least four faces.
First, it is stochastic; that means, the sequence itself as well as any of its reasonable subsequences has the property of frequency stability.
Second, it is chaotic; that means, it is disordered, i. e. the occurences of its terms are not governed by any reasonable rule, so the sequence itself has no reasonable description.
Third, it is typical; that means, it belongs to any reasonable majority.
Fourth, it is unpredictable; that means, one who gambles on it cannot win by using any reasonable strategy.

All the four formulations use the word "reasonable". In each of the four cases, the theory of algorithms allows to fill that word with some exact meaning. So four well-defined classes of sequences appear. And each of them claims to be the true class of random squences. Some of those claims are more justified than others.


REFERENCES:

1. A. N. Kolmogorov, and V. A. Uspensky.
Algorithms and randomness, SIAM J. Theory of Probability and Its Applications, vol. 32 (1987), pp. 389-412.

2. V. A. Uspensky, A. L. Semenov, and A. Kh. Shen.
Can an individual sequence of zeros and ones be random?, Russian Mathematical Survey, vol. 45 (1990), no. 1, pp. 121-189.

3. V. Uspensky, and A. Semenov.
Algorithms: Main Ideas and Applications., Kluwer, 1991. - 269 pp.

4. An. A. Muchnik, A. L. Semenov, V. A. Uspensky.
Mathematical metaphysics of randomness, Theoretical Computer Science, vol. 207 (1998), pp. 263-317.