Randomness and reducibility Export

@article{citeulike:565313, abstract = {We study reducibilities that act as measures of relative randomness on reals, concentrating particularly on their behavior on the computably enumerable reals. One such reducibility, called domination or Solovay reducibility, has already proved to be a powerful tool in the study of randomness of effectively presented reals. Motivated by certain shortcomings of Solovay reducibility, we introduce two new measures of relative randomness and investigate their properties and the relationships between them and Solovay reducibility.}, author = {Downey, Rod G. and Hirschfeldt, Denis R. and Laforte, Geoff}, citeulike-article-id = {565313}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.jcss.2003.07.004}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WJ0-49W6P3F-1/2/7904f0c10d67221f6d817078a019597c}, doi = {10.1016/j.jcss.2003.07.004}, journal = {Journal of Computer and System Sciences}, keywords = {algorithmic\_information\_theory, computably\_enumerable\_reals, kolmogorov\_complexity, relative\_randomness, solovay\_reducibility}, month = {February}, number = {1}, pages = {96--114}, posted-at = {2006-03-27 11:25:41}, priority = {0}, title = {Randomness and reducibility}, url = {http://dx.doi.org/10.1016/j.jcss.2003.07.004}, volume = {68}, year = {2004} }

TY - JOUR ID - citeulike:565313 L3 - citeulike-article-id:565313 N2 - We study reducibilities that act as measures of relative randomness on reals, concentrating particularly on their behavior on the computably enumerable reals. One such reducibility, called domination or Solovay reducibility, has already proved to be a powerful tool in the study of randomness of effectively presented reals. Motivated by certain shortcomings of Solovay reducibility, we introduce two new measures of relative randomness and investigate their properties and the relationships between them and Solovay reducibility. IS - 1 JF - Journal of Computer and System Sciences EP - 114 TI - Randomness and reducibility VL - 68 SP - 96 KW - algorithmic_information_theory KW - computably_enumerable_reals KW - kolmogorov_complexity KW - relative_randomness KW - solovay_reducibility AU - Downey, Rod AU - Hirschfeldt, Denis AU - Laforte, Geoff PY - 2004/02// UR - http://dx.doi.org/10.1016/j.jcss.2003.07.004 ER -