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

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

2010-06-02

arxiv.org/abs/1006.0396v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512908