|
This article is cited in 8 scientific papers (total 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.
Received: 18.08.2015 Revised: 24.02.2016
Citation:
P. Koepke, A. S. Morozov, “The computational power of infinite time Blum–Shub–Smale machines”, Algebra Logika, 56:1 (2017), 55–92; Algebra and Logic, 56:1 (2017), 37–62
Linking options:
https://www.mathnet.ru/eng/al778 https://www.mathnet.ru/eng/al/v56/i1/p55
|
Statistics & downloads: |
Abstract page: | 277 | Full-text PDF : | 48 | References: | 46 | First page: | 17 |
|