What Are the Limitations in Diophantine Equations? I read a bit about Diophantine equations, and I learned Hilbert tried to see if a solution exists for problems such as
$x^2y^3z^5-23x^5y^4+11x^2=176$
Apparently, rather than the notion our mathematics has not caught up yet it is actually that, Diophantine equations are impossible to solve. This was demonstrated by Yuri Matiyasevic back in the 70s. 
My question is: Can anybody explain, preferably concisely, why Diophantine equations are impossible to solve according to Matiyasevic's proof? 
 A: The MRDP theorem lets us "port over" basic facts about the behavior of algorithms and halting to Diophantine equations and the existence of solutions; in particular, what we're seeing here is the analogue of the undecidability of the Halting Problem.
Specifically: the MRDP theorem implies that for every algorithm $\alpha$ there is a Diophantine equation $D_\alpha$ such that $D_\alpha$ has a solution if and only if $\alpha$ halts (= finishes and gives an answer) on input $D_\alpha$.

There is a lot of self-reference here, which might trouble you, but it is in fact perfectly fine.

Now suppose $\beta$ were an algorithm for telling whether a Diophantine equation has a solution. Note that this is equivalent to also finding such a solution, if it exists: if we know a Diophantine equation has a solution, we can just search until we find one. Consider the following algorithm $\alpha$:


*

*When we give $\alpha$ a Diophantine equation $E$ as input, $\alpha$ runs $\beta$ on $E$, and bases its further behavior on what happens:


*

*If $\beta$ says "$E$ does not have a root," then $\alpha$ halts.

*If $\beta$ says "$E$ does have a root," then $\alpha$ enters an infinite loop.
Now consider the Diophantine equation $D_\alpha$. If we feed $D_\alpha$ to $\beta$, what happens?


*

*Can $\beta$ say "$D_\alpha$ has a solution"? Well, no: if it did, then $\alpha$ wouldn't halt on input $D_\alpha$ (see the definition of $\alpha$), which means $D_\alpha$ wouldn't have a solution (recall how $D_\alpha$ behaves with respect to $\alpha$), so $\beta$ would be incorrect.

*Can $\beta$ say "$D_\alpha$ has no solution"? Well, it can't do that either: if it did, then $\alpha$ would halt on input $D_\alpha$ (again, see the definition of $\alpha$), which means that $D_\alpha$ would have a solution (again, recall how $D_\alpha$ behaves with respect to $\alpha$), so $\beta$ would again be incorrect.

Now you might further ask how the MRDP theorem is proved. The proof is quite complicated, and I don't think I can do a good summary here, but this part of the wiki page gives a decent quick overview of what results happened when, and this note goes into much more detail without being too overwhelming. For a complete proof, see part II of Manin's text.
