09-08-2026, 04:14 PM
The MRDP Theorem — Peter Smith
Peter Smith gives an accessible introduction to the MRDP theorem—the Matiyasevich–Robinson–Davis–Putnam theorem—which provides the negative solution to Hilbert’s Tenth Problem. Hilbert asked whether there could be an algorithm which, given an arbitrary Diophantine equation $p(x_1,\ldots,x_n)=0$ with integer coefficients, decides in finitely many steps whether it has an integer solution. Smith first explains Diophantine equations and Diophantine sets: a set $K\subseteq\mathbb N$ is Diophantine when membership can be expressed as $x\in K\iff \exists y_1\cdots \exists y_k;p(x,y_1,\ldots,y_k)=0$. He then connects this apparently number-theoretic notion with computability. Every Diophantine set is recursively enumerable because possible tuples can simply be searched mechanically. The profound converse, completed by Yuri Matiyasevich following work of Martin Davis, Hilary Putnam and Julia Robinson, states that every recursively enumerable set is Diophantine. Matiyasevich supplied the crucial step by showing how exponential behaviour could itself be represented Diophantinely, using properties of Fibonacci-type sequences.
Thus, $\boxed{\text{Diophantine sets}=\text{recursively enumerable sets}}$. Since recursively enumerable sets exist whose membership is undecidable, a hypothetical algorithm deciding whether every polynomial equation has a solution would make every recursively enumerable set decidable—a contradiction. Hence the MRDP theorem implies that there is no algorithm which determines for every Diophantine equation whether it has a solution. Smith then develops the striking connection with mathematical logic: recursively enumerable sets correspond to $\Sigma_1$-definable sets, and MRDP allows such statements to be translated into assertions about polynomial equations. Consequently, statements equivalent to “this particular Diophantine equation has no solution” can be true but unprovable in Peano Arithmetic.
The theorem therefore creates a remarkable bridge between number theory, computability and mathematical logic. In particular, Gödelian incompleteness can appear in a very concrete arithmetic form: there are particular polynomial equations for which the assertion that they have no integer solutions is true but cannot be proved within a given sufficiently strong formal theory.
Key takeaways
ARTICLE [PDF]
Peter Smith gives an accessible introduction to the MRDP theorem—the Matiyasevich–Robinson–Davis–Putnam theorem—which provides the negative solution to Hilbert’s Tenth Problem. Hilbert asked whether there could be an algorithm which, given an arbitrary Diophantine equation $p(x_1,\ldots,x_n)=0$ with integer coefficients, decides in finitely many steps whether it has an integer solution. Smith first explains Diophantine equations and Diophantine sets: a set $K\subseteq\mathbb N$ is Diophantine when membership can be expressed as $x\in K\iff \exists y_1\cdots \exists y_k;p(x,y_1,\ldots,y_k)=0$. He then connects this apparently number-theoretic notion with computability. Every Diophantine set is recursively enumerable because possible tuples can simply be searched mechanically. The profound converse, completed by Yuri Matiyasevich following work of Martin Davis, Hilary Putnam and Julia Robinson, states that every recursively enumerable set is Diophantine. Matiyasevich supplied the crucial step by showing how exponential behaviour could itself be represented Diophantinely, using properties of Fibonacci-type sequences.
Thus, $\boxed{\text{Diophantine sets}=\text{recursively enumerable sets}}$. Since recursively enumerable sets exist whose membership is undecidable, a hypothetical algorithm deciding whether every polynomial equation has a solution would make every recursively enumerable set decidable—a contradiction. Hence the MRDP theorem implies that there is no algorithm which determines for every Diophantine equation whether it has a solution. Smith then develops the striking connection with mathematical logic: recursively enumerable sets correspond to $\Sigma_1$-definable sets, and MRDP allows such statements to be translated into assertions about polynomial equations. Consequently, statements equivalent to “this particular Diophantine equation has no solution” can be true but unprovable in Peano Arithmetic.
The theorem therefore creates a remarkable bridge between number theory, computability and mathematical logic. In particular, Gödelian incompleteness can appear in a very concrete arithmetic form: there are particular polynomial equations for which the assertion that they have no integer solutions is true but cannot be proved within a given sufficiently strong formal theory.
Key takeaways
- Hilbert’s Tenth Problem has a negative answer: there is no universal algorithm deciding whether arbitrary Diophantine equations have integer solutions.
- The central equivalence is $\boxed{K\text{ is Diophantine}\iff K\text{ is recursively enumerable}}$.
- MRDP connects Diophantine equations, computability theory and mathematical logic.
- Some statements of the form “this polynomial equation has no integer solution” can be true but unprovable in a sufficiently strong formal system.
ARTICLE [PDF]
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘