# Wikipedia talk:Articles for creation/K-trivial sets

Jump to navigation Jump to search

In mathematics, a set of natural numbers is called K-trivial 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 ∈ ℕ 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 ∈ℕ 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..

K-trivial sets are characterized by obedience to the Standard cost function, defined by

$c_{K}(x,s)=\Sigma _{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

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 ∈ℕ such that

$\forall nK^{A}(n)+b\geq K(n)$ .
##### Lowness for Martin-Löf-randomness

Ais 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 (notice here no randomness is mentioned).

### Developments after 2008

Since 2009 an intrusion of concepts from analysis took place, which 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 (2012)  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 (2012) 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.