An explicit solution to Post's problem over the reals
From MaRDI portal
Publication:2479313
DOI10.1016/j.jco.2006.09.004zbMath1151.03019OpenAlexW1590722750MaRDI QIDQ2479313
Publication date: 26 March 2008
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2006.09.004
Undecidability and degrees of sets of sentences (03D35) Turing machines and related notions (03D10) Other Turing degree structures (03D28)
Related Items
A topological view on algebraic computation models ⋮ Computational processes, observers and Turing incompleteness ⋮ Computation over algebraic structures and a classification of undecidable problems ⋮ SOME INITIAL THOUGHTS ON BOUNDED QUERY COMPUTATIONS OVER THE REALS ⋮ Real computational universality: the word problem for a class of groups with infinite presentation ⋮ 2010 North American Annual Meeting of the Association for Symbolic Logic ⋮ A hierarchy below the halting problem for additive machines ⋮ Generalized finite automata over real and complex numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A uniform approach to obtain diagonal sets in complexity classes
- A survey on real structural complexity theory
- Saturation and stability in the theory of computation over the reals
- Real number models under various sets of operations
- Computing over the reals with addition and order
- Post's problem for supertasks has both positive and negative solutions
- Hypercomputation with quantum adiabatic processes
- Completeness and reduction in algebraic complexity theory
- Computing over the reals with addition and order: Higher complexity classes
- A note on non-complete problems in \(NP_\mathbb{R}\)
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Classical physics and the Church--Turing Thesis
- Existence and Uniqueness of Interpolating Rational Functions
- Irreducible polynomials with integral coefficients have succinct certificates
- The Arithmetical Hierarchy Over the Reals
- On the Structure of Polynomial Time Reducibility
- On the Structure of $\cal NP_\Bbb C$
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Computability Over Arbitrary Fields
- On the Linear Independence of Fractional Powers of Integers
- Recursively enumerable sets of positive integers and their decision problems
- Algorithms in real algebraic geometry
