On the hierarchies of Δ 2 0 -real numbers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 1, pp. 3-25.

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.

DOI : 10.1051/ita:2007008
Classification : 03D55, 26E40, 68Q15
Mots-clés : computably approximable reals, $\Delta ^0_2$-reals, hierarchy 
@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},
     pages = {3--25},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {1},
     year = {2007},
     doi = {10.1051/ita:2007008},
     mrnumber = {2330040},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007008/}
}
TY  - JOUR
AU  - Zheng, Xizhong
TI  - On the hierarchies of $\Delta ^0_2$-real numbers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 3
EP  - 25
VL  - 41
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007008/
DO  - 10.1051/ita:2007008
LA  - en
ID  - ITA_2007__41_1_3_0
ER  - 
%0 Journal Article
%A Zheng, Xizhong
%T On the hierarchies of $\Delta ^0_2$-real numbers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 3-25
%V 41
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007008/
%R 10.1051/ita:2007008
%G en
%F 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) no. 1, pp. 3-25. doi : 10.1051/ita:2007008. http://www.numdam.org/articles/10.1051/ita:2007008/

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

[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

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

[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

[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

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

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

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

[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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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

[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

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

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

[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 | Zbl

[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

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

[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 | Zbl

[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

[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

[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

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

[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

[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

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

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

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

Cité par Sources :