Abstract
It is shown that a set is low for weakly 1-generic iff it has neither dnr nor hyperimmune Turing degree. As this notion is more general than being recursively traceable, this answers negatively a recent question on the characterization of these sets. Furthermore, it is shown that every set which is low for weakly 1-generic is also low for Kurtz-random.
The research of the first author is supported in part by NUS grant R-252-000-212-112. The second author is supported by postdoctoral fellowship from computability theory and algorithmic randomness R-146-000-054-123 of Singapore, NSF of China No. 10471060 and No. 10420130638.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Downey, R.G., Hirschfeldt, D.: Algorithmic randomness and complexity. Springer, Heidelberg (to appear)
Downey, R., Jockusch, C.G., Stob, M.: Array nonrecursive degrees and genericity. In: Computability, Enumerability, Unsolvability. London Mathematical Society Lecture Notes Series, vol. 224, pp. 93–104 (1996)
Downey, R.G., Griffiths, E.J., Reid, S.: On Kurtz randomness. Theoretical Computer Science 321(2-3), 249–270 (2004)
Downey, R., Hirschfeldt, D., Miller, J., Nies, A.: Relativizing Chaitin’s halting probability. Journal of Mathematical Logic 5, 167–192 (2005)
Kjos-Hanssen, B., Merkle, W., Stephan, F.: Kolmogorov Complexity and the Recursion Theorem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 149–161. Springer, Heidelberg (2006)
Kjos-Hanssen, B., Nies, A., Stephan, F.: Lowness for the class of Schnorr random reals. SIAM Journal on Computing (to appear)
Kurtz, S.: Randomness and genericity in the degrees of unsolvability. Ph.D. Dissertation. University of Illinois, Urbana (1981)
Li, M., Vitányi, P.: An introduction to Kolmogorov complexity and its applications. Texts and Monographs in Computer Science. Springer, New York (1993)
Miller, J.S., Nies, A.: Randomness and computability: Open questions. The Bulletin of Symbolic Logic (to appear)
Nies, A.: Lowness properties and randomness. Advances in Mathematics 197(1), 274–305 (2005)
Odifreddi, P.: Classical Recursion Theory. North-Holland, Amsterdam (1989)
Post, E.: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society 50, 284–316 (1944)
Soare, R.I.: Recursively enumerable sets and degrees. Springer, Heidelberg (1987)
Terwijn, S.A., Zambella, D.: Computational randomness and lowness. The Journal of Symbolic Logic 66(3), 1199–1205 (2001)
Yu, L.: Lowness for genericity. Archive for Mathematical Logic 45(2), 233–238 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stephan, F., Yu, L. (2006). Lowness for Weakly 1-generic and Kurtz-Random. In: Cai, JY., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2006. Lecture Notes in Computer Science, vol 3959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11750321_72
Download citation
DOI: https://doi.org/10.1007/11750321_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34021-8
Online ISBN: 978-3-540-34022-5
eBook Packages: Computer ScienceComputer Science (R0)