{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T14:15:25Z","timestamp":1674483325829},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["R252-000-420-112"]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["0652669, 0901020, CNS-0435060, CCR-0325197, and EN-CS-0329609"]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME 1806\/3-1"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0652669, 0901020, CNS-0435060, CCR-0325197, and EN-CS-0329609"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2012,8]]},"abstract":"\n We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or\n left-r.e.<\/jats:italic>\n sets. In addition to pinpointing the complexity of left-r.e. Martin-L\u00f6f, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-L\u00f6f randoms and Kurtz nonrandoms) have left-r.e. numberings, there is no canonical, or\n acceptable<\/jats:italic>\n , left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.\n <\/jats:p>","DOI":"10.1145\/2287718.2287724","type":"journal-article","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T13:09:44Z","timestamp":1346159384000},"page":"1-18","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Arithmetic complexity via effective names for random sequences"],"prefix":"10.1145","volume":"13","author":[{"given":"Bj\u00f8rn","family":"Kjos-Hanssen","sequence":"first","affiliation":[{"name":"University of Hawai\u2018i at M\u0101noa"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Jason","family":"Teutsch","sequence":"additional","affiliation":[{"name":"Ruprecht-Karls-Universit\u00e4t Heidelberg"}]}],"member":"320","published-online":{"date-parts":[[2012,8,28]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"9","article-title":"Some generalizations of a fixed-point theorem","volume":"5","author":"Arslanov M. M.","year":"1981","unstructured":"Arslanov , M. M. 1981 . Some generalizations of a fixed-point theorem . Izv. Vyssh. Uchebn. Zaved. Mat. 5 , 9 -- 16 . Arslanov, M. M. 1981. Some generalizations of a fixed-point theorem. Izv. Vyssh. Uchebn. Zaved. Mat. 5, 9--16.","journal-title":"Izv. Vyssh. Uchebn. Zaved. Mat."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1876420.1876427"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03073-4_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(87)90010-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1082418542"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.055"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Hirschfeldt D. R. 2010. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer. Downey R. G. and Hirschfeldt D. R. 2010. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964290"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227839.1227845"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Jain S. Stephan F. and \n Teutsch J\n . \n 2011\n . Closed left-r.e. sets. In Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC '11). M. Ogihara and J. Tarui Eds. Lecture Notes in Computer Science Series vol. \n 6648 Springer 218--229. Jain S. Stephan F. and Teutsch J. 2011. Closed left-r.e. sets. In Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC '11). M. Ogihara and J. Tarui Eds. Lecture Notes in Computer Science Series vol. 6648 Springer 218--229.","DOI":"10.1007\/978-3-642-20877-5_23"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200041104"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_11"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05306-7"},{"key":"e_1_2_1_14_1","volume-title":"Recursion theory week (Oberwolfach","author":"Ku\u010dera A.","year":"1984","unstructured":"Ku\u010dera , A. 1985. Measure , \u03a001-classes and complete extensions of PA . In Recursion theory week (Oberwolfach , 1984 ). Lecture Notes in Math. Series, vol. 1141 , Springer , Berlin, 245--259. Ku\u010dera, A. 1985. Measure, \u03a001-classes and complete extensions of PA. In Recursion theory week (Oberwolfach, 1984). Lecture Notes in Math. Series, vol. 1141, Springer, Berlin, 245--259."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90141-4"},{"key":"e_1_2_1_17_1","first-page":"206","article-title":"Laws of information conservation (nongrowth) and aspects of the foundation of probability theory","volume":"10","author":"Levin L. A.","year":"1974","unstructured":"Levin , L. A. 1974 . Laws of information conservation (nongrowth) and aspects of the foundation of probability theory . Prob. Inf. Transm. 10 , 3, 206 -- 210 . Levin, L. A. 1974. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Prob. Inf. Transm. 10, 3, 206--210.","journal-title":"Prob. Inf. Transm."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vit\u00e1nyi P. 2008. An Introduction to Kolmogorov Complexity and Its Applications 3rd Ed. Texts in Computer Science Springer. Li M. and Vit\u00e1nyi P. 2008. An Introduction to Kolmogorov Complexity and Its Applications 3rd Ed. Texts in Computer Science Springer.","DOI":"10.1007\/978-0-387-49820-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_20_1","volume-title":"Oxford University Press","author":"Nies A.","unstructured":"Nies , A. 2009. Computability and Randomness. Oxford University Press , Oxford, UK . Nies, A. 2009. Computability and Randomness. Oxford University Press, Oxford, UK."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1120224726"},{"key":"e_1_2_1_22_1","volume-title":"Classical Recursion Theory","author":"Odifreddi P. G.","unstructured":"Odifreddi , P. G. 1999. Classical Recursion Theory . Vol. II ., Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co. , Amsterdam. Odifreddi, P. G. 1999. Classical Recursion Theory. Vol. II., Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964292"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694181"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Mathematics","volume-title":"Zuf\u00e4lligkeit und Wahrscheinlichkeit. Eine algorithmische Begr\u00fcndung der Wahrscheinlichkeitstheorie","author":"Schnorr C.-P.","unstructured":"Schnorr , C.-P. 1971b. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Eine algorithmische Begr\u00fcndung der Wahrscheinlichkeitstheorie . Lecture Notes in Mathematics , Vol. 218 , Springer . Schnorr, C.-P. 1971b. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Eine algorithmische Begr\u00fcndung der Wahrscheinlichkeitstheorie. Lecture Notes in Mathematics, Vol. 218, Springer."},{"key":"e_1_2_1_27_1","volume-title":"Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic","author":"Soare R. I.","unstructured":"Soare , R. I. 1987. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic , Springer . Soare, R. I. 1987. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Springer."},{"key":"e_1_2_1_28_1","unstructured":"Stephan F. and Teutsch J. Things that can be made into themselves. Manuscript. http:\/\/arxiv.org\/abs\/1208.0682 Stephan F. and Teutsch J. Things that can be made into themselves. Manuscript. http:\/\/arxiv.org\/abs\/1208.0682"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2287718.2287724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T09:19:05Z","timestamp":1672391945000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2287718.2287724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2287718.2287724"],"URL":"http:\/\/dx.doi.org\/10.1145\/2287718.2287724","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":["Computational Mathematics","Logic","General Computer Science","Theoretical Computer Science"],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2010-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}