Geodesic
Characterizations of ITBM-computability.~I
Algebra i logika, Tome 59 (2020) no. 6, pp. 627-648.

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

We examine whether some well-known properties of partial recursive functions are valid for ITBM-computable functions, i.e., functions which can be computed with infinite time Blum–Shub–Smale machines. It is shown that properties of graphs of ITBM-computable functions differ from the usual properties of graphs of partial recursive functions. All possible ranges of ITBM-computable functions are described, and we consider the existence problem for ITBM-computable bijections between ITBM-computable sets of the same cardinality.
Keywords: Blum–Shub–Smale machine, ITBM-computable functions, partial recursive functions, graph of function. 
@article{AL_2020_59_6_a1,
     author = {P. Koepke and A. S. Morozov},
     title = {Characterizations of {ITBM-computability.~I}},
     journal = {Algebra i logika},
     pages = {627--648},
     publisher = {mathdoc},
     volume = {59},
     number = {6},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2020_59_6_a1/}
}
TY  - JOUR
AU  - P. Koepke
AU  - A. S. Morozov
TI  - Characterizations of ITBM-computability.~I
JO  - Algebra i logika
PY  - 2020
SP  - 627
EP  - 648
VL  - 59
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2020_59_6_a1/
LA  - ru
ID  - AL_2020_59_6_a1
ER  - 
%0 Journal Article
%A P. Koepke
%A A. S. Morozov
%T Characterizations of ITBM-computability.~I
%J Algebra i logika
%D 2020
%P 627-648
%V 59
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2020_59_6_a1/
%G ru
%F AL_2020_59_6_a1
P. Koepke; A. S. Morozov. Characterizations of ITBM-computability.~I. Algebra i logika, Tome 59 (2020) no. 6, pp. 627-648. http://geodesic.mathdoc.fr/item/AL_2020_59_6_a1/

[1] B. Seyfferth, P. Koepke, “Towards a theory of infinite time Blum–Shub–Smale machines”, How the world computes, Turing centenary conf. and 8th conf. comput. Europe, CiE 2012 (Cambridge, UK, June 18–23, 2012), Lect. Notes Comput. Sci., 7318, eds. S. B. Cooper et al., Springer-Verlag, Berlin, 2012, 405–415 | DOI | MR | Zbl

[2] P. Koepke, A. Morozov, “On the computational strength of infinite time Blum Shub Smale machines”, Turing centenary conference: How the World computes, Abstracts of informal presentations (Univ. Cambridge, 18-23 June, 2012), Univ. Cambridge, 2012, 78 | MR

[3] P. Kepke, A. S. Morozov, “O vychislitelnykh vozmozhnostyakh mashin Blyum–Shuba–Smeila, rabotayuschikh v beskonechnom vremeni”, Algebra i logika, 56:1 (2017), 55–92 \smallskip | MR

[4] P. Welch, “Transfinite machine models”, Turing's legacy: Developments from Turing's ideas in logic, Lect. Notes Log., Cambridge, 42, ed. R. Downey, Cambridge Univ. Press, Cambridge, 2014, 493–529 | MR

[5] P. D. Welch, “Discrete Transfinite Computation”, Turing's revolution. The impact of his ideas about computability, eds. G. Sommaruga et al., Birkhäuser/Springer, Cham, 2015, 161–185 | DOI | MR | Zbl

[6] Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, М., 1972 | MR | Zbl

[7] G. E. Sacks, Higher recursion theory, Perspect. Math. Log., Springer-Verlag, Berlin etc., 1990 | DOI | MR | Zbl

[8] J. D. Hamkins, “A survey of infinite time Turing machines”, Machines, computations, and universality, 5th int. conf. MCU 2007 (Orléans, France, September 10–13, 2007), Lect. Notes Comput. Sci., 4664, eds. J. Durand-Lose et al., Springer, Berlin, 2007, 62–71 | DOI | Zbl

[9] P. Koepke, B. Seyfferth, “Ordinal machines and admissible recursion theory”, Ann. Pure Appl. Logic, 160:3 (2009), 310–318 | DOI | MR | Zbl

[10] P. Koepke, “Ordinal computability”, Mathematical theory and computational practice, 5th conf. comput. Europe, CiE 2009 (Heidelberg, Germany, July 19–24, 2009), Lect. Notes Comput. Sci., 5635, eds. K. Ambos-Spies et al., Springer-Verlag, Berlin, 2009, 280—289 | DOI | MR | Zbl

[11] M. Carl, T. Fischbach, P. Koepke, R. Miller, M. Nasfi, G. Weckbecker, “The basic theory of infinite time register machines”, Arch. Math. Logic, 49:2 (2010), 249–273 | DOI | MR | Zbl

[12] L. Blum, M. Shub, S. Smale, “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines”, Bull. Am. Math. Soc., New Ser., 21:1 (1989), 1–46 | DOI | MR | Zbl