The exponential diophantine problem for

Journal of Symbolic Logic 85 (2):671-672 (2020)
  Copy   BIBTEX

Abstract

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.

Categories

Keywords

Reprint years

DOI

10.1017/jsl.2020.18

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Undecidable and decidable restrictions of Hilbert's Tenth Problem: images of polynomials vs. images of exponential functions.Mihai Prunescu - 2006 - Mathematical Logic Quarterly 52 (1):14-19.
Classification of Quantifier Prefixes Over Diophantine Equations.Some Diophantine Forms of Godel's Theorem.Universal Diophantine Equation.Exponential Diophantine Representation of Recursively Enumerable Sets.Register Machine Proof of the Theorem on Exponential Diophantine Representation of Enumerable Sets.James P. Jones, Verena H. Dyson, John C. Shepherdson & J. P. Jones - 1986 - Journal of Symbolic Logic 51 (2):477-479.
On the existence of a new family of diophantine equations for Ω.Toby Ord - 2003 - Fundamenta Informaticae 56:273-284.
Diophantine properties of finite commutative rings.Mihai Prunescu - 2003 - Archive for Mathematical Logic 42 (3):293-302.
The Decision Problem for Exponential Diophantine Equations.Martin Davis, Hilary Putnam & Julia Robinson - 1970 - Journal of Symbolic Logic 35 (1):151-152.
Verena H. Dyson, James P. Jones, and John C. Shepherdson. Some diophantine forms of Gödel's theorem. Archiv für mathematische Logik und Grundlagenforschung, vol. 22 , pp. 51–60. - James P. Jones. Universal diophantine equation. The journal of symbolic logic, vol. 47 , pp. 549–571. - J. P. Jones and Ju. V. Matijasevič. Exponential diophantine representation of recursively enumerable sets. English with French abstract. Proceedings of the Herbrand Symposium, Logic Colloquium '81, Proceedings of the Herbrand Symposium held in Marseilles, France, July 1981, edited by J. Stern, Studies in logic and the foundations of mathematics, vol. 107, North-Holland Publishing Company, Amsterdam, New York, and Oxford, 1982, pp. 159–177. - J. P. Jones and Y. V. Matijasevič. Register machine proof of the theorem on exponential diophantine representation of enumerable sets. The journal of symbolic logic, vol. 49 , pp. 818–829. [REVIEW]Martin Davis - 1986 - Journal of Symbolic Logic 51 (2):477-479.
Diophantine Induction.Richard Kaye - 1990 - Annals of Pure and Applied Logic 46 (1):1-40.
Note on Quantifier Prefixes Over Diophantine Equations.Classification of Quantifier Prefixes over Exponential Diophantine Equations.Shih Ping Tung - 1988 - Journal of Symbolic Logic 53 (1):309-310.
Review: Charles N. Delzell, Note on Quantifier Prefixes Over Diophantine Equations; J. P. Jones, H. Levitz, A. J. Wilkie, Classification of Quantifier Prefixes over Exponential Diophantine Equations. [REVIEW]Shih Ping Tung - 1988 - Journal of Symbolic Logic 53 (1):309-310.
Martin Davis, Hilary Putnam, and Julia Robinson. The decision problem for exponential diophantine equations. Annals of mathematics, second series vol. 74 , pp. 425–436. [REVIEW]Hartley Rogers - 1970 - Journal of Symbolic Logic 35 (1):151-152.
A direct method for simulating partial recursive functions by Diophantine equations.Yuri Matiyasevich - 1994 - Annals of Pure and Applied Logic 67 (1-3):325-348.
Diophantine equivalence and countable rings.Alexandra Shlapentokh - 1994 - Journal of Symbolic Logic 59 (3):1068-1095.
The Undecidability of Exponential Diophantine Equations.Hartley Rogers & Julia Robinson - 1970 - Journal of Symbolic Logic 35 (1):152.
Decidability of some problems pertaining to base 2 exponential diophantine equations.Hilbert Levitz - 1985 - Mathematical Logic Quarterly 31 (7‐8):109-115.
Charles N. Delzell. Note on quantifier prefixes over diophantine equations. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 32 , pp. 395–397. - J. P. Jones, H. Levitz, and A. J. Wilkie. Classification of quantifier prefixes over exponential diophantine equations. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 32 , pp. 399–406. [REVIEW]Shih Ping Tung - 1988 - Journal of Symbolic Logic 53 (1):309-310.

Analytics

Added to PP
2020-07-22

Downloads
13 (#973,701)

6 months
5 (#526,961)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references