Randomness, lowness and degrees. (English) Zbl 1145.03020

Summary: We say that \(A\leq _{LR}B\) if every \(B\)-random number is \(A\)-random. Intuitively this means that if oracle \(A\) can identify some patterns on some real \(\gamma \), oracle \(B\) can also find patterns on \(\gamma \). In other words, \(B\) is at least as good as \(A\) for this purpose. We study the structure of the \(LR\) degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever \(\alpha \) is not \(GL_{2}\) the \(LR\) degree of \(\alpha \) bounds \(2^{\aleph _{0}}\) degrees (so that, in particular, there exist \(LR\) degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. \(LR\) degrees.


03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
03D28 Other Turing degree structures
Full Text: DOI Link


[1] Lowness for the class of random sets 64 pp 1396– (1999) · Zbl 0954.68080
[2] Degrees of Unsolvahility: Local and Global Theory (1983)
[3] Rossiskaya Akademiya Nauk 192 pp 1224– (1970)
[4] Recursively Eumerable Sets and Degrees (1987)
[5] DOI: 10.1002/malq.200710012 · Zbl 1123.03040
[6] DOI: 10.1090/S0002-9939-07-08648-0 · Zbl 1128.03031
[7] DOI: 10.4153/CJM-1977-105-5 · Zbl 0355.02032
[8] Recursive Function Theory Newsletter (1976)
[9] Algebra i Logika 7 pp 47– (1968)
[10] Algorithmic Randomness and Complexity (2008)
[11] Almost everywhere domination 69 pp 914– (2004)
[12] Computability Theory (2004) · Zbl 1041.03001
[13] DOI: 10.1016/j.entcs.2006.08.005 · Zbl 1262.03062
[14] Working below a high recursively enumerable degree 58 pp 824– (1993)
[15] Degrees of Unsolvability (1963) · Zbl 0143.25302
[16] Classical Recursion Theory II (1999) · Zbl 0931.03057
[17] DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017
[18] DOI: 10.1007/BFb0076224
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.