K-trivial set


In mathematics, a set of natural numbers is called a K-trivial set if its initial segments viewed as binary strings are easy to describe: the prefix-free Kolmogorov complexity is as low as possible, close to that of a computable set. Solovay proved in 1975 that a set can be K-trivial without being computable.
The Schnorr–Levin theorem says that random sets have a high initial segment complexity. Thus the K-trivials are far from random. This is why these sets are studied in the field of algorithmic randomness, which is a subfield of Computability theory and related to algorithmic information theory in computer science.
At the same time, K-trivial sets are close to computable. For instance, they are all superlow, i.e. sets whose Turing jump is computable from the Halting problem, and form a Turing ideal, i.e. class of sets closed under Turing join and closed downward under Turing reduction.

Definition

Let K be the prefix-free Kolmogorov Complexity, i.e. given a string x, K outputs the least length of the input string under a prefix-free universal machine. Such a machine, intuitively, represents a universal programming language with the property that no valid program can be obtained as a proper extension of another valid program. For more background of K, see e.g. Chaitin's constant.
We say a set A of the natural numbers is K-trivial via a constant b ∈ ℕ if
A set is K-trivial if it is K-trivial via some constant.

Brief history and development

In the early days of the development of K-triviality, attention was paid to separation of K-trivial sets and computable sets.
Chaitin in his 1976 paper mainly studied sets such that there exists b ∈ℕ with
where C denotes the plain Kolmogorov complexity. These sets are known as C-trivial sets. Chaitin showed they coincide with the computable sets. He also showed that the K-trivials are computable in the halting problem. This class of sets is commonly known as sets in arithmetical hierarchy.
Robert M. Solovay was the first to construct a noncomputable K-trivial set, while construction of a computably enumerable such A was attempted by Calude, Coles and other unpublished constructions by Kummer of a K-trivial, and Muchnik junior of a low for K set.

Developments 1999–2008

In the context of computability theory, a cost function is a computable function
For a computable approximation of set A, such a function measures the cost c of changing the approximation to A at stage s. The first cost function construction was due to Kučera and Terwijn. They built a computably enumerable set that is low for Martin-Löf-randomness but not computable. Their cost function was adaptive, in that the definition of the cost function depends on the computable approximation of the set being built.
A cost function construction of a K-trivial computably enumerable noncomputable set first appeared in Downey et al.
We say a set A obeys a cost function c if there exists a computable approximation of A,
K-trivial sets are characterized by obedience to the Standard cost function, defined by
and is the s-th step in a computable approximation of a fixed universal prefix-free machine.

Sketch of the construction of a non-computable K-trivial set

In fact the set can be made promptly simple. The idea is to meet the prompt simplicity requirements,
as well as to keep the costs low. We need the cost function to satisfy the limit condition
namely the supremum over stages of the cost for x goes to 0 as x increases. For instance, the standard cost function has this property. The construction essentially waits until the cost is low before putting numbers into to meet the promptly simple requirements. We define a computable enumeration such that
. At stage s> 0 , for each e < s, if has not been met yet and there exists x ≥ 2e such that and, then we put x into and declare that is met. End of construction.
To verify that the construction works, note first that A obeys the cost function since at most one number enters A for the sake of each requirement. The sum S is therefore at most
Secondly, each requirement is met: if is infinite, by the fact that the cost function satisfies the limit condition, some number will eventually be enumerated into A to meet the requirement.

Equivalent characterizations

K-triviality turns out to coincide with some computational lowness notions, saying that a set is close to computable. The following notions capture the same class of sets.
Lowness for ''K''
We say that A is low for K if there is b ∈ ℕ such that
Here is prefix-free Kolmogorov complexity relative to oracle.
Lowness for Martin-Löf-randomness
A is low for Martin-Löf-randomness if whenever Z is Martin-Löf random, it is already Martin-Löf random relative to A.
Base for Martin-Löf-randomness
A is a base for Martin-Löf-randomness if A is Turing reducible to Z for some set Z that is Martin-Löf random relative to A.
More equivalent characterizations of K-triviality have been studied, such as:
  1. Lowness for weakly-2-randomness;
  2. Lowness for difference-left-c.e. reals.

    Developments after 2008

From 2009 on, concepts from analysis entered the stage. This helped solving some notorious problems.
One says that a set Y is a positive density point if every effectively closed class containing Y has positive lower Lebesgue density at Y. Bienvenu, Hölzl, Miller, and Nies showed that a ML-random is Turing incomplete iff it is a positive density point. Day and Miller used this for an affirmative answer to the ML-cupping problem: A is K-trivial iff for every Martin-Löf random set Z such that A⊕Z compute the halting problem, already Z by itself computes the halting problem.
One says that a set Y is a density-one point if every effectively closed class containing Y has Lebesgue density 1 at Y. Any Martin-Löf random set that is not a density-one point computes every K trivial set by Bienvenu, et al. Day and Miller showed that there is Martin-Löf random set which is a positive density point but not a density one point. Thus there is an incomplete such Martin-Löf random set which computes every K-trivial set. This affirmatively answered the covering problem first asked by Stephan and then published by Miller and Nies. For a summary see L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies, and D. Turetsky
Variants of K-triviality have been studied: