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 ∈ formula_1 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 ∈formula_1 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 formula_5 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 formula_7 of formula_5 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 formula_5 set being built. A cost function construction of a K-trivial computably enumerable noncomputable set first appeared in Downey et al. We  say a formula_5 set "A" obeys a cost function "c" if there exists a computable approximation of A, formula_11 formula_12 where formula_13 and formula_14 is the "s"-th step in a computable approximation of a fixed universal prefix-free machine formula_15. 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 formula_18 to meet the promptly simple requirements. We define a computable enumeration formula_19 such that formula_20. At stage "s"> 0 , for each "e" < "s", if formula_21 has not been met yet and there exists "x" ≥ 2"e" such that formula_22 and formula_23, then we put "x" into formula_24 and declare that formula_21 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 formula_27 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" ∈ formula_1 such that Here  formula_30 is prefix-free Kolmogorov complexity relative to oracle formula_31. 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: 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: