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

lmcs:732 - Logical Methods in Computer Science, December 25, 2013, Volume 9, Issue 4
Strong Turing Degrees for Additive BSS RAM's

Authors: Gaßner, Christine

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.


Source : oai:arXiv.org:1312.3927
DOI : 10.2168/LMCS-9(4:25)2013
Volume: Volume 9, Issue 4
Published on: December 25, 2013
Submitted on: February 11, 2013
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 81 times.
This article's PDF has been downloaded 39 times.