Geodesic
Coherent randomness tests and computing the $K$-trivial sets
Journal of the European Mathematical Society, Tome 18 (2016) no. 4, pp. 773-812

Voir la notice de l'article provenant de la source EMS Press

We introduce Oberwolfach randomness, a notion within Demuth's framework of statistical tests with moving components; here the components' movement has to be coherent across levels. We show that a ML-random set computes all K-trivial sets if and only if it is not Oberwolfach random, and indeed that there is a K-trivial set which is not computable from any Oberwolfach random set. We show that Oberwolfach random sets satisfy effective versions of almost-everywhere theorems of analysis, such as the Lebesgue density theorem and Doob's martingale convergence theorem. We also show that random sets which are not Oberwolfach random satisfy highness properties (such as LR-hardness) which mean they are close to computing the halting problem.
DOI : 10.4171/jems/602
Classification : 03-XX, 00-XX
Keywords: Coherent randomness tests, K-trivial sets 
@article{JEMS_2016_18_4_a2,
     author = {Laurent Bienvenu and Noam Greenberg and Anton{\'\i}n Ku\v{c}era and Andr\'e Nies and Dan Turetsky},
     title = {Coherent randomness tests and computing the $K$-trivial sets},
     journal = {Journal of the European Mathematical Society},
     pages = {773--812},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2016},
     doi = {10.4171/jems/602},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/jems/602/}
}
TY  - JOUR
AU  - Laurent Bienvenu
AU  - Noam Greenberg
AU  - Antonín Kučera
AU  - André Nies
AU  - Dan Turetsky
TI  - Coherent randomness tests and computing the $K$-trivial sets
JO  - Journal of the European Mathematical Society
PY  - 2016
SP  - 773
EP  - 812
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4171/jems/602/
DO  - 10.4171/jems/602
ID  - JEMS_2016_18_4_a2
ER  - 
%0 Journal Article
%A Laurent Bienvenu
%A Noam Greenberg
%A Antonín Kučera
%A André Nies
%A Dan Turetsky
%T Coherent randomness tests and computing the $K$-trivial sets
%J Journal of the European Mathematical Society
%D 2016
%P 773-812
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4171/jems/602/
%R 10.4171/jems/602
%F JEMS_2016_18_4_a2
Laurent Bienvenu; Noam Greenberg; Antonín Kučera; André Nies; Dan Turetsky. Coherent randomness tests and computing the $K$-trivial sets. Journal of the European Mathematical Society, Tome 18 (2016) no. 4, pp. 773-812. doi: 10.4171/jems/602

Cité par Sources :