Strong Turing degrees for additive BSS RAM's

DOI10.2168/LMCS-9(4:25)2013MaRDI QIDQ2871478zbMATH OpenFDO

Authors Christine Gaßner

Publication date 8 January 2014

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.3927

zbMATH Keywords

additive machinesBSS modelhalting problemoracle machineTuring degrees

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: 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.

Recommendations

• Low upper bounds in the Turing degrees revisited
• Strength of the reversible, garbage-free \(2^{k } \pm 1\) multiplier
• On the strongly bounded Turing degrees of simple sets
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• An extension of the recursively enumerable Turing degrees
• Embeddings into the Turing degrees
• scientific article; zbMATH DE number 7250153
• Memoryless computation: new results, constructions, and extensions
• Complementation in the Turing degrees
• The strength of non-size increasing computation

Cited in

(10)

• A hierarchy below the halting problem for additive machines
• The Turing closure of an Archimedean field
• Noncomputable functions in the Blum-Shub-Smale model
• Real analytic machines and degrees: a topological view on algebraic limiting computation
• Computation over algebraic structures and a classification of undecidable problems
• scientific article; zbMATH DE number 1827830 (Why is no real title available?)
• A Survey on Analog Models of Computation
• The cardinality of an oracle in Blum-Shub-Smale computation
• Real analytic machines and degrees
• Fundamentals of Computation Theory

This page was built for publication: Strong Turing degrees for additive BSS RAM's

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2871478)