Trivial Reals Export

@article{citeulike:565316, abstract = {Solovay showed that there are noncomputable reals [alpha] such that H([alpha] || n) H(1n)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of \“highly nonrandom\” reals that have been previously studied.}, author = {Downey, Rod G. and Hirschfeldt, Denis R. and Nies, Andre and Stephan, Frank}, booktitle = {CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop)}, citeulike-article-id = {565316}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S1571-0661(04)80377-3}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B75H1-4DD86JV-27/2/778cc53bd2d17f04facf853041948c41}, doi = {10.1016/S1571-0661(04)80377-3}, journal = {Electronic Notes in Theoretical Computer Science}, keywords = {computably\_enumerable\_reals, kolmogorov\_complexity}, month = {July}, number = {1}, pages = {1--17}, posted-at = {2006-03-27 11:29:34}, priority = {0}, title = {Trivial Reals}, url = {http://dx.doi.org/10.1016/S1571-0661(04)80377-3}, volume = {66}, year = {2002} }

TY - JOUR ID - citeulike:565316 L3 - citeulike-article-id:565316 N2 - Solovay showed that there are noncomputable reals [alpha] such that H([alpha] || n) H(1n)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of “highly nonrandom” reals that have been previously studied. IS - 1 JF - Electronic Notes in Theoretical Computer Science EP - 17 TI - Trivial Reals VL - 66 T2 - CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop) SP - 1 KW - computably_enumerable_reals KW - kolmogorov_complexity AU - Downey, Rod AU - Hirschfeldt, Denis AU - Nies, Andre AU - Stephan, Frank PY - 2002/07// UR - http://dx.doi.org/10.1016/S1571-0661(04)80377-3 ER -