Computer Science – Logic in Computer Science
Scientific paper
2010-06-02
EPTCS 24, 2010, pp. 56-66
Computer Science
Logic in Computer Science
Scientific paper
10.4204/EPTCS.24.10
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.
Calvert Wesley
Krämer Ken
Miller Russell
No associations
LandOfFree
The Cardinality of an Oracle in Blum-Shub-Smale Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Cardinality of an Oracle in Blum-Shub-Smale Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Cardinality of an Oracle in Blum-Shub-Smale Computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-512908