Register machine proof of the theorem on exponential diophantine representation of enumerable sets
From MaRDI portal
Publication:3734384
DOI10.2307/2274135zbMath0599.03043OpenAlexW1997517079MaRDI QIDQ3734384
No author found.
Publication date: 1984
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2274135
Decidability (number-theoretic aspects) (11U05) Recursively (computably) enumerable sets and degrees (03D25)
Related Items (27)
A direct method for simulating partial recursive functions by Diophantine equations ⋮ Further results on Hilbert's tenth problem ⋮ Turing Machines for Dummies ⋮ The conformon-P system: a molecular and cell biology-inspired computability model ⋮ Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets ⋮ Incompleteness theorems for random reals ⋮ Extensions of Hilbert's tenth problem ⋮ Metafinite model theory ⋮ The quest for Diophantine finite-fold-ness ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ On some algebraic ways to calculate zeros of the Riemann zeta function ⋮ Undecidability and incompleteness in classical mechanics ⋮ Computability and randomness of Nash equilibrium in infinite games ⋮ \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly ⋮ Martin Davis and Hilbert’s Tenth Problem ⋮ A Story of Hilbert’s Tenth Problem ⋮ Metafinite model theory ⋮ Information-theoretic incompleteness ⋮ LISP program-size complexity. II ⋮ European Summer Meeting of the Association for Symbolic Logic, Hull, 1986 ⋮ Note on the topological structure of random strings ⋮ Three counterexamples refuting Kieu's plan for ``quantum adiabatic hypercomputation; and some uncomputable quantum mechanical tasks ⋮ Unnamed Item ⋮ The Riemann hypothesis in computer science ⋮ Hilbert's Tenth Problem in Coq ⋮ On the computational power of context-free PC grammar systems ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
Cites Work
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- The decision problem for exponential diophantine equations
- How to Program an Infinite Abacus
- Recursive Undecidability--An Exposition
- Hilbert's Tenth Problem is Unsolvable
- A proof of negative answer to Hilbert's $10$th problem
- Applications of a Simple Counting Technique
- An Informal Arithmetical Approach to Computability and Computation
- Computability of Recursive Functions
- Arithmetical problems and recursively enumerable predicates
This page was built for publication: Register machine proof of the theorem on exponential diophantine representation of enumerable sets
