Real analytic machines and degrees: a topological view on algebraic limiting computation

DOI10.2168/LMCS-7(3:11)2011MaRDI QIDQ3224677zbMATH OpenOpenAlexFDO

Authors Tobias Gärtner, Martin Ziegler

Publication date 2 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.0398

zbMATH Keywords

Blum-Shub-Smale modelBorel hierarchyhalting oraclelimiting computation

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Descriptive set theory (03E15)

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).

Recommendations

• Real analytic machines and degrees
• Computability of analytic functions with analytic machines
• Representation theorems for analytic machines and computability of analytic functions
• Strong Turing degrees for additive BSS RAM's
• Analytic machines

Cited in

(7)

• Analytic machines
• A topological view on algebraic computation models
• Computability of analytic functions with analytic machines
• scientific article; zbMATH DE number 517066 (Why is no real title available?)
• Real analytic machines and degrees
• Computing measure as a primitive operation in real number computation
• Representation theorems for analytic machines and computability of analytic functions

This page was built for publication: Real analytic machines and degrees: a topological view on algebraic limiting computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3224677)