Michael Deveau, Department of Pure Mathematics, University of Waterloo
“Relative Randomness and van Lambalgen’s Theorem”
Abstract
Now that we have seen some of the basic results about ML-randomness, we generalize them to allow sets to be random with respect to other sets. After a brief discussion of relativization as applied to randomness, we present the main result of this section, van Lambalgen’s theorem, which allows us to relate the randomness of a set to its computational power.
MC 5403