Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657797 | Theoretical Computer Science | 2005 | 47 Pages |
Abstract
The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Löf) and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. The issues are the following:
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter Gács,