Lowness for Kurtz randomness. (English) Zbl 1168.03033

The main result here is that no diagonally nonrecursive (DNR) degree is low for Kurtz randomness. The authors point out that the bulk of the proof is combinatorial – the key notion introduced is that of a svelte tree – with computability appearing only towards the end. Using the same machinery, the paper also shows that every degree in Low (ML, Kurtz) is non-DNR, Kjos-Hanssen having proved the converse.


03D80 Applications of computability and recursion theory
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
03D28 Other Turing degree structures
Full Text: DOI Link


[1] DOI: 10.1016/j.tcs.2004.03.055 · Zbl 1070.68054
[2] Lowness and {\(\Pi\)}2 0 nullsets 71 pp 1044– (2006)
[3] DOI: 10.2178/bsl/1154698741 · Zbl 1113.03037
[4] DOI: 10.1007/s00153-005-0306-y · Zbl 1148.03033
[5] Computational randomness and lowness 66 pp 1199– (2001) · Zbl 0990.03033
[6] DOI: 10.1007/11750321_72
[7] DOI: 10.1137/S0097539704446323 · Zbl 1095.68043
[8] COLT ’91: Proceedings of the fourth annual workshop on Computational Learning Theory pp 379– (1991)
[9] DOI: 10.1142/S0219061307000652 · Zbl 1150.03013
[10] DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017
[11] Randomness, relativization and Turing degrees 70 pp 515– (2005) · Zbl 1090.03013
[12] Computability and randomness (2009) · Zbl 1169.03034
[13] DOI: 10.2307/1969604 · Zbl 0074.01302
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.