Universality, optimality, and randomness deficiency

Rupert Hölzl, Paul Shafer

A Martin-Löf test $\mathcal{U}$ is universal if it captures all non-Martin-Löf random sequences, and it is optimal if for every ML-test $\mathcal{V}$ there is a $c\in \omega$ such that $…