# Diophantine equation and Turing Machine

If a Diophantine equation is: exists v, p(x,v) = 0 (where v is a vector of finitely many integers) for some polynomial p, is there a Turing machine which prints out all values of x?

-

Given a polynomial $p(\bar{x},\bar{v})$ with integer coefficients, there is indeed a Turing machine that enumerates all tuples of integers $\bar{x}$ for which there exists a tuple of integers $\bar{v}$ with $p(\bar{x},\bar{v}) = 0$. In other words, the set of such tuples $\bar{x}$ is recursively enumerable.
One way to do the enumeration is to start by making a machine that enumerates all pairs of integer tuples $(\bar{x}, \bar{v})$ (where each tuple has the appropriate length). Then feed the output of this machine into a machine that checks whether $p(\bar{x},\bar{v}) = 0$.
On the other hand, there is no Turing machine that takes a polynomial $p$ as input, and a tuple $\bar{x}$ as a second input, and decides whether there is a tuple $\bar{v}$ of integers with $p(\bar{x},\bar{v}) = 0$. This is the MRDP theorem, which solved Hilbert's 10th problem.