Davis–Putnam–Robinson–Matiyasevich theorem
E838586
The Davis–Putnam–Robinson–Matiyasevich theorem is a landmark result in mathematical logic and number theory that shows every recursively enumerable set is Diophantine, implying the unsolvability of Hilbert’s tenth problem.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Davis–Putnam–Robinson–Matiyasevich theorem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T10055467 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Davis–Putnam–Robinson–Matiyasevich theorem Context triple: [Hilbert’s tenth problem, relatedTo, Davis–Putnam–Robinson–Matiyasevich theorem]
-
A.
Hilbert’s tenth problem
Hilbert’s tenth problem is a famous unsolved question in mathematics that asked for a general algorithm to determine whether any given Diophantine equation has an integer solution, and whose negative answer helped establish fundamental limits of computability.
-
B.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
C.
Tarski–Mostowski–Robinson theorem
The Tarski–Mostowski–Robinson theorem is a fundamental result in model theory that characterizes when a class of structures is first-order axiomatizable, linking definability properties with closure under ultraproducts and isomorphisms.
-
D.
Herbrand's theorem
Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.
-
E.
Hilbert’s second problem
Hilbert’s second problem is one of David Hilbert’s famous list of 23 problems, asking for a proof of the consistency of arithmetic from a finite set of axioms using finitary methods.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Davis–Putnam–Robinson–Matiyasevich theorem Target entity description: The Davis–Putnam–Robinson–Matiyasevich theorem is a landmark result in mathematical logic and number theory that shows every recursively enumerable set is Diophantine, implying the unsolvability of Hilbert’s tenth problem.
-
A.
Hilbert’s tenth problem
Hilbert’s tenth problem is a famous unsolved question in mathematics that asked for a general algorithm to determine whether any given Diophantine equation has an integer solution, and whose negative answer helped establish fundamental limits of computability.
-
B.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
C.
Tarski–Mostowski–Robinson theorem
The Tarski–Mostowski–Robinson theorem is a fundamental result in model theory that characterizes when a class of structures is first-order axiomatizable, linking definability properties with closure under ultraproducts and isomorphisms.
-
D.
Herbrand's theorem
Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.
-
E.
Hilbert’s second problem
Hilbert’s second problem is one of David Hilbert’s famous list of 23 problems, asking for a proof of the consistency of arithmetic from a finite set of axioms using finitary methods.
- F. None of above. chosen
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf | mathematical theorem ⓘ |
| alsoKnownAs | DPRM theorem NERFINISHED ⓘ |
| classification | undecidability theorem ⓘ |
| completedBy | Yuri Matiyasevich NERFINISHED ⓘ |
| completionYear | 1970 ⓘ |
| concerns |
Diophantine equations
ⓘ
Diophantine sets ⓘ Hilbert's tenth problem NERFINISHED ⓘ recursively enumerable sets ⓘ |
| domain | natural numbers ⓘ |
| field |
Diophantine geometry
NERFINISHED
ⓘ
computability theory ⓘ mathematical logic ⓘ number theory ⓘ recursion theory ⓘ |
| historicalPrecursor |
partial results by Hilary Putnam
ⓘ
partial results by Julia Robinson ⓘ partial results by Martin Davis ⓘ |
| implies |
there is no algorithm to decide whether an arbitrary Diophantine equation has an integer solution
ⓘ
unsolvability of Hilbert's tenth problem ⓘ |
| importance |
central result connecting computability and number theory
ⓘ
landmark result in the theory of Diophantine equations ⓘ |
| inspiredBy | Hilbert's tenth problem NERFINISHED ⓘ |
| involves |
existential quantifiers over integers
ⓘ
polynomials with integer coefficients ⓘ |
| namedAfter |
Hilary Putnam
NERFINISHED
ⓘ
Julia Robinson NERFINISHED ⓘ Martin Davis NERFINISHED ⓘ Yuri Matiyasevich NERFINISHED ⓘ |
| proofTechnique |
encoding of recursively enumerable sets by Diophantine equations
ⓘ
use of Fibonacci numbers in Matiyasevich's final step ⓘ |
| relatedTo |
Church–Turing thesis
NERFINISHED
ⓘ
Gödel's incompleteness theorems NERFINISHED ⓘ Hilbert's problems NERFINISHED ⓘ undecidability results in mathematics ⓘ |
| shows |
every recursively enumerable set can be represented as the set of parameter values for which a polynomial equation with integer coefficients has a solution in the remaining variables
ⓘ
no algorithm can decide solvability of arbitrary polynomial equations with integer coefficients in several variables ⓘ recursively enumerable subsets of the natural numbers coincide with Diophantine subsets ⓘ there exist specific polynomial equations whose solvability encodes arbitrary computations ⓘ |
| states | every recursively enumerable set of natural numbers is Diophantine ⓘ |
| typicalFormulation | for every recursively enumerable set S subset of N there exists a polynomial p with integer coefficients such that n is in S iff there exist integers x1,...,xk with p(n,x1,...,xk)=0 ⓘ |
| usesConcept |
Diophantine representation of computable functions
ⓘ
exponential Diophantine equations ⓘ recursion theory ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Davis–Putnam–Robinson–Matiyasevich theorem Description of subject: The Davis–Putnam–Robinson–Matiyasevich theorem is a landmark result in mathematical logic and number theory that shows every recursively enumerable set is Diophantine, implying the unsolvability of Hilbert’s tenth problem.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.