K-trivial set
id:
k-trivial-set-300-5383743
title:
K-trivial set
text:
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 algorithm
brand slug:
wiki
category slug:
encyclopedia
description:
Type of set in mathematics
original url:
https://en.wikipedia.org/wiki/K-trivial_set
date created:
date modified:
2023-09-19T21:27:25Z
main entity:
{"identifier":"Q15958734","url":"https://www.wikidata.org/entity/Q15958734"}
image:
fields total:
13
integrity:
14