Real Analytic Machines and Degrees

Abstract

We study and compare in two degree-theoretic ways (iterated Halting oracles analogous to Kleene's arithmetical hierarchy and the Borel hierarchy of descriptive set theory) the capabilities and limitations of three models of analytic computation: BSS machines (aka real-RAM) and strongly/weakly analytic machines as introduced by Hotz et. al. (1995).

Keywords

• computer science - logic in computer science
• mathematics - logic
• f.4.1, f.1.1, g.1.0