zbMATH — the first resource for mathematics

Coherent randomness tests and computing the \(K\)-trivial sets. (English) Zbl 1375.03049
The authors introduce a new type of algorithmic randonmness called “Oberwolfach randomness”, inspired by Demuth’s statistical tests of randomness. They prove that Oberwolfach random sets satisatisfy effective versions of almost everywhere theorems in analysis such as the Lebesgue density theorem and Doob’s martingale convergence theorem. These results show that a Martin-Löf random set which fails the effective Lebesgue density theorem for closed set has to compute all \(K\)-trivial sets and can be used to give a positive answer to the Martin-Löf covering problem and negative answers for stronger forms of the covering problem.

03D32 Algorithmic randomness and dimension
03D25 Recursively (computably) enumerable sets and degrees
Full Text: DOI