4
$\begingroup$

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?

1 Answers 1

4

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.

  • 0
    ah thank you, it's possible to print them all out but not in order.2010-12-10