Schnorr trivial reals: a construction |
| |
Authors: | Johanna N Y Franklin |
| |
Institution: | (1) Department of Mathematics, National University of Singapore, 2, Science Drive 2, Singapore, 117543, Singapore |
| |
Abstract: | A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing
reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305,
2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength,
it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees.
This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in
the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science |
| |
Keywords: | Randomness Triviality Schnorr trivial |
本文献已被 SpringerLink 等数据库收录! |
|