Weak computability and representation of reals

Mathematical Logic Quarterly 50 (4-5):431-442 (2004)
  Copy   BIBTEX

Abstract

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,102

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
Regular reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.
Complexity of reals in inner models of set theory.Boban Velickovic & W. Hugh Woodin - 1998 - Annals of Pure and Applied Logic 92 (3):283-295.
Cohen reals from small forcings.Janusz Pawlikowski - 2001 - Journal of Symbolic Logic 66 (1):318-324.
Needed reals and recursion in generic reals.Andreas Blass - 2001 - Annals of Pure and Applied Logic 109 (1-2):77-88.
Fragments of Martin's axiom and δ13 sets of reals.Joan Bagaria - 1994 - Annals of Pure and Applied Logic 69 (1):1-25.
Randomness and the linear degrees of computability.Andrew Em Lewis & George Barmpalias - 2007 - Annals of Pure and Applied Logic 145 (3):252-257.
Understanding preservation theorems, II.Chaz Schlindwein - 2010 - Mathematical Logic Quarterly 56 (5):549-560.
Approximation Representations for Δ2 Reals.George Barmpalias - 2004 - Archive for Mathematical Logic 43 (8):947-964.
Degrees of d. c. e. reals.Rod Downey, Guohua Wu & Xizhong Zheng - 2004 - Mathematical Logic Quarterly 50 (4-5):345-350.

Analytics

Added to PP
2013-12-01

Downloads
35 (#408,502)

6 months
4 (#404,301)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Nicht konstruktiv beweisbare sätze der analysis.Ernst Specker - 1949 - Journal of Symbolic Logic 14 (3):145-158.
Rekursive Funktionen.Raphael M. Robinson & Rozsa Peter - 1951 - Journal of Symbolic Logic 16 (4):280.
Criteria of constructibility for real numbers.John Myhill - 1953 - Journal of Symbolic Logic 18 (1):7-10.
Degrees of d. c. e. reals.Rod Downey, Guohua Wu & Xizhong Zheng - 2004 - Mathematical Logic Quarterly 50 (4-5):345-350.

Add more references