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.
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.
We say a set A of the natural numbers is K-trivial via a constant b ∈
Chaitin in his 1976 paper [3] mainly studied sets such that there exists b ∈
Chaitin showed they coincide with the computable sets.
He also showed that the K-trivials are computable in the halting problem.
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 [4] and other unpublished constructions by Kummer of a K-trivial, and Muchnik junior of a low for K set.
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.
A cost function construction of a K-trivial computably enumerable noncomputable set first appeared in Downey et al.[6] We say a
set A obeys a cost function c if there exists a computable approximation of A,
K-trivial sets are characterized[7] by obedience to the Standard cost function, defined by and
is the s-th step in a computable approximation of a fixed universal prefix-free machine
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.
The construction essentially waits until the cost is low before putting numbers into
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.
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.
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: From 2009 on, concepts from analysis entered the stage.
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.
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.
This affirmatively answered the covering problem first asked by Stephan and then published by Miller and Nies.