Prefix and plain Kolmogorov complexity characteriz

Authors: Bruno Bauwens

Publish Date: 2015/05/01

Volume: 54, Issue: 5-6, Pages: 615-629

PDF Link

Abstract

Miller J Symb Log 693907–913 2004 http//projecteuclidorg/euclidjsl/1096901774 and independently Nies et al J Symb Log 702515–535 2005 gave a complexity characterization of 2random sequences in terms of plain Kolmogorov complexity Ccdot they are sequences that have infinitely many initial segments with O1maximal plain complexity among the strings of the same length Later Miller Notre Dame J Form Log 504381–391 2009 showed that prefix complexity Kcdot can also be used in a similar way a sequence is 2random if and only if it has infinitely many initial segments with O1maximal prefix complexity which is n + Kn for strings of length n The known proofs of these results are quite involved in this paper we provide elementary proofs Miller J Symb Log 693907–913 2004 http//projecteuclidorg/euclidjsl/1096901774 also gave a quantitative version of the first result the mathbf0randomness deficiency of a sequence omega equals lim inf n n Comega 1dotsomega n + O1 Our simplified proof can also be used to prove this We show and this seems to be a new result that a similar quantitative result is also true for prefix complexity mathbf0randomness deficiency equals lim inf n n + KPn Komega 1dotsomega n+ O1

Keywords: