Invisible wrote:
> Question: Why is this undecidable?

It's due to a proof known as Matiyasevich's theorem which I'm not 
familiar with the details of offhand.  The gist is that you can show 
that every recursively enumerable set* can be represented as the roots 
of such a polynomial.  Since there are non-computable recursively 
enumerable sets there must be such polynomials (known as Diophantine 
equations) which are not computable.

If you're interested in the details, this paper looks like it might be 
useful, although I haven't read it myself:

http://modular.math.washington.edu/edu/Spring2003/21n/papers/hilbert10.pdf

If you're interested in the details, but less so, this is probably more 
useful:

http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

More intuitively, note that the problem statement come pretty close to 
having Fermat's last theorem as a subproblem.

> Surely it's a trivial matter of iterating over all integers and testing 
> whether any of them is a root?

If there is no solution to a given polynomial, when does this program 
you describe halt?



* A recursively enumerable set is defines as any set for which these 
exists an algorithm that will eventually list any number in the set, and 
no numbers that are not.  Note that the algorithm is not required to 
ever halt, so you can't , in general, be sure which numbers are not in 
the set and which are in the set but it just hasn't gotten around to 
listing yet.

An example of such a set which is not computable would be the set of 
numbers corresponding to the binary representations of all programs 
which eventually halt.

Post a reply to this message