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. 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.
Wikipage redirect
primaryTopic
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. 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.
has abstract
In mathematics, a set of natur ...... wnward under Turing reduction.
@en
数学においてある自然数の集合がK自明集合(Kじめいしゅうごう ...... に関して閉じていて、チューリング還元に関して下に閉じている。
@ja
Wikipage page ID
41,341,441
Wikipage revision ID
733,891,800
comment
In mathematics, a set of natur ...... wnward under Turing reduction.
@en
数学においてある自然数の集合がK自明集合(Kじめいしゅうごう ...... に関して閉じていて、チューリング還元に関して下に閉じている。
@ja
label
K-trivial set
@en
K自明集合
@ja