Hilbert's Tenth Problem is Unsolvable

DOI10.2307/2318447zbMath0277.02008OpenAlexW4254784218WikidataQ55878720 ScholiaQ55878720MaRDI QIDQ4401926

Martin Davis

Publication date: 1973

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2318447

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Decidability of theories and sets of sentences (03B25) History of mathematical logic and foundations (03-03) Applications of computability and recursion theory (03D80) Diophantine equations (11D99)

Related Items (only showing first 100 items - show all)

A direct method for simulating partial recursive functions by Diophantine equations ⋮ Power series with coefficients from a finite set ⋮ Diophantine undecidability in some rings of algebraic numbers of totally real infinite extensions of \(\mathbb{Q}\) ⋮ Further results on Hilbert's tenth problem ⋮ Diophantine Sets Over Algebraic Integer Rings. II ⋮ Diophantine definability and decidability in extensions of degree 2 of totally real fields ⋮ ELLIPTIC CURVE POINTS AND DIOPHANTINE MODELS OF ℤ IN LARGE SUBRINGS OF NUMBER FIELDS ⋮ Arithmetic on curves ⋮ Associative-commutative unification ⋮ Unification problems with one-sided distributivity ⋮ Interprétation de l'arithmétique dans certains groupes de permutations affines par morceaux d'un intervalle ⋮ On the metamathematics of the P vs. NP question ⋮ The Diophantine Problem for Polynomial Rings and Fields of Rational Functions ⋮ Register machine proof of the theorem on exponential diophantine representation of enumerable sets ⋮ Degrees of Unsolvability: A Tutorial ⋮ An asymptotic formula for \(\pi\) ⋮ The undecidability of the D_A-unification problem ⋮ R.J. THOMPSON’S GROUPSFANDTARE BI-INTERPRETABLE WITH THE RING OF THE INTEGERS ⋮ DIOPHANTINE SETS OF POLYNOMIALS OVER ALGEBRAIC EXTENSIONS OF THE RATIONALS ⋮ Diophantine representations of linear recurrences. I ⋮ Recursively enumerable sets of polynomials over a finite field ⋮ The logic of pseudo-\(S\)-integers ⋮ A survey on Büchi's problem: new presentations and open problems ⋮ Existential Diophantine definability of string length ⋮ A sharp version of the bounded Matijasevich conjecture and the end-extension problem ⋮ An analogue of Hilbert's 10th problem for fields of meromorphic functions over non-Archimedean valued fields ⋮ Unnamed Item ⋮ Elliptic curves retaining their rank in finite extensions and Hilbert's Tenth Problem for rings of algebraic numbers ⋮ Primes are nonnegative values of a polynomial in 10 variables ⋮ A new proof of the theorem on exponential diophantine representation of enumerable sets ⋮ On a theorem of Matiyasevich ⋮ Algorithms for sentences over integral domains ⋮ Uniform existential interpretation of arithmetic in rings of functions of positive characteristic ⋮ Inferring answers to queries ⋮ Undecidability and incompleteness in classical mechanics ⋮ Defining integrality at prime sets of high density in number fields. ⋮ Diophantine undecidability for some function fields of infinite transcendence degree and positive characteristic ⋮ Two conjectures on the arithmetic in ℝ and ℂ ⋮ Generic oracles, uniform machines, and codes ⋮ My Life as a Logician ⋮ Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory ⋮ A Story of Hilbert’s Tenth Problem ⋮ What Is Essential Unification? ⋮ Recursively enumerable sets of polynomials over a finite field are Diophantine ⋮ Weak quantifier elimination for the full linear theory of the integers ⋮ Automatic verification of a class of systolic circuits ⋮ An extension of Büchi’s problem for polynomial rings in zero characteristic ⋮ Defining Integers ⋮ The ring of \(k\)-regular sequences ⋮ Hilbert's tenth problem is of unification type zero ⋮ On a Diophantine representation of the predicate of provability ⋮ Minimality and completions of PA ⋮ The undecidability of pattern matching in calculi where primitive recursive functions are representable ⋮ Diophantine sets of polynomials over number fields ⋮ Diophantine definability and decidability in large subrings of totally real number fields and their totally complex extensions of degree 2 ⋮ Syntax and semantics of universal programming languages ⋮ Diophantine equations and the generalized Riemann hypothesis ⋮ The analogue of Büchi's problem for function fields ⋮ An existential divisibility lemma for global fields ⋮ Three universal representations of recursively enumerable sets ⋮ New techniques and results in multidimensional problems ⋮ The theory of all substructures of a structure: Characterisation and decision problems ⋮ Computability on reals, infinite limits and differential equations ⋮ The Riemann hypothesis in computer science ⋮ Some decision problems for polynomial mappings ⋮ The Matiyasevich theorem. Preliminaries ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Some nonstationary linear and quasilinear systems occuring in the investigation of the motion of viscous fluids ⋮ Theories of arithmetics in finite models ⋮ Weakly associative relation algebras with projections ⋮ Rings of algebraic numbers in infinite extensions of \(\mathbb Q\) and elliptic curves retaining their rank ⋮ LCM of sequences of polynomials ⋮ Factoring numbers in O(log n) arithmetic steps ⋮ Existence of noneffectivizable estimates in the theory of exponential Diophantine equations ⋮ Infiniteness sets of primes, admitting diophantine representations in eight variables ⋮ Recursively enumerable sets and degrees ⋮ H for Hilbert. \dots and M for mathematics ⋮ Execution traces and programming-language semantics ⋮ A unification-theoretic method for investigating the \(k\)-provability problem ⋮ Definability, decidability, complexity ⋮ Basic Diophantine relations ⋮ A decision algorithm for distributive unification ⋮ On \(q\)-arithmetic entire functions ⋮ Complete sets of unifiers and matchers in equational theories ⋮ The incompleteness of theories of games ⋮ Decidability questions for a ring of Laurent polynomials ⋮ Mass problems associated with effectively closed sets ⋮ Semi-algebraic sets of \(f\)-vectors ⋮ How to build a hypercomputer ⋮ Diophantine undecidability of holomorphy rings of function fields of characteristic 0 ⋮ Deep learning and k-means clustering in heterotic string vacua with line bundles ⋮ A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets ⋮ Diophantine sets. II ⋮ Formalization of the MRDP theorem in the Mizar system ⋮ Hilbert's tenth problem for term algebras with a substitution operator ⋮ Simple second-order languages for which unification is undecidable ⋮ Universal diophantine equation ⋮ On effectively computable realizations of choice functions ⋮ On Dipphantine definability and decidability in some rings of algebraic functions of characteristic 0 ⋮ A Diophantine Problem for Laurent Polynomial Rings

This page was built for publication: Hilbert's Tenth Problem is Unsolvable