Recherche et téléchargement d’archives de revues mathématiques numérisées

 
 
  Table des matières de ce fascicule | Article précédent | Article suivant
Zheng, Xizhong
On the hierarchies of $\Delta ^0_2$-real numbers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 41 no. 1 (2007), p. 3-25
Texte intégral djvu | pdf | Analyses MR 2330040 | Zbl pre05238551
Class. Math.: 03D55, 26E40, 68Q15
Mots clés: computably approximable reals, $\Delta ^0_2$-reals, hierarchy

URL stable: http://www.numdam.org/item?id=ITA_2007__41_1_3_0

Voir cet article sur le site de l'éditeur

Résumé

A real number $x$ is called $\Delta ^0_2$ if its binary expansion corresponds to a $\Delta ^0_2$-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, $\Delta ^0_2$-reals have different levels of effectiveness. This leads to various hierarchies of $\Delta ^0_2$ reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators.

Bibliographie

[1] K. Ambos-Spies, K. Weihrauch and X. Zheng, Weakly computable real numbers. J. Complexity 16 (2000) 676690.  Zbl 0974.03054
[2] C.S. Calude, P.H. Hertling, B. Khoussainov and Y. Wang, Recursively enumerable reals and Chaitin $\Omega $ numbers. Theor. Comput. Sci. 255 (2001) 125149.  Zbl 0974.68072
[3] R. Downey, G. Wu and X. Zheng, Degrees of d.c.e. reals. Math. Logic Quart. 50 (2004) 345350.  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) 97147.  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) 1629.  Zbl 0985.03027
[6] H. Gordon Rice, Recursive real numbers. Proc. Amer. Math. Soc. 5 (1954) 784791.  Zbl 0058.00602
[7] C.-K. Ho, Relatively recursive reals and real functions. Theor. Comput. Sci. 210 (1999) 99120.  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) 4773; 7 (1968) 1547; 9 (1970) 3451.  Zbl 0233.02017
[10] J. Myhill, Criteria of constructibility for real numbers. J. Symbolic Logic 18 (1953) 710.
Article |  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 1620, 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) 672691.  Zbl 1043.03037
[16] R. Rettinger and X. Zheng, Solovay reducibility on d-c.e. real numbers, in COCOON 2005, August 1619, 2005, Kunming, China. Lect. Notes Comput. Sci. (2005) 359368.  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 2023, 2001. Lect. Notes Comput. Sci. 2108 (2001) 586595.  Zbl 0991.03520
[18] R.M. Robinson, Review of “Peter, R., Rekursive Funktionen”. J. Symbolic Logic 16 (1951) 280282.
Article
[19] R.I. Soare, Computability and recursion. Bull. Symbolic Logic 2 (1996) 284321.
Article |  Zbl 0861.03031
[20] R.I. Soare, Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math. 31 (1969) 215231.
Article |  Zbl 0172.00902
[21] R.I. Soare, Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc. 140 (1969) 271294.  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 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) 145158.
Article |  Zbl 0033.34102
[25] A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society 42 (1936) 230265.  JFM 62.1059.03
[26] A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. A correction, in proceedings of the London Mathematical Society 43 (1937) 544546.  JFM 63.0823.02
[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) 798806.  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) 363374.
[29] X. Zheng, Recursive approximability of real numbers. Mathematical Logic Quarterly 48 (2002) 131156.  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 102111, Berlin (2003). Springer. COOCON 2003, July 2528, 2003, Big Sky, MT, USA.
[31] X. Zheng, On the Turing degrees of weakly computable real numbers. J. Logic Computation 13 (2003) 159172.  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 1620, Lutherstadt Wittenberg, Germany (2004).  Zbl 1111.03039
[33] X. Zheng and R. Rettinger, On the extensions of solovay reducibility, in COOCON 2004, August 1720, 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) 431442.  Zbl 1059.03077
[35] X. Zheng, R. Rettinger and R. Gengler, Effective jordan decomposition. Theor. Comput. Syst. 38 (2005) 189209.  Zbl 1071.03028
[36] X. Zheng, R. Rettingre and G. Barmpalias, $h$-monotonically computable real numbers. Mathematical Logic Quarterly 51 (2005) 114.  Zbl 1066.03060
Copyright Cellule MathDoc 2014 | Crédit | Plan du site