On the hierarchies of Δ20-real numbers

Xizhong Zheng

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 1, page 3-25
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Zheng, Xizhong. "On the hierarchies of Δ20-real numbers." RAIRO - Theoretical Informatics and Applications 41.1 (2007): 3-25. <http://eudml.org/doc/250050>.

@article{Zheng2007,
abstract = { A real number x is called Δ20 if its binary expansion corresponds to a Δ20-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, Δ20-reals have different levels of effectiveness. This leads to various hierarchies of Δ20 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators. },
author = {Zheng, Xizhong},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Computably approximable reals; Δ20-reals; hierarchy.; computably approximable reals; -reals; hierarchy},
language = {eng},
month = {4},
number = {1},
pages = {3-25},
publisher = {EDP Sciences},
title = {On the hierarchies of Δ20-real numbers},
url = {http://eudml.org/doc/250050},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Zheng, Xizhong
TI - On the hierarchies of Δ20-real numbers
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/4//
PB - EDP Sciences
VL - 41
IS - 1
SP - 3
EP - 25
AB - A real number x is called Δ20 if its binary expansion corresponds to a Δ20-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, Δ20-reals have different levels of effectiveness. This leads to various hierarchies of Δ20 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators.
LA - eng
KW - Computably approximable reals; Δ20-reals; hierarchy.; computably approximable reals; -reals; hierarchy
UR - http://eudml.org/doc/250050
ER -

References

top
  1. K. Ambos-Spies, K. Weihrauch and X. Zheng, Weakly computable real numbers. J. Complexity16 (2000) 676–690.  
  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.  
  3. R. Downey, G. Wu and X. Zheng, Degrees of d.c.e. reals. Math. Logic Quart.50 (2004) 345–350.  
  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.  
  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.  
  6. H. Gordon Rice, Recursive real numbers. Proc. Amer. Math. Soc.5 (1954) 784–791.  
  7. C.-K. Ho, Relatively recursive reals and real functions. Theor. Comput. Sci.210 (1999) 99–120.  
  8. K.-I. Ko, Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA (1991).  
  9. Y. Leonidovich Ershov, A certain hierarchy of sets. i, ii, iii. (Russian). Algebra i Logika7 (1968) 47–73; 7 (1968) 15–47; 9 (1970) 34–51.  
  10. J. Myhill, Criteria of constructibility for real numbers. J. Symbolic Logic18 (1953) 7–10.  
  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 Mathematics125. North-Holland Publishing Co., Amsterdam (1989).  
  13. P. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics143. North-Holland Publishing Co., Amsterdam (1999).  
  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. Complexity19 (2003) 672–691.  
  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.  
  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.  
  18. R.M. Robinson, Review of “Peter, R., Rekursive Funktionen”. J. Symbolic Logic16 (1951) 280–282.  
  19. R.I. Soare, Computability and recursion. Bull. Symbolic Logic2 (1996) 284–321.  
  20. R.I. Soare, Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math.31 (1969) 215–231.  
  21. R.I. Soare, Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc.140 (1969) 271–294.  
  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).  
  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 Logic14 (1949) 145–158.  
  25. A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society42 (1936) 230–265.  
  26. A.M. Turing, On computable numbers, with an application to the “Entscheidungsproblem”. A correction, in proceedings of the London Mathematical Society43 (1937) 544–546.  
  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.  
  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 Quarterly48 (2002) 131–156.  
  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.  
  31. X. Zheng, On the Turing degrees of weakly computable real numbers. J. Logic Computation13 (2003) 159–172.  
  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).  
  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).  
  34. X. Zheng and R. Rettinger, Weak computability and representation of reals. Mathematical Logic Quarterly50 (4/5) (2004) 431–442.  
  35. X. Zheng, R. Rettinger and R. Gengler, Effective jordan decomposition. Theor. Comput. Syst.38 (2005) 189–209.  
  36. X. Zheng, R. Rettingre and G. Barmpalias, h-monotonically computable real numbers. Mathematical Logic Quarterly51 (2005) 1–14.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.