A Banach–Mazur computable but not Markov computable function on the computable real numbers

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


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



    Upload a copy of this work     Papers currently archived: 86,412

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

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

17 (#711,220)

6 months
2 (#522,698)

Historical graph of downloads
How can I increase my downloads?

References found in this work

A Comparison of Five “Computable” Operators.Marian Boykan Pour-El - 1960 - Mathematical Logic Quarterly 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