10
$\begingroup$

In Chaitin's Meta Math! The Quest For Omega, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive integer coefficients: $p=0 \iff p_1 = p_2$.

Then he says that we can think of these equations like a "computer":

Diophantine Equation Computer: $$L(k,n,x,y,z,...)=R(k,n,x,y,z,...)$$ Program: $k$, Output: $n$, Time: $x,y,z,...$

With left side $L$, right side $R$. He says $k$ is the program of this computer, which outputs $n$. He also says that the unknowns are a multi-dimensional time variable.

What confuses me is that he then says that Hilbert's 10th Problem is clearly not solvable when viewed in this way. He basically says "because of Turing's Halting Problem". But I don't see the connection (I'm just beginning to learn the theory). I was hoping someone could more clearly explain what Chaitin's point is here.

I know that Turing's Halting Problem basically states that you cannot predict when a program will halt before it actually halts (given a finite amount of time). What is the application to Hilbert's 10th Problem, using the notation laid out by Chaitin?

$\endgroup$
7
$\begingroup$

Good question. It sounds like you might need some additional background on Hilbert's 10th Problem. I hope this isn't overkill.

The problem asks:

Is there an algorithm that, given a Diophantine polynomial, decides whether or not there is a setting of its variables that makes it equal to $0$?

This was resolved in the 70's as a consequence of the MRDP (also called Matiyasevich's theorem, if you feel like searching it) which states:

Define: A set $D \subset \mathbb{N}$ is Diophantine if there is a Diophantine polynomial $p$ on $k+1$ inputs such that $D = \{ x \, | \, \exists y \in \mathbb{R}_+^k \, p(x, y) = 0\}$.

The Diophantine sets are precisely those that are recognizable by Turing machines.

This theorem is obvious in one direction (every Diophantine set is recognizable by a Turing Machine -- on input $x$, simply have your machine start guessing vectors $y \in \mathbb{R}_+^k$, evaluate $p(x, y)$, and halt if/when you find that $p(x, y) = 0$). It is very non-obvious in the other direction -- why is it true that every Turing recognizable set is Diophantine? The encoding schemes are disgusting, but trust me, it can be done.

Anyways, how does the MRDP theorem resolve Hilbert's 10th problem? Well...

For the sake of contradiction, let's pretend we have an algorithm that, given a Diophantine polynomial $p(y)$, decides whether or not there is an input vector $y$ that causes $p(y) = 0$.

Now I'm going to use this magical algorithm to solve the halting problem. Given a machine, I will use the disgusting encoding of Diophantine equations to convert the problem "Does $M$ halt on input $x$?" into the problem "Does the Diophantine polynomial $p(y | x)$ have a set of inputs that make it equal to $0$?" Then I will use my magical algorithm to solve this problem, and now I have solved the halting problem.

Of course, this is impossible, so in reality there can't be a magical algorithm that searches for an input vector that causes $p(y) = 0$. Similarly, there can't be an algorithm that looks at two Diophantine polynomials and decides if they're ever equal. That's what Chaitin is saying.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.