{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:33:21Z","timestamp":1760121201938},"reference-count":23,"publisher":"Wiley","issue":"4-5","license":[{"start":{"date-parts":[[2004,8,18]],"date-time":"2004-08-18T00:00:00Z","timestamp":1092787200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of \u0394<jats:sup>0<\/jats:sup><jats:sub>2<\/jats:sub>\u2010sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d\u2010c. e. reals. (\u00a9 2004 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200310110","type":"journal-article","created":{"date-parts":[[2004,8,18]],"date-time":"2004-08-18T12:01:34Z","timestamp":1092830494000},"page":"431-442","source":"Crossref","is-referenced-by-count":11,"title":["Weak computability and representation of reals"],"prefix":"10.1002","volume":"50","author":[{"given":"Xizhong","family":"Zheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Rettinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2004,8,18]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2000.0561"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310103"},{"key":"e_1_2_1_4_2","unstructured":"R. G.Downey Some computability\u2010theoretical aspects of real and randomness. Preprint September 2001."},{"key":"e_1_2_1_5_2","unstructured":"A. J.Dunlop andM. B.Pour\u2010El The degree of unsolvability of a real number. In: Computability and Complexity in Analysis CCA 2000 Swansea UK September 2000 (J. Blanck V. Brattka and P. Hertling eds.) Lecture Notes in Computer Science2064 pp. 16\u201329 (Springer\u2010Verlag Berlin 2001)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"R. L.Epstein Degrees of unsolvability: Structure and theory. Lecture Notes in Math.759(Springer\u2010Verlag Berlin 1979).","DOI":"10.1007\/BFb0067135"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"R. L.Epstein R.Haas andR. L.Kramer Hierarchies of sets and degrees below0\u2032. In: Logic Year 1979\u201080 (Proc. Seminars and Conf. Math. Logic Univ. Connecticut Storrs Conn. 1979\/80) Lecture Notes in Math.859 pp. 32\u201348 (Springer\u2010Verlag Berlin 1981).","DOI":"10.1007\/BFb0090937"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02218750"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00098-X"},{"key":"e_1_2_1_10_2","unstructured":"K.\u2010I.Ko Complexity Theory of Real Functions. Progress in Theoretical Computer Science (Birkh\u00e4user Boston 1991)."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.2307\/2266321"},{"key":"e_1_2_1_12_2","unstructured":"P.Odifreddi Classical Recursion Theory. Volume 125 of Studies in Logic and the Foundations of Mathematics (North\u2010Holland Publ. Comp. Amsterdam 1989)."},{"key":"e_1_2_1_13_2","unstructured":"P.Odifreddi Classical Recursion Theory II. Volume 143 of Studies in Logic and the Foundations of Mathematics (North\u2010Holland Publ. Comp. Amsterdam 1999)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"R.Rettinger X.Zheng R.Gengler andB.von Braunm\u00fchl Weakly computable real numbers and total computable real functions. In: Proceedings of COCOON 2001 Guilin China August 20\u201023 2001 Lecture Notes in Computer Science2108 pp. 586\u2013595 (Springer\u2010Verlag Berlin 2001).","DOI":"10.1007\/3-540-44679-6_65"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1090\/S0002-9939-1954-0063328-5","article-title":"Recursive real numbers","volume":"5","author":"Rice H. G.","year":"1954","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.2307\/2267933"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970028"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1969.31.215"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"R. I.Soare Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic (Springer\u2010Verlag Berlin 1987).","DOI":"10.1007\/978-3-662-02460-7"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.2307\/2267043"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"},{"key":"e_1_2_1_22_2","unstructured":"G.Wu Regular reals. In: Proceedings of CCA 2003 Cincinnati USA (V. Brattka M. Schr\u00f6der K. Weihrauch and N. Zhong eds.) Informatik Berichte FernUniversit\u00e4t Hagen 302 \u2010 8\/2003 pp. 363\u2013374 (2003)."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.2.159"},{"key":"e_1_2_1_24_2","first-page":"172","article-title":"On the definition of degrees of unsolvability for reals (in Chinese)","volume":"38","author":"Zheng X.","year":"1993","journal-title":"Chinese Science Bulletin"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200310110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200310110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T16:14:01Z","timestamp":1693412041000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200310110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8,18]]},"references-count":23,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["10.1002\/malq.200310110"],"URL":"https:\/\/doi.org\/10.1002\/malq.200310110","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8,18]]}}}