A level of Martin-Lof randomness.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1271.60005
author: Bradley S. Tice
publication date: 2012-07-11T00:00:00Z
Mathematics Subject Classification ID: 60-02
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 60K40
Mathematics Subject Classification ID: 62P30
Mathematics Subject Classification ID: 62P35
zbMATH DE Number: 6054390
zbMATH Keywords: random sequential string
zbMATH Keywords: compression algorithm
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Martin-L\"f randomness
zbMATH Keywords: modified symbolic space multiplier program
MaRDI profile type: Publication
title: A level of Martin-Lof randomness.
review text: 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).
reviewed by: Uwe Küchler
description: scientific article; zbMATH DE number 6054390