Strong Turing Degrees for Additive BSS RAM's
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,...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2013-12-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/732/pdf |
| _version_ | 1827322897410031616 |
|---|---|
| author | Christine Gaßner |
| author_facet | Christine Gaßner |
| author_sort | Christine Gaßner |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:37:09Z |
| format | Article |
| id | doaj.art-e6a912e602ec4f549bbb7d80f70ee56b |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:09Z |
| publishDate | 2013-12-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-e6a912e602ec4f549bbb7d80f70ee56b2024-03-08T09:30:37ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742013-12-01Volume 9, Issue 410.2168/LMCS-9(4:25)2013732Strong Turing Degrees for Additive BSS RAM'sChristine GaßnerFor 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.https://lmcs.episciences.org/732/pdfcomputer science - logic in computer science |
| spellingShingle | Christine Gaßner Strong Turing Degrees for Additive BSS RAM's Logical Methods in Computer Science computer science - logic in computer science |
| title | Strong Turing Degrees for Additive BSS RAM's |
| title_full | Strong Turing Degrees for Additive BSS RAM's |
| title_fullStr | Strong Turing Degrees for Additive BSS RAM's |
| title_full_unstemmed | Strong Turing Degrees for Additive BSS RAM's |
| title_short | Strong Turing Degrees for Additive BSS RAM's |
| title_sort | strong turing degrees for additive bss ram s |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/732/pdf |
| work_keys_str_mv | AT christinegaßner strongturingdegreesforadditivebssrams |