Lowness for Kurtz randomness. (English) Zbl 1168.03033

Greenberg, Noam; Miller, Joseph S.

J. Symb. Log. 74, No. 2, 665-678 (2009).

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.

Reviewer: Leon Harkleroad (Wilton)

MSC:

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

Keywords:

diagonally nonrecursive; svelte tree; Kurtz randomness; lowness

References:

[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