DPRM theorem(Davis, Putnam, Robinson, Matiyasevich):
A subset of $\mathcal{Z}$ is listable iff it is diophantine.
Listable means that there is an algorithm that prints the subset. Diophantine set consists of integers for which diophantine equations has solutions.
Undeciability of the halting problem yields a listable set that is not computable. By DPRM theorem, listable implies diophantine. Hence, diophantine set is not computable.
By definition of diophantine set, we have a polynomial $p(t,\overrightarrow{x})$ such that there is no algorithm for deciding for which values of $a \in \mathcal{Z}$ the equation $p(a,\overrightarrow{x})$ has a solution.
Thus, there is no algorithm for deciding the existence of integer solutions to all polynomial equations.
No comments:
Post a Comment