Demuth randomness and computational complexity
2011
Demuth tests generalize Martin-Lof tests (Gm)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 Gm. If we only allow Demuth tests such that Gm⊇Gm+1 for each m, we have weak Demuth randomness.
We show that a weakly Demuth random set can be high and Δ20, yet not superhigh. Next, any c.e. set Turing below a Demuth random set is strongly jump-traceable.
We also prove a basis theorem for non-empty Π10 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
26
References
38
Citations
NaN
KQI