Hilbert’s tenth problem

E208849

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.

All labels observed (2)

How this entity was disambiguated

Statements (47)

Predicate Object
instanceOf decision problem
mathematical problem
problem in computability theory
problem in number theory
alsoKnownAs H10
answer no algorithm exists that solves it in general
asksFor algorithm to decide solvability of Diophantine equations in integers
general method to determine whether a Diophantine equation has an integer solution
concerns Diophantine equations
integer solutions of polynomial equations
decidability undecidable
field computability theory
mathematical logic
mathematics
number theory
formalizationUses polynomial equations with integer coefficients
historicalImportance central in development of modern computability theory
key example of an undecidable problem in number theory
impliesLimitOn algorithmic solvability of Diophantine equations
inputType Diophantine equation
inspiredWorkBy Hilary Putnam
Julia Robinson
Martin Davis
Yuri Matiyasevich
locationPosed Paris
numberInHilbertList 10
outputType yes-no answer about existence of integer solutions
partOf Hilbert problems
surface form: Hilbert’s problems
posedBy David Hilbert
presentedAt International Congress of Mathematicians
surface form: International Congress of Mathematicians 1900
quantifiesOver integer solutions
relatedTo Church–Turing thesis
Davis–Putnam–Robinson–Matiyasevich theorem
Turing machine
computably enumerable sets
recursively enumerable sets
shows fundamental limits of computability
not all mathematical questions about integers are algorithmically decidable
solutionCompletedBy Yuri Matiyasevich
solutionStatus negatively solved
solvedBy Hilary Putnam
Julia Robinson
Martin Davis
Yuri Matiyasevich
status unsolvable by algorithm
yearPosed 1900
yearSolutionCompleted 1970

How these facts were elicited

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Hilbert problems hasPart Hilbert’s tenth problem
Hilbert problems notableProblem Hilbert’s tenth problem
this entity surface form: Diophantine equations decision problem
Entscheidungsproblem relatedTo Hilbert’s tenth problem