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

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

Full description

Saved in:
Bibliographic Details
Published in:Electronic proceedings in theoretical computer science 2010-01, Vol.24 (Proc. CCA 2010), p.56-66
Main Authors: Calvert, Wesley, Kramer, Ken, Miller, Russell
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2075-2180
2075-2180
DOI:10.4204/EPTCS.24.10