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 ∈ N {\displaystyle \mathbb {N} } if
∀ n K ( A ↾ n ) ≤ K ( n ) + b {\displaystyle \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 ∈ N {\displaystyle \mathbb {N} } with
∀ n C ( A ↾ n ) ≤ C ( n ) + b {\displaystyle \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 Δ 2 0 {\displaystyle \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 : N × N → Q ≥ 0 . {\displaystyle c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}.}
For a computable approximation ⟨ A s ⟩ {\displaystyle \langle A_{s}\rangle } of Δ 2 0 {\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. 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 {\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. We say a Δ 2 0 {\displaystyle \Delta _{2}^{0}} set A obeys a cost function c if there exists a computable approximation of A, ⟨ A s : s ∈ ω ⟩ {\displaystyle \langle A_{s}:s\in \omega \rangle }
S = Σ x , s c ( x , s ) [ x < s ∧ x is the least s.t. A s − 1 ( x ) ≠ A s ( x ) ] < ∞ . {\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 by obedience to the Standard cost function, defined by
… excerpt ends here. Continue reading the full article.
