Noncomputable functions in the Blum-Shub-Smale model

Details Noncomputable functions in the Blum-Shub-Smale model Noncomputable functions in the Blum-Shub-Smale model

2011-05-06

arxiv.org/abs/1105.1380v2

LMCS 7 (2:15) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(2:15)2011

Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on relative computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for relative BSS-computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine.

Affiliated with

Also associated with

No associations

Rating

Noncomputable functions in the Blum-Shub-Smale model 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 Noncomputable functions in the Blum-Shub-Smale model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Noncomputable functions in the Blum-Shub-Smale model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-653173