Geodesic
Reducibility of computable metrics on the real line
Algebra i logika, Tome 56 (2017) no. 4, pp. 453-476.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study computable reducibility of computable metrics on $\mathbf R$ induced by reducibility of their respective Cauchy representations. It is proved that this ordering has a subordering isomorphic to an arbitrary countable tree. Also we introduce a weak version of computable reducibility and construct a countable antichain of computable metrics that are incomparable with respect to it. Informally, copies of the real line equipped with these metrics are pairwise homeomorphic but not computably homeomorphic.
Keywords: computable metric space, Cauchy representation, reducibility of representations. 
@article{AL_2017_56_4_a4,
     author = {R. A. Kornev},
     title = {Reducibility of computable metrics on the real line},
     journal = {Algebra i logika},
     pages = {453--476},
     publisher = {mathdoc},
     volume = {56},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2017_56_4_a4/}
}
TY  - JOUR
AU  - R. A. Kornev
TI  - Reducibility of computable metrics on the real line
JO  - Algebra i logika
PY  - 2017
SP  - 453
EP  - 476
VL  - 56
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2017_56_4_a4/
LA  - ru
ID  - AL_2017_56_4_a4
ER  - 
%0 Journal Article
%A R. A. Kornev
%T Reducibility of computable metrics on the real line
%J Algebra i logika
%D 2017
%P 453-476
%V 56
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2017_56_4_a4/
%G ru
%F AL_2017_56_4_a4
R. A. Kornev. Reducibility of computable metrics on the real line. Algebra i logika, Tome 56 (2017) no. 4, pp. 453-476. http://geodesic.mathdoc.fr/item/AL_2017_56_4_a4/

[1] M. B. Pour-El, J. I. Richards, Computability in analysis and physics, Perspect. Math. Logic, Springer-Verlag, Berlin etc., 1989 | DOI | MR | Zbl

[2] Z. Iljazović, “Isometries and computability structures”, J. UCS, 16:18 (2010), 2569–2596 | MR | Zbl

[3] A. G. Melnikov, “Computably isometric spaces”, J. Symb. Log., 78:4 (2013), 1055–1085 | DOI | MR | Zbl

[4] A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proc. Lond. Math. Soc. II Ser., 42 (1936), 230–265 | MR | Zbl

[5] A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem. A correction”, Proc. Lond. Math. Soc. II Ser., 43 (1937), 544–546 | MR | Zbl

[6] N. A. Shanin, “Konstruktivnye veschestvennye chisla i konstruktivnye funktsionalnye prostranstva”, Problemy konstruktivnogo napravleniya v matematike. 2. Konstruktivnyi matematicheskii analiz, Tr. MIAN SSSR, 67, izd-vo AN SSSR, M.–L., 1962, 15–294 | MR | Zbl

[7] Y. N. Moschovakis, “Recursive metric spaces”, Fundam. Math., 55 (1964), 215–238 | DOI | MR | Zbl

[8] Ch. Kreitz, K. Weihrauch, “Theory of representations”, Theor. Comput. Sci., 38 (1985), 35–53 | DOI | MR | Zbl

[9] K. Weihrauch, “Computability on computable metric spaces”, Theor. Comput. Sci., 113:2 (1993), 191–210 | DOI | MR | Zbl

[10] K. Weihrauch, Computable analysis. An introduction, Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2000 | DOI | MR | Zbl

[11] R. Dillhage, Computable functional analysis. Compact operators on computable Banach spaces and computable best approximation, PhD Thesis, Fak. Math. Inform., FernUniversität Hagen, 2012

[12] M. A. Khamsi, W. A. Kirk, An introduction to metric spaces and fixed point theory, Pure Appl. Math. (Hoboken), John Wiley Sons, NJ, 2001 | MR | Zbl