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

Algebra Logika, 2017 Volume 56, Number 1, Pages 55–92 (Mi al778)

This article is cited in 8 papers

The computational power of infinite time Blum–Shub–Smale machines

P. Koepkea, A. S. Morozovbc

a Math. Inst., Rheinische Friedrich-Wilhelms-Univ. Bonn, Endenicher Allee 60, Bonn, 53115 Germany
b Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
c Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090 Russia

Abstract: Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with $\mathbb R\cap L_{\omega^\omega}$.

Keywords: infinite time Blum–Shub–Smale machines, infinite computations, iterated jump, ITBM, BSS-machines, computable reals.

UDC: 510.5

Received: 18.08.2015
Revised: 24.02.2016

DOI: 10.17377/alglog.2017.56.103


 English version:
Algebra and Logic, 2017, 56:1, 37–62

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025