Demuth randomness and computational complexity (Q639659): Difference between revisions

Demuth tests are a generalization of Martin-Löf tests \(\{G_m\}_{m\in \omega}\) so that one can exchange the \(m\)-th component a computably bounded number of times. A set \(Z\subseteq \omega\) fails a Demuth test if \(Z\) is in infinitely many final versions of the \(G_m\). One has weak Demuth randomness if \(G_m\supseteq G_{m+1}\) for each \(m\). It is shown that, different from weak-2-randomness, which is a well-known randomness notion stronger than Martin-Löf randomness, each \(\Pi^0_1\) class of positive measure contains a weakly Demuth random set which is \(\Delta^0_2\) and high, but no weakly Demuth random set is superhigh. Moreover, any c.e. set Turing-below a Demuth random set is strongly jump-traceable.