The Complexity of the Set of Nonrandom Numbers
No Thumbnail Available
Date
2007-02-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Let C and H denote the plain and prefix-free Kolmogorov complexity, respectively. Then the sets NRC of nonrandom numbers with respect to C has neither a maximal nor an r-maximal superset. The set of NRH of nonrandom numbers with respect to H has an r-maximal but no maximal superset. Thus the lattices of recursively enumerable supersets (modulo finite sets) of NRC and NRH are not isomorphic.
Further investigations deal with the related set NRW of all numbers x which are the maximum of some r.e. set with an index e < x. Friedman originally asked whether NRW is Turing equivalent to K and Davie provided a positive answer for many acceptable numberings.
Later Teutsch asked the related question whether one can choose the underlying acceptable numbering such that NRW is either an r.e. or co-r.e. set. A negative answer is provided to this question and the position of NRW in the difference-hierarchy is provided:
one can choose the underlying numbering such that NRW is a co-2-r.e. set but NRW is never a 2-r.e. set. Furthermore, if the underlying numbering is a Kolmogorov numbering, then NRW is an omega-r.e. set but not an n-r.e. set for any natural number n.