Non-stochastic infinite and finite sequences
Dr Vladimir V'yugin, Institute of Problems of Information Transmission, Moscow

Abstract: Combining outcomes of coin-tossing and transducer algorithms it is possible to generate with probability close to 1 very pathological sequences for which computable probabilistic forecasting is impossible. These sequences are not random with respect to any reasonable probability distribution. A natural consequence from the definition of such sequences is that each simple measure of the set of all such sequences is equal to 0. It was Kolmogorov's and Levin's idea to estimate the probability of generating such sequences in the combinations of probabilistic and algorithmic processes. We present several results in this direction for infinite sequences and asymptotic results for finite sequences.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 23 June 1998.

back