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 ∈ ℕ if

$\forall n K(A\upharpoonright n)\leq K(n)+b$.

A set is K-trivial if it is K-trivial via some constant.^[1][2]

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 ^[3] mainly studied sets such that there exists b ∈ℕ with

$\forall n C(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 ^[4] 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.^[5] 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.^[6]

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^[7] 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. ^[7]

Lowness for K

We say that A is low for K if there is b ∈ ℕ such that

$\forall n K^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^[8] 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.

^[7]

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

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 ^[9] showed that a ML-random is Turing incomplete iff it is a positive density point. Day and Miller (2012) ^[10] used this for an affirmative answer to the ML-cupping problem:^[11] 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.^[12] 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.^[13] For a summary see L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies, and D. Turetsky ^[14] 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.

References

1. A. Nies (2009). Computability and Randomness, Oxford Science Publications, ISBN 978-0199230761
2. Downey, Rodney G., Hirschfeldt, Denis R. (2010), "Algorithmic Randomness and Complexity", ISBN 978-0-387-68441-3
3. Gregory J. Chaitin (1976), "Information-Theoretic Characterizations of Recursive Infinite Strings", Theoretical Computer Science Volume 2, Issue 1, June 1976, Pages 45–48
4. Cristian Calude, Richard J. Coles, Program-Size Complexity of Initial Segments and Domination Reducibility, (1999), proceeding of: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa
5. Antonin Kučera and Sebastiaan A. Terwijn (1999), "Lowness for the Class of Random Sets", The Journal of Symbolic Logic Vol. 64, No. 4 (Dec., 1999), pp. 1396–1402
6. Rod G. Downey, Denis R. Hirschfeldt, Andr ́e Nies, Frank Stephan, "Trivial Reals", Electronic Notes in Theoretical Computer Science 66 No. 1 (2002), URL: http://www.elsevier.nl/locate/entcs/volume66.html
7. André Nies, (2005), "Lowness properties and randomness", Advances in Mathematics, Volume 197, Issue 1, 20 October 2005, Pages 274–305
8. Antonin Kučera and Sebastiaan A. Terwijn (1999), "Lowness for the Class of Random Sets", The Journal of Symbolic Logic, Vol. 64, No. 4 (Dec., 1999), pp. 1396–1402
9. Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies, (2012), "The Denjoy alternative for computable functions", Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics, pages 543–554. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.
10. J. Miller, A. Day. (2012) "Cupping with random sets", To appear in the Proceedings of the American Mathematical Society
11. Miller and Nies, Randomness and computability: Open questions. Bull. Symb. Logic. 12 no 3 (2006) 390-410
12. Bienvenu, Greenberg, Kucera, Nies and Turetsky, "K-Triviality, Oberwolfach Randomness, and Differentiability", Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach Preprints (OWP), ISSN 1864-7596
13. Miller and Nies, Randomness and computability: Open questions. Bull. Symb. Logic. 12 no 3 (2006) 390–410
14. Computing K-trivial sets by incomplete random sets. Bull. Symbolic Logic. 20, March 2014, pp 80-90.