Effective randomness, strong reductions and Demuth's theorem

Details Effective randomness, strong reductions and Demuth's theorem Effective randomness, strong reductions and Demuth's theorem

2011-10-09

arxiv.org/abs/1110.1860v2

Mathematics

Logic

Submitted to Theoretical Computer Science

Scientific paper

We study generalizations of Demuth's Theorem, which states that the image of a Martin-L\"of random real under a tt-reduction is either computable or Turing equivalent to a Martin-L\"of random real. We show that Demuth's Theorem holds for Schnorr randomness and computable randomness (answering a question of Franklin), but that it cannot be strengthened by replacing the Turing equivalence in the statement of the theorem with wtt-equivalence. We also provide some additional results about the Turing and tt-degrees of reals that are random with respect to some computable measure.

Affiliated with

Also associated with

No associations

Rating

Effective randomness, strong reductions and Demuth's theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Effective randomness, strong reductions and Demuth's theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Effective randomness, strong reductions and Demuth's theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88392