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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Seyfferth and P. Koepke, “Towards a theory of infinite time Blum–Shub–Smale machines,” Lect. Notes Comp. Sci., 7318, Springer, Berlin (2012), pp. 405-415.
P. Koepke and A. Morozov, “On the computational strength of infinite time Blum–Shub–Smale machines,” in Turing Centenary Conference 2012: How the World Computes (University of Cambridge, 18-23 June, 2012), Abstracts of informal presentations, Univ. Cambridge (2012).
P. Koepke and A. Morozov, “The computational power of infinite time Blum–Shub–Smale machines,” Algebra and Logic, Vol. 56, No. 1, 37-62 (2017).
P. Welch, “Transfinite machine models,” in Lect. Notes Log., Cambridge, 42, Cambridge Univ. Press, Cambridge (2014), pp. 493-529.
P. D. Welch, “Discrete transfinite computation,” in Turing’s Revolution. The Impact of His Ideas about Computability, G. Sommarugaet al. (Eds.), Springer, Cham (2015), pp. 161-185.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
G. E. Sacks, Higher Recursion Theory (Perspect. Math. Log.), Springer, Berlin (1990).
J. D. Hamkins, “A survey of infinite time Turing machines,” in Lect. Notes Comput. Sci., 4664, Springer, Berlin (2007), pp. 62-71.
P. Koepke and B. Seyfferth, “Ordinal machines and admissible recursion theory,” Ann. Pure Appl. Log., 160, No. 3, 310-318 (2009).
P. Koepke, “Ordinal computability,” in Lect. Notes Comput. Sci., 5635, Springer, Berlin (2009), pp. 280-289.
M. Carl, T. Fischbach, P. Koepke, R. Miller, M. Nasfi, and G. Weckbecker, “The basic theory of infinite time register machines,” Arch. Math. Log., 49, No. 2, 249-273 (2010).
L. Blum, M. Shub, and 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, No. 1, 1-46 (1989).
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the Alexander von Humboldt Foundation. The results were obtained during the second author’s visit to the University of Bonn in spring 2017.
Translated from Algebra i Logika, Vol. 59, No. 6, pp. 627-648, November-December, 2020. Russian DOI: https://doi.org/10.33048/alglog.2020.59.602.
Rights and permissions
About this article
Cite this article
Koepke, P., Morozov, A.S. Characterizations of ITBM-computability. I. Algebra Logic 59, 423–436 (2021). https://doi.org/10.1007/s10469-021-09622-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-021-09622-2