A level of Martin-Lof randomness. (Q2898374)

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).