The Cardinality of an Oracle in Blum-Shub-Smale Computation

Wesley Calvert
(Murray State University)
Ken Kramer
(Queens College & CUNY Graduate Center)
Russell Miller
(Queens College & CUNY Graduate Center)

We examine the relation of BSS-reducibility on subsets of the real numbers. The question was asked recently (and anonymously) whether it is possible for the halting problem H in BSS-computation to be BSS-reducible to a countable set. Intuitively, it seems that a countable set ought not to contain enough information to decide membership in a reasonably complex (uncountable) set such as H. We confirm this intuition, and prove a more general theorem linking the cardinality of the oracle set to the cardinality, in a local sense, of the set which it computes. We also mention other recent results on BSS-computation and algebraic real numbers.

In Xizhong Zheng and Ning Zhong: Proceedings Seventh International Conference on Computability and Complexity in Analysis (CCA 2010), Zhenjiang, China, 21-25th June 2010, Electronic Proceedings in Theoretical Computer Science 24, pp. 56–66.
Published: 3rd June 2010.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: