Christine Gaßner - Strong Turing Degrees for Additive BSS RAM's

lmcs:732 - Logical Methods in Computer Science, December 25, 2013, Volume 9, Issue 4 - https://doi.org/10.2168/LMCS-9(4:25)2013
Strong Turing Degrees for Additive BSS RAM's

Authors: Christine Gaßner

    For the additive real BSS machines using only constants 0 and 1 and order tests we consider the corresponding Turing reducibility and characterize some semi-decidable decision problems over the reals. In order to refine, step-by-step, a linear hierarchy of Turing degrees with respect to this model, we define several halting problems for classes of additive machines with different abilities and construct further suitable decision problems. In the construction we use methods of the classical recursion theory as well as techniques for proving bounds resulting from algebraic properties. In this way we extend a known hierarchy of problems below the halting problem for the additive machines using only equality tests and we present a further subhierarchy of semi-decidable problems between the halting problems for the additive machines using only equality tests and using order tests, respectively.


    Volume: Volume 9, Issue 4
    Published on: December 25, 2013
    Accepted on: June 25, 2015
    Submitted on: February 11, 2013
    Keywords: Computer Science - Logic in Computer Science

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 376 times.
    This article's PDF has been downloaded 288 times.