K-trivial set

Short description: Type of set in mathematics

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 ∈ [math]\displaystyle{ \mathbb{N} }[/math] if

[math]\displaystyle{ \forall n K(A\upharpoonright n)\leq K(n)+b }[/math].

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 ∈[math]\displaystyle{ \mathbb{N} }[/math] with

[math]\displaystyle{ \forall n C(A\upharpoonright n)\leq C(n)+b }[/math]

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 [math]\displaystyle{ \Delta_2^0 }[/math] 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

[math]\displaystyle{ c: \mathbb{N}\times\mathbb{N}\to \mathbb{Q}^{\geq 0}. }[/math]

For a computable approximation [math]\displaystyle{ \langle A_s \rangle }[/math] of [math]\displaystyle{ \Delta_2^0 }[/math] 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 [math]\displaystyle{ \Delta_2^0 }[/math] set being built.

A cost function construction of a K-trivial computably enumerable noncomputable set first appeared in Downey et al.

We say a [math]\displaystyle{ \Delta_2^0 }[/math] set A obeys a cost function c if there exists a computable approximation of A, [math]\displaystyle{ \langle A_s: s\in \omega\rangle }[/math] [math]\displaystyle{ S=\Sigma_{x,s} c(x,s)[x\lt s \wedge \text{x is the least s.t. }A_{s-1}(x)\neq A_s(x)] \lt \infty. }[/math]

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

[math]\displaystyle{ c_K (x,s)=\Sigma_{x \lt y\leq s} 2^{-K_s(x)} }[/math] where [math]\displaystyle{ K_s(x)=\min \{|\sigma|: \mathbb{U}_s(\sigma)=x\} }[/math]

and [math]\displaystyle{ \mathbb{U}_s }[/math] is the s-th step in a computable approximation of a fixed universal prefix-free machine [math]\displaystyle{ \mathbb{U} }[/math].

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,

[math]\displaystyle{ 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] }[/math]

as well as to keep the costs low. We need the cost function to satisfy the limit condition

[math]\displaystyle{ \lim_x \sup_{s\gt x}c(x,s)=0 }[/math]

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 [math]\displaystyle{ A }[/math] to meet the promptly simple requirements. We define a computable enumeration [math]\displaystyle{ \langle A_s: s\in\omega\rangle }[/math] such that

[math]\displaystyle{ A_0=\emptyset }[/math]. At stage s> 0 , for each e < s, if [math]\displaystyle{ PS_e }[/math] has not been met yet and there exists x ≥ 2e such that [math]\displaystyle{ x\in W_{e,s}\backslash W_{e,s-1} }[/math] and [math]\displaystyle{ c(x,s)\leq 2^{-e} }[/math], then we put x into [math]\displaystyle{ A_s }[/math] and declare that [math]\displaystyle{ PS_e }[/math] 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

[math]\displaystyle{ \Sigma_e 2^{-e} \lt \infty. }[/math]

Secondly, each requirement is met: if [math]\displaystyle{ W_e }[/math] 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 ∈ [math]\displaystyle{ \mathbb{N} }[/math] such that

[math]\displaystyle{ \forall n K^A(n)+b \geq K(n). }[/math]

Here [math]\displaystyle{ K^A }[/math] is prefix-free Kolmogorov complexity relative to oracle [math]\displaystyle{ A }[/math].

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 (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.