skip to content

Demuth randomness and its variants

Monday 2nd July 2012 - 11:00 to 12:00
INI Seminar Room 1
A Demuth test is like a Martin-Löf test with the passing condition to be out of infinitely many components; the strength of the test is enhanced by the possibility to exchange the $n$-th component of the test a computably bounded number of times. Demuth introduced Demuth randomness of reals in 1982, and showed that the Denjoy alternative for Markov computable functions holds at any such real. In [1] we proved that Demuth's hypothesis is in fact too strong: difference randomness (i.e., ML-randomness together with incompleteness) of the real already suffices. However, Demuth randomness now plays an important role in the interaction of computability and randomness. The basic relevant fact here is that a Demuth random set can be below the halting problem.

In [2] we characterized lowness for Demuth randomness by a property called BLR-traceability, in conjunction with being computably dominated. The low for Demuth random sets form a proper subclass of the computably traceable sets used by Terwijn and Zambella to characterize lowness for Schnorr randomness.

The covering problem asks whether each K-trivial set $A$ is Turing below a difference random set $Y$. Combining work of Kucera and Nies [3] with results of Downey, Diamondstone, Greenberg and Turetsky gives an affirmative answer to an analogous question: a set $A$ is strongly jump traceable if and only if it is below a Demuth random set $Y$.

In recent work, Bienvenu, Greenberg, Kucera, Nies, and Turetsky introduced a weakening of Demuth randomness called Oberwolfach randomness. They used it to build a ``smart'' K-trivial set $A$: it is difficult to cover in that any Martin-Löf random set $Y$ above $A$ must be LR-hard.

[2] Bienvenu, Downey, Greenberg, Nies, and Turetsky. "Characterizing lowness for Demuth Randomness." Submitted.

[1] Bienvenu, Hoelzl, Miller, and Nies. "The Denjoy alternative for computable functions." Proceedings of STACS 2012.

[3] Kucera, A. and Nies, A. Demuth. "randomness and computational complexity." Annals of Pure and Applied Logic 162 (2011) 504–513.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons