Aspects of Schnorr randomness.

摘要

We study the Turing degrees of Schnorr trivial reals. A real is said to be Schnorr trivial if its initial-segment complexity is determined by a computable Turing machine to be no greater than that of a recursive real. Nies has previously shown that the Turing degrees of K-trivial reals have a very simple characterization. In this thesis, we show that the Turing degrees of Schnorr trivial reals cannot be so neatly characterized.; We begin by relating Schnorr triviality to the Turing jump by proving that every Turing degree in the cone above a Turing degree a contains a Schnorr trivial real if and only if a' ≥ T 0". We also show that there are natural classes of Turing degrees that do not contain Schnorr trivial reals, such as the 2-generic degrees, while showing that the same cannot be said of the 1-generic degrees. Later, we show that the reals which are not Schnorr trivial are dense in the recursively enumerable sets.; We also investigate the relationship between Schnorr lowness and Schnorr triviality. Downey, Griffiths, and Laforte have shown that these notions do not coincide. We show here that Schnorr lowness implies Schnorr triviality and, in fact, that these notions are equivalent within the hyperimmune-free degrees. The hyperimmune-free Turing degrees are precisely the Turing degrees that correspond to truth-table degrees. We now believe that the Schnorr trivial reals are best analyzed in the truth-table degrees.; Finally, we prove that the Schnorr trivial reals are closed under join. Since Downey, Griffiths, and Laforte have proved that the Schnorr trivial reals are closed downward in the truth-table degrees, this is enough to show that they form an ideal in this degree structure. This ideal is fairly rich, since there is a II01 class of Schnorr trivial reals with no recursive elements, and this class must necessarily contain a perfect subset.