The Computational Power of Infinite Time Blum–Shub–Smale Machines
Tóm tắt
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 ℝ∩L
ωω.
Tài liệu tham khảo
J. D. Hamkins and A. Lewis, “Infinite time Turing machines,” J. Symb. Log., 65, No. 2, 567-604 (2000).
P. Koepke, “Turing computations on ordinals,” Bull. Symb. Log., 11, No. 3, 377-397 (2005).
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.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
G. E. Sacks, Higher Recursion Theory, Springer, Berlin (1990).