Computation over algebraic structures and a classification of undecidable problems

DOI10.1017/S0960129516000116MaRDI QIDQ4593236zbMATH OpenFDO

Authors Christine Gaßner

Publication date 22 November 2017

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0960129516000116

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• The Arithmetical Hierarchy Over the Reals
• Noncomputable functions in the Blum-Shub-Smale model
• Computational complexity in algebraic systems
• Toward a generalized computability theory
• A survey on real structural complexity theory

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• scientific article; zbMATH DE number 781350 (Why is no real title available?)
• scientific article; zbMATH DE number 785052 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Abstract First Order Computability. I
• Algorithmic Procedures
• An explicit solution to Post's problem over the reals
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity theory and the operational structure of algebraic programming systems
• Computability of String Functions Over Algebraic Structures Armin Hemmerling
• Computing over the reals with addition and order
• Computing over the reals with addition and order: Higher complexity classes
• Descriptive set theory
• Every \({\Delta}^0_2\)-set is natural, up to Turing equivalence
• Finite model theory and its applications.
• Implicit complexity over an arbitrary structure: Quantifier alternations
• Noncomputable functions in the Blum-Shub-Smale model
• On NP-completeness for linear machines
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On some decision problems in programming
• Oracles and relativizations of the P =? NP question for several structures
• Some definitional suggestions for automata theory
• Strong Turing degrees for additive BSS RAM's
• The Arithmetical Hierarchy Over the Reals

Cited in

(3)

• Undecidability in Some Structures Related to Computation Theory
• Decidability of classes of algebraic systems in polynomial time
• An introduction to a model of abstract computation: the BSS-RAM model

This page was built for publication: Computation over algebraic structures and a classification of undecidable problems

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