K-trivial set

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a set of natural numbers is called a K-trivial set if its <a href="/facts/Upper_set/hSyGJ2WB">initial segments</a> viewed as binary strings are easy to describe: the prefix-free <a href="/facts/Kolmogorov_complexity/L9ezq8pY">Kolmogorov complexity</a> is as low as possible, close to that of a <a href="/facts/Recursive_set/rsnT9cLn">computable set</a>. 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 <a href="/facts/Algorithmically_random_sequence/n0UTETlJ">algorithmic randomness</a>, which is a subfield of <a href="/facts/Computability_theory/cqDfXwdf">Computability theory</a> and related to <a href="/facts/Algorithmic_information_theory/Tltn3I0Y">algorithmic information theory</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>.
At the same time, K-trivial sets are close to computable. For instance, they are all superlow, i.e. sets whose <a href="/facts/Turing_jump/zcRxdWPt">Turing jump</a> is computable from the <a href="/facts/Halting_problem/Xz1bac40">Halting problem</a>, and form a Turing ideal, i.e. class of sets closed under Turing join and closed downward under <a href="/facts/Turing_reduction/qczcQTbz">Turing reduction</a>.

K-trivial set open-in-new

K-trivial set