On the hierarchies of Δ 2 0 -real numbers
Zheng, Xizhong
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 3-25 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

A real number x is called Δ 2 0 if its binary expansion corresponds to a Δ 2 0 -set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, Δ 2 0 -reals have different levels of effectiveness. This leads to various hierarchies of Δ 2 0 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators.

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007008
Classification:  03D55,  26E40,  68Q15 
@article{ITA_2007__41_1_3_0,
     author = {Zheng, Xizhong},
     title = {On the hierarchies of $\Delta ^0\_2$-real numbers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {3-25},
     doi = {10.1051/ita:2007008},
     mrnumber = {2330040},
     zbl = {pre05238551},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_1_3_0}
}

Zheng, Xizhong. On the hierarchies of $\Delta ^0_2$-real numbers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 3-25. doi : 10.1051/ita:2007008. http://gdmltest.u-ga.fr/item/ITA_2007__41_1_3_0/

[1] K. Ambos-Spies, K. Weihrauch and X. Zheng, Weakly computable real numbers. J. Complexity 16 (2000) 676-690. | Zbl 0974.03054

[2] C.S. Calude, P.H. Hertling, B. Khoussainov and Y. Wang, Recursively enumerable reals and Chaitin Ω numbers. Theor. Comput. Sci. 255 (2001) 125-149. | Zbl 0974.68072

[3] R. Downey, G. Wu and X. Zheng, Degrees of d.c.e. reals. Math. Logic Quart. 50 (2004) 345-350. | Zbl 1059.03075

[4] R.G. Downey, Some computability-theoretic aspects of reals and randomness, in The Notre Dame lectures, Assoc. Symbol. Logic, Urbana, IL. Lect. Notes Log. 18 (2005) 97-147. | Zbl 1075.03020

[5] A.J. Dunlop and M. Boykan Pour-El, The degree of unsolvability of a real number, in Proceedings of CCA 2000, Swansea, UK, September 2000, edited by J. Blanck, V. Brattka and P. Hertling. Lect. Notes Comput. Sci. 2064 (2001) 16-29. | Zbl 0985.03027

[6] H. Gordon Rice, Recursive real numbers. Proc. Amer. Math. Soc. 5 (1954) 784-791. | Zbl 0058.00602

[7] C.-K. Ho, Relatively recursive reals and real functions. Theor. Comput. Sci. 210 (1999) 99-120. | Zbl 0912.68034

[8] K.-I. Ko, Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA (1991). | MR 1137517 | Zbl 0791.03019

[9] Y. Leonidovich Ershov, A certain hierarchy of sets. i, ii, iii. (Russian). Algebra i Logika 7 (1968) 47-73; 7 (1968) 15-47; 9 (1970) 34-51. | Zbl 0233.02017

[10] J. Myhill, Criteria of constructibility for real numbers. J. Symbolic Logic 18 (1953) 7-10. | MR 54549 | Zbl 0052.25101

[11] K. Meng Ng, M. Sc. Thesis. National University of Singapore. (In preparation).

[12] P. Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics 125. North-Holland Publishing Co., Amsterdam (1989). | MR 982269 | Zbl 0661.03029

[13] P. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics 143. North-Holland Publishing Co., Amsterdam (1999). | MR 1718169 | Zbl 0931.03057

[14] A. Raichev, D.c.e. reals, relative randomness, and real closed fields, in CCA 2004, August 16-20, 2004, Lutherstadt Wittenberg, Germany (2004).

[15] R. Rettinger and X. Zheng, On the hierarchy and extension of monotonically computable real numbers. J. Complexity 19 (2003) 672-691. | MR 2003239 | Zbl 1043.03037

[16] R. Rettinger and X. Zheng, Solovay reducibility on d-c.e. real numbers, in COCOON 2005, August 16-19, 2005, Kunming, China. Lect. Notes Comput. Sci. (2005) 359-368. | MR 2190859 | Zbl 1128.03307

[17] R. Rettinger, X. Zheng, R. Gengler and B. Von Braunmühl, Weakly computable real numbers and total computable real functions, in Proceedings of COCOON 2001, Guilin, China, August 20-23, 2001. Lect. Notes Comput. Sci. 2108 (2001) 586-595. | Zbl 0991.03520

[18] R.M. Robinson, Review of “Peter, R., Rekursive Funktionen”. J. Symbolic Logic 16 (1951) 280-282.

[19] R.I. Soare, Computability and recursion. Bull. Symbolic Logic 2 (1996) 284-321. | Zbl 0861.03031

[20] R.I. Soare, Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math. 31 (1969) 215-231. | Zbl 0172.00902

[21] R.I. Soare, Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc. 140 (1969) 271-294. | Zbl 0181.30503

[22] R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, in Perspectives in Mathematical Logic. Springer-Verlag, Berlin (1987). | MR 882921 | Zbl 0623.03042 | Zbl 0667.03030

[23] R.M. Solovay, Draft of a paper (or a series of papers) on chaitin's work .... manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY (1975) 215.

[24] E. Specker, Nicht konstruktiv beweisbare Sätze der Analysis. J. Symbolic Logic 14 (1949) 145-158. | Zbl 0033.34102

[25] A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society 42 (1936) 230-265. | JFM 62.1059.03 | Zbl 0016.09701

[26] A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. A correction, in proceedings of the London Mathematical Society 43 (1937) 544-546. | JFM 63.0823.02 | Zbl 0018.19304

[27] K. Weihrauch and X. Zheng, A finite hierarchy of the recursively enumerable real numbers, in Proceedings of MFCS'98, Brno, Czech Republic, August, 1998. Lect. Notes Comput. Sci. 1450 (1998) 798-806. | Zbl 0920.03054

[28] G. Wu, Regular reals, in Proceedings of CCA 2003, Cincinnati, USA, edited by V. Brattka, M. Schröder, K. Weihrauch and N. Zhong, volume 302 - 8/2003 of Informatik Berichte, FernUniversität Hagen (2003) 363-374.

[29] X. Zheng, Recursive approximability of real numbers. Mathematical Logic Quarterly 48 (2002) 131-156. | Zbl 1017.03039

[30] X. Zheng, On the divergence bounded computable real numbers, in Computing and Combinatorics, edited by T. Warnow and B. Zhu. Lect. Notes Comput. Sci. 2697 102-111, Berlin (2003). Springer. COOCON 2003, July 25-28, 2003, Big Sky, MT, USA. | Zbl 1276.03036

[31] X. Zheng, On the Turing degrees of weakly computable real numbers. J. Logic Computation 13 (2003) 159-172. | Zbl 1054.03040

[32] X. Zheng and R. Rettinger, A note on the Turing degree of divergence bounded computable real numbers, in CCA 2004, August 16-20, Lutherstadt Wittenberg, Germany (2004). | Zbl 1111.03039

[33] X. Zheng and R. Rettinger, On the extensions of solovay reducibility, in COOCON 2004, August 17-20, Jeju Island, Korea. Lect. Notes Comput. Sci. 3106 (2004). | Zbl 1091.03013

[34] X. Zheng and R. Rettinger, Weak computability and representation of reals. Mathematical Logic Quarterly 50 (4/5) (2004) 431-442. | Zbl 1059.03077

[35] X. Zheng, R. Rettinger and R. Gengler, Effective jordan decomposition. Theor. Comput. Syst. 38 (2005) 189-209. | Zbl 1071.03028

[36] X. Zheng, R. Rettingre and G. Barmpalias, h-monotonically computable real numbers. Mathematical Logic Quarterly 51 (2005) 1-14. | Zbl 1066.03060