K-trivial set

In the context of computability theory, a cost function is a computable function

${\displaystyle c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}.}$

For a computable approximation ${\displaystyle \langle A_{s}\rangle }$ of ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \Delta _{2}^{0}}$ set A obeys a cost function c if there exists a computable approximation of A, ${\displaystyle \langle A_{s}:s\in \omega \rangle }$ ${\displaystyle 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

${\displaystyle c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}}$ where ${\displaystyle K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}}$

and ${\displaystyle \mathbb {U} _{s}}$ is the s-th step in a computable approximation of a fixed universal prefix-free machine ${\displaystyle \mathbb {U} }$.

In fact the set can be made promptly simple. The idea is to meet the prompt simplicity requirements,

${\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}]}$

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

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

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

${\displaystyle \Sigma _{e}2^{-e}<\infty .}$

Secondly, each requirement is met: if ${\displaystyle 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.

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]

We say that A is low for K if there is b ∈ ${\displaystyle \mathbb {N} }$ such that

${\displaystyle \forall nK^{A}(n)+b\geq K(n).}$

Here ${\displaystyle K^{A}}$ is prefix-free Kolmogorov complexity relative to oracle ${\displaystyle A}$.

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.

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

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