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