Wesley Calvert ; Ken Kramer ; Russell Miller - Noncomputable functions in the Blum-Shub-Smale model

lmcs:1226 - Logical Methods in Computer Science, May 24, 2011, Volume 7, Issue 2 - https://doi.org/10.2168/LMCS-7(2:15)2011
Noncomputable functions in the Blum-Shub-Smale modelArticle

Authors: Wesley Calvert ORCID; Ken Kramer ; Russell Miller

    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.

    https://doi.org/10.2168/LMCS-7(2:15)2011
    Source: arXiv.org:1105.1380
    Volume: Volume 7, Issue 2
    Published on: May 24, 2011
    Imported on: October 30, 2010
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,F.1.1, F.1.3, I.1.2
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Computability Theory, Facing Outwards; Funder: National Science Foundation; Code: 1001306
    • COLLABORATIVE RESEARCH: EMSW21-RTG: JOINT COLUMBIA-CUNY-NYU RESEARCH TRAINING GROUP IN NUMBER THEORY; Funder: National Science Foundation; Code: 0739346

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    2 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 2410 times.
    This article's PDF has been downloaded 863 times.