RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2020 Volume 59, Number 6, Pages 627–648 (Mi al2640)

This article is cited in 4 papers

Characterizations of ITBM-computability. I

P. Koepkea, A. S. Morozovb

a Math. Inst., Rheinische Friedrich-Wilhelms-Univ. Bonn, Bonn, GERMANY
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: 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.

UDC: 510.5

Received: 05.06.2020
Revised: 05.03.2021

DOI: 10.33048/alglog.2020.59.602


 English version:
Algebra and Logic, 2021, 59:6, 423–436

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025