z-logo
open-access-imgOpen Access
Schnorr Trivial Reals: A construction
Author(s) -
Johan. Y. Franklin
Publication year - 2007
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2006.08.008
Subject(s) - mathematics , randomness , discrete mathematics , set (abstract data type) , turing , computer science , theoretical computer science , programming language , statistics
A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null Σ10 (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 [11] that all K-trivial reals are low. In this paper, we prove that if h is a high degree, then every degree a⩾Th 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom