# 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(x) 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 ∈ $\mathbb {N}$ if
    $\forall nK(A\upharpoonright n)\leq K(n)+b$.
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 ∈$\mathbb {N}$ with
    $\forall nC(A\upharpoonright n)\leq C(n)+b$
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 $\Delta _{2}^{0}$ 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
    $c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}.$
For a computable approximation $\langle A_{s}\rangle$ of $\Delta _{2}^{0}$ set A, such a function measures the cost c(n,s) of changing the approximation to A(n) 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 $\Delta _{2}^{0}$ set being built.
A cost function construction of a K-trivial computably enumerable noncomputable set first appeared in Downey et al.
We say a $\Delta _{2}^{0}$ set A obeys a cost function c if there exists a computable approximation of A, $\langle A_{s}:s\in \omega \rangle$ $S=\Sigma _{x,s}c(x,s)[x<s\wedge {\text{x is the least s.t. }}A_{s-1}(x)\neq A_{s}(x)]<\infty .$
K-trivial sets are characterized by obedience to the Standard cost function, defined by
    $c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}$ where $K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}$
and $\mathbb {U} _{s}$ is the s-th step in a computable approximation of a fixed universal prefix-free machine $\mathbb {U}$.

#### 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,
    $PS_{e}:|W_{e}|=\infty \Rightarrow \exists s\exists x[x\in W_{e,s}\backslash W_{e,s-1}\wedge x\in A_{s}]$
as well as to keep the costs low. We need the cost function to satisfy the limit condition
    $\lim _{x}\sup _{s>x}c(x,s)=0$
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 $A$ to meet the promptly simple requirements. We define a computable enumeration $\langle A_{s}:s\in \omega \rangle$ such that
$A_{0}=\emptyset$. At stage s> 0 , for each e < s, if $PS_{e}$ has not been met yet and there exists x ≥ 2e such that $x\in W_{e,s}\backslash W_{e,s-1}$ and $c(x,s)\leq 2^{-e}$, then we put x into $A_{s}$ and declare that $PS_{e}$ 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
    $\Sigma _{e}2^{-e}<\infty .$
Secondly, each requirement is met: if $W_{e}$ 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 ∈ $\mathbb {N}$ such that
    $\forall nK^{A}(n)+b\geq K(n).$
Here $K^{A}$ is prefix-free Kolmogorov complexity relative to oracle $A$.

##### 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:
* Lowness for weakly-2-randomness;
* Lowness for difference-left-c.e. reals (notice here no randomness is mentioned).

### 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:
* Schnorr trivial sets where the machines have domain with computable measure.
* strongly jump traceable sets, a lowness property of sets far inside K-triviality.