Demuth randomness and computational complexity

Demuth tests generalize Martin-Löf tests ( G m ) m ∈ N in that one can exchange the m -th component a computably bounded number of times. A set Z ⊆ N fails a Demuth test if Z is in infinitely many final versions of the G m . If we only allow Demuth tests such that G m ⊇ G m + 1 for each m , we have weak Demuth randomness. w that a weakly Demuth random set can be high and Δ 2 0 , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly jump-traceable. o prove a basis theorem for non-empty Π 1 0 classes P . It extends the Jockusch–Soare basis theorem that some member of P is computably dominated. We use the result to show that some weakly 2-random set does not compute a 2-fixed point free function.