Demuth randomness and computational complexity

Annals of Pure and Applied Logic 162 (7):504-513 (2011)
  Copy   BIBTEX


Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , 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 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



    Upload a copy of this work     Papers currently archived: 83,890

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Computational complexity and Godel's incompleteness theorem.Gregory J. Chaitin - 1970 - [Rio de Janeiro,: Centro Técnico Científico, Pontifícia Universidade Católica do Rio de Janeiro. Edited by Gregory J. Chaitin.
The computational complexity of logical theories.Jeanne Ferrante - 1979 - New York: Springer Verlag. Edited by Charles W. Rackoff.
Computational vs. causal complexity.Matthias Scheutz - 2001 - Minds and Machines 11 (4):543-566.


Added to PP

34 (#369,767)

6 months
1 (#503,386)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Lowness properties and approximations of the jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.

View all 8 references / Add more references