Independence, relative randomness, and PA degrees
We study pairs of reals that are mutually MartinLรถf random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen's Theorem holds for noncomputable probability measures, too. We study, for a given real A, the independence spectrum of A, the set of all B so that there exists a probability measure mu so that mu{A,B} = 0 and (A,B) is (mu x mu)random. We prove that if A is c.e., then no Delta02 set is in the independence spectrum of A. We obtain applications of this fact to PA degrees. In particular, we show that if A is c.e. and P is of PA degree so that P is not recursive in A, then A + P computes the halting problem.
Files
Metadata
Work Title  Independence, relative randomness, and PA degrees 

Access  
Creators 

Keyword 

License  AttributionNonCommercialNoDerivs 3.0 United States 
Work Type  Research Paper 
Deposited  September 25, 2012 
Versions
Analytics
Collections
This resource is currently not in any collection.