A real number is called if its binary expansion corresponds to a -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, -reals have different levels of effectiveness. This leads to various hierarchies of reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators.
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] Weakly computable real numbers. J. Complexity 16 (2000) 676-690. | Zbl
, and ,[2] Recursively enumerable reals and Chaitin numbers. Theor. Comput. Sci. 255 (2001) 125-149. | Zbl
, , and ,[3] Degrees of d.c.e. reals. Math. Logic Quart. 50 (2004) 345-350. | Zbl
, and ,[4] 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] 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
and ,[6] Recursive real numbers. Proc. Amer. Math. Soc. 5 (1954) 784-791. | Zbl
,[7] Relatively recursive reals and real functions. Theor. Comput. Sci. 210 (1999) 99-120. | Zbl
,[8] Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA (1991). | MR | Zbl
,[9] 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] Criteria of constructibility for real numbers. J. Symbolic Logic 18 (1953) 7-10. | MR | Zbl
,[11] Thesis. National University of Singapore. (In preparation).
, .[12] Classical recursion theory, Studies in Logic and the Foundations of Mathematics 125. North-Holland Publishing Co., Amsterdam (1989). | MR | Zbl
,[13] Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics 143. North-Holland Publishing Co., Amsterdam (1999). | MR | Zbl
,[14] D.c.e. reals, relative randomness, and real closed fields, in CCA 2004, August 16-20, 2004, Lutherstadt Wittenberg, Germany (2004).
,[15] On the hierarchy and extension of monotonically computable real numbers. J. Complexity 19 (2003) 672-691. | MR | Zbl
and ,[16] 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
and ,[17] 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
, , and ,[18] Review of “Peter, R., Rekursive Funktionen”. J. Symbolic Logic 16 (1951) 280-282.
,[19] Computability and recursion. Bull. Symbolic Logic 2 (1996) 284-321. | Zbl
,[20] Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math. 31 (1969) 215-231. | Zbl
,[21] Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc. 140 (1969) 271-294. | Zbl
,[22] 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] 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] Nicht konstruktiv beweisbare Sätze der Analysis. J. Symbolic Logic 14 (1949) 145-158. | Zbl
,[25] On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society 42 (1936) 230-265. | JFM | Zbl
,[26] 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] 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
and ,[28] 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] Recursive approximability of real numbers. Mathematical Logic Quarterly 48 (2002) 131-156. | Zbl
,[30] 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] On the Turing degrees of weakly computable real numbers. J. Logic Computation 13 (2003) 159-172. | Zbl
,[32] A note on the Turing degree of divergence bounded computable real numbers, in CCA 2004, August 16-20, Lutherstadt Wittenberg, Germany (2004). | Zbl
and ,[33] On the extensions of solovay reducibility, in COOCON 2004, August 17-20, Jeju Island, Korea. Lect. Notes Comput. Sci. 3106 (2004). | Zbl
and ,[34] Weak computability and representation of reals. Mathematical Logic Quarterly 50 (4/5) (2004) 431-442. | Zbl
and ,[35] Effective jordan decomposition. Theor. Comput. Syst. 38 (2005) 189-209. | Zbl
, and ,[36] -monotonically computable real numbers. Mathematical Logic Quarterly 51 (2005) 1-14. | Zbl
, and ,Cité par Sources :