|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |