A level of Martin-Lof randomness.
compression algorithmKolmogorov complexityMartin-L\"f randomnessmodified symbolic space multiplier programrandom sequential string
Research exposition (monographs, survey articles) pertaining to probability theory (60-02) Other physical applications of random processes (60K40) Applications of statistics in engineering and industry; control charts (62P30) Applications of statistics to physics (62P35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
The author defines a concrete class of invertible compression algorithms for finite sequential strings of binary and larger radix-based systems and studies them for several radixes and examples of random and non-random sequential strings; these algorithms are called modified symbolic space programs by the author. It turns out that random sequences for those algorithms can have a compression ratio greater than one. He draws connections to the complexity theory of Kolmogorov and Martin-Löf. The contribution of different authors (among them R. J. Solomonoff, G. Pólya, G. J. Chaitin) to the problem of randomness of sequential strings is outlined. Applications to statistical communication theory, computing and other fields are sketched. The author assumes that, in the literature, a random sequential string is defined to be a string if it is not compressible, and the only compressible strings are non-random sequential strings. As a new definition of randomness, the author proposes ``a random sequential string may be compressible based on the type of algorithmic system used as a program for that random sequential string (see Chapter 11, Conclusions).
This page was built for publication: A level of Martin-Lof randomness.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2898374)
