NONCOMPUTABLE FUNCTIONS IN THE BLUM-SHUB-SMALE MODEL

作     者：Calvert, Wesley Kramer, Ken Miller, Russell 

作者机构：So Illinois Univ Dept Math Carbondale IL 62901 USA CUNY Queens Coll Dept Math Flushing NY 11367 USA CUNY Grad Ctr PhD Program Math New York NY 10016 USA CUNY Grad Ctr PhD Program Comp Sci New York NY 10016 USA 

出 版 物：《LOGICAL METHODS IN COMPUTER SCIENCE》 (Log. Methods Comp. Sci.)

年 卷 期：2011年第7卷第2期

核心收录：

学科分类：08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Templeton Foundation NSF [DMS-0739346, DMS-1001306] City University of New York PSC-CUNY [61467-00 39, 62632-00 40, 63286-00 41] Queens College [90927-08 08] 

主　　题：algebraic real numbers Blum-Shub-Smale computation BSS machine oracle computation relative computability 

摘      要：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.