K trivial set

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

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 Δ 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

For a computable approximation ⟨ A s ⟩ of Δ 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 Δ 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 Δ 2 0 set A obeys a cost function c if there exists a computable approximation of A, ⟨ A s : s ∈ ω ⟩ S = Σ x , s c ( x , s ) [ x < s ∧ x is the least s.t.  A s − 1 ( x ) ≠ A s ( x ) ] < ∞ .

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

and U s is the s-th step in a computable approximation of a fixed universal prefix-free machine 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,

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 A to meet the promptly simple requirements. We define a computable enumeration ⟨ A s : s ∈ ω ⟩ such that

A 0 = ∅ . At stage s> 0 , for each e < s, if P S e has not been met yet and there exists x ≥ 2e such that x ∈ W e , s ∖ W e , s − 1 and c ( x , s ) ≤ 2 − e , then we put x into A s and declare that P S 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

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

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:

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: