On Kurtz randomness Export

@article{citeulike:566308, abstract = {Kurtz randomness is a notion of algorithmic randomness for real numbers. In particular a real [alpha] is called Kurtz random (or weakly random) iff it is contained in every computably enumerable set U of (Lebesgue) measure 1. We prove a number of characterizations of this notion, relating it to other notions of randomness such as the well-known notions of computable randomness, Martin-Lof randomness and Schnorr randomness. For the first time we give machine characterizations of Kurtz randomness. Whereas the Turing degree of every Martin-Lof random c.e. real is the complete degree, and the degrees of Schnorr random c.e. reals are all high, we show that Kurtz random c.e. reals occur in every non-zero c.e. degree. Additionally, we show that the sets that are low for Kurtz randomness are all hyperimmune and include those that are low for Schnorr randomness, characterized previously by Terwijn and Zambella.}, author = {Downey, Rodney G. and Griffiths, Evan J. and Reid, Stephanie}, citeulike-article-id = {566308}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.tcs.2004.03.055}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V1G-4C477DB-4/2/d4c04fee714f7911421e0b34713025fc}, day = {16}, doi = {10.1016/j.tcs.2004.03.055}, journal = {Theoretical Computer Science}, keywords = {kolmogorov\_complexity, kurtz\_randomness, lowness, randomness}, month = {August}, number = {2-3}, pages = {249--270}, posted-at = {2006-03-27 23:31:14}, priority = {0}, title = {On Kurtz randomness}, url = {http://dx.doi.org/10.1016/j.tcs.2004.03.055}, volume = {321}, year = {2004} }

TY - JOUR ID - citeulike:566308 L3 - citeulike-article-id:566308 N2 - Kurtz randomness is a notion of algorithmic randomness for real numbers. In particular a real [alpha] is called Kurtz random (or weakly random) iff it is contained in every computably enumerable set U of (Lebesgue) measure 1. We prove a number of characterizations of this notion, relating it to other notions of randomness such as the well-known notions of computable randomness, Martin-Lof randomness and Schnorr randomness. For the first time we give machine characterizations of Kurtz randomness. Whereas the Turing degree of every Martin-Lof random c.e. real is the complete degree, and the degrees of Schnorr random c.e. reals are all high, we show that Kurtz random c.e. reals occur in every non-zero c.e. degree. Additionally, we show that the sets that are low for Kurtz randomness are all hyperimmune and include those that are low for Schnorr randomness, characterized previously by Terwijn and Zambella. IS - 2-3 JF - Theoretical Computer Science EP - 270 TI - On Kurtz randomness VL - 321 SP - 249 KW - kolmogorov_complexity KW - kurtz_randomness KW - lowness KW - randomness AU - Downey, Rodney AU - Griffiths, Evan AU - Reid, Stephanie PY - 2004/08/16/ UR - http://dx.doi.org/10.1016/j.tcs.2004.03.055 ER -