×

zbMATH — the first resource for mathematics

Low upper bounds in the LR degrees. (English) Zbl 1247.03073
Summary: We say that \(A\leq _{\mathrm {LR}} B\) if every \(B\)-random real is \(A\)-random – in other words, if \(B\) has at least as much derandomization power as \(A\). The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to \(\mathbf {0^{\prime}}\).

MSC:
03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barmpalias, G., Elementary differences between the degrees of unsolvability and the degrees of compressibility, Ann. pure appl. logic, 161, 923-934, (2010) · Zbl 1227.03054
[2] Barmpalias, G.; Lewis, A., Chaitin’s halting probability and the compression of strings using oracles, Proc. R. soc., 467, 2912-2926, (2011) · Zbl 1319.03051
[3] Barmpalias, G.; Lewis, A.; Ng, K.M., The importance of \(\Pi_1^0\) classes in effective randomness, J. symbolic logic, 75, 387-400, (2010) · Zbl 1184.03039
[4] Barmpalias, G.; Lewis, A.; Stephan, F., \(\Pi_0^1\) classes, LR degrees and Turing degrees, Ann. pure appl. logic, 156, 21-38, (2008) · Zbl 1156.03040
[5] Barmpalias, G.; Lewis, A.; Soskova, M., Randomness, lowness and degrees, J. symbolic logic, 73, 559-577, (2008) · Zbl 1145.03020
[6] Kjos-Hanssen, B., Low for random reals and positive measure domination, Proc. amer. math. soc., 135, 3703-3709, (2007) · Zbl 1128.03031
[7] Kjos-Hanssen, B.; Miller, J.; Solomon, R., Lowness notions, measure, and domination, J. symbolic logic, 74, 517-534, (2009)
[8] Miller, Joseph, The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets, Notre dame J. form. log., 50, 381-391, (2010) · Zbl 1213.03053
[9] Nies, André, Lowness properties and randomness, Adv. math., 197, 274-305, (2005) · Zbl 1141.03017
[10] Nies, André, Computability and randomness, (2009), Oxford University Press Oxford · Zbl 1169.03034
[11] Simpson, Stephen G., Almost everywhere domination and superhighness, Math. log. Q., 53, 462-482, (2007) · Zbl 1123.03040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.