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...

Full description

Saved in:
Bibliographic Details
Published in:Annals of pure and applied logic 2011-06, Vol.162 (7), p.504-513
Main Authors: Kučera, Antonín, Nies, André
Format: Article
Language:English
Subjects:
Computability
Demuth randomness
Lowness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. We show 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. We also 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.
ISSN:0168-0072
DOI:10.1016/j.apal.2011.01.004