Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-16T11:15:15.189Z Has data issue: false hasContentIssue false
  • English
  • Français

On the hierarchies of Δ20-real numbers

Published online by Cambridge University Press:  24 April 2007

Xizhong Zheng
Xizhong Zheng*
Affiliation:
Department of Computer Science, Jiangsu University, Zhenjiang 212013, China. Theoretische Informatik, BTU Cottbus, 03044 Cottbus, Germany; [email protected]
Get access

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.

Keywords

Computably approximable realsΔ20-realshierarchy.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 1: Real Numbers , January 2007 , pp. 3 - 25
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ambos-Spies, K., Weihrauch, K. and Zheng, X., Weakly computable real numbers. J. Complexity 16 (2000) 676–690. CrossRef
Calude, C.S., Hertling, P.H., Khoussainov, B. and Wang, Y., Recursively enumerable reals and Chaitin Ω numbers. Theor. Comput. Sci. 255 (2001) 125–149. CrossRef
Downey, R., Wu, G. and Zheng, X., Degrees of d.c.e. reals. Math. Logic Quart. 50 (2004) 345–350. CrossRef
Downey, R.G., 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.
Dunlop, A.J. and Boykan Pour-El, M., 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. CrossRef
Gordon Rice, H., Recursive real numbers. Proc. Amer. Math. Soc. 5 (1954) 784–791. CrossRef
Relatively, C.-K. Ho recursive reals and real functions. Theor. Comput. Sci. 210 (1999) 99–120.
K.-I. Ko, Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA (1991).
Leonidovich Ershov, Y., A certain hierarchy of sets. i, ii, iii. (Russian). Algebra i Logika 7 (1968) 47–73; 7 (1968) 15–47; 9 (1970) 34–51.
Myhill, J., Criteria of constructibility for real numbers. J. Symbolic Logic 18 (1953) 7–10. CrossRef
K. Meng Ng, M. Sc. Thesis. National University of Singapore. (In preparation).
P. Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics 125. North-Holland Publishing Co., Amsterdam (1989).
P. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics 143. North-Holland Publishing Co., Amsterdam (1999).
A. Raichev, D.c.e. reals, relative randomness, and real closed fields, in CCA 2004, August 16–20, 2004, Lutherstadt Wittenberg, Germany (2004).
Rettinger, R. and Zheng, X., On the hierarchy and extension of monotonically computable real numbers. J. Complexity 19 (2003) 672–691. CrossRef
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.
Rettinger, R., Zheng, X., Gengler, R. and von Braunmühl, B., 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. CrossRef
Robinson, R.M., Review of “Peter, R., Rekursive Funktionen”. J. Symbolic Logic 16 (1951) 280–282.
Soare, R.I., Computability and recursion. Bull. Symbolic Logic 2 (1996) 284–321. CrossRef
Soare, R.I., Cohesive sets and recursively enumerable Dedekind cuts. Pacific J. Math. 31 (1969) 215–231. CrossRef
Soare, R.I., Recursion theory and Dedekind cuts. Trans. Amer. Math. Soc. 140 (1969) 271–294.
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).
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.
Specker, E., Nicht konstruktiv beweisbare Sätze der Analysis. J. Symbolic Logic 14 (1949) 145–158. CrossRef
Turing, A.M., On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society 42 (1936) 230–265.
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.
Weihrauch, K. and Zheng, X., 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. CrossRef
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.
Zheng, X., Recursive approximability of real numbers. Mathematical Logic Quarterly 48 (2002) 131–156. 3.0.CO;2-#>CrossRef
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.
Zheng, X., On the Turing degrees of weakly computable real numbers. J. Logic Computation 13 (2003) 159–172. CrossRef
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).
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).
X. Zheng and R. Rettinger, Weak computability and representation of reals. Mathematical Logic Quarterly 50 (4/5) (2004) 431–442.
Zheng, X., Rettinger, R. and Gengler, R., Effective jordan decomposition. Theor. Comput. Syst. 38 (2005) 189–209. CrossRef
Zheng, X., Rettingre, R. and Barmpalias, G., h-monotonically computable real numbers. Mathematical Logic Quarterly 51 (2005) 1–14. CrossRef