Computably enumerable sets below random sets (Q450954): Difference between revisions

Intuitively, randomness of a set means, in particular, that there is no algorithmic way to generate this set, while computable enumerability (c.e.) means that the set is generated by an algorithm. Since these two notions are opposite, it may seem reasonable to expect that the only c.e.~sets Turing below a random set are computable ones. This expectation is not literally true for most algorithmic definitions of randomness. However, the author proves several interesting results in the spirit of this expectation, results proving that c.e.~sets Turing below a random set are usually low in the Turing-reduction hierarchy. For example, he proves that each \(\omega^2\)-computably approximable Martin-Löf random set is \(\omega\)-traceable; this lowness property is one of the indications that this set is very weak as an oracle. Even stronger results are proven for Demuth randomness -- a known strengthening of Martin-Löf randomness.