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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,549

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

H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Normal Numbers and Limit Computable Cantor Series.Achilles Beros & Konstantinos Beros - 2017 - Notre Dame Journal of Formal Logic 58 (2):215-220.
The Arithmetical Hierarchy of Real Numbers.Xizhong Zheng & Klaus Weihrauch - 2001 - Mathematical Logic Quarterly 47 (1):51-66.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
A Real Number Structure that is Effectively Categorical.Peter Hertling - 1999 - Mathematical Logic Quarterly 45 (2):147-182.
Degree spectra of real closed fields.Russell Miller & Victor Ocasio González - 2019 - Archive for Mathematical Logic 58 (3-4):387-411.
Primitive recursive real numbers.Qingliang Chen, Kaile Su & Xizhong Zheng - 2007 - Mathematical Logic Quarterly 53 (4‐5):365-380.

Analytics

Added to PP
2014-01-16

Downloads
28 (#568,659)

6 months
11 (#350,453)

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