Annals of Pure and Applied Logic 132 (2-3):227-246 (2005)

We consider two classical computability notions for functions mapping all computable real numbers to computable real numbers. It is clear that any function that is computable in the sense of Markov, i.e., computable with respect to a standard Gödel numbering of the computable real numbers, is computable in the sense of Banach and Mazur, i.e., it maps any computable sequence of real numbers to a computable sequence of real numbers. We show that the converse is not true. This solves a long-standing open problem posed by Kushner
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2004.08.001
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,607
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

A Comparison of Five “Computable” Operators.Marian Boykan Pour-El - 1960 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 6 (15-22):325-340.
A Comparison of Five “Computable” Operators.Marian Boykan Pour-El - 1960 - Mathematical Logic Quarterly 6 (15‐22):325-340.
Recursive Metric Spaces.Y. N. Moschovakis - 1966 - Journal of Symbolic Logic 31 (4):651-652.
On the Continuity of Constructive Functions.A. A. Markov - 1956 - Journal of Symbolic Logic 21 (3):319-320.
Classes Récursivement Fermees Et Fonctions Majorantes.Daniel Lacombe - 1959 - Journal of Symbolic Logic 24 (1):52-53.

Add more references

Citations of this work BETA

Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.

Add more citations

Similar books and articles

Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
H‐Monotonically Computable Real Numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Computable Metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
WHAT IS. . . A Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.


Added to PP index

Total views
9 ( #957,763 of 2,533,648 )

Recent downloads (6 months)
1 ( #389,210 of 2,533,648 )

How can I increase my downloads?


My notes