From Surf Wiki (app.surf) — the open knowledge base

K-trivial set

Quality 0.00 · 0 views · Updated 1 month ago

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.