Algorithm to determine whether Polynomial Diophantine Equation has Integer Solution

Theorem

There is no algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution.

Proof

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Historical Note

Hilbert's $10$th problem was the question:

Given a Diophantine equation with any number of unknown quantities and with rational integer numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

The MRDP Theorem has shown that recursively enumerable sets are equivalent to Diophantine sets.

Matiyasevich's Theorem shows that solutions to Diophantine equations may grow exponentially.

Yuri Vladimirovich Matiyasevich proved this in $1970$ by using a method involving Fibonacci numbers, which grow exponentially.

Hilbert $23$

This problem is no. $10$ in the Hilbert $23$.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Diophantine equation
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Diophantine equation