Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The MDRP theorem – which answers Hilbert's tenth problem in the negative – says:

There is no algorithm for determining whether an arbitrary diophantine equation has a solution.

In other words: there is no algorithm for determining whether an arbitrary diophantine equation $p(n_1,\dots,n_k,x)=0$ has a non-empty solution set

$$N = \lbrace x \in \mathbb{N}\ |\ (\exists n_1,\dots,n_k)\ p(n_1,\dots,n_k,x)=0 \rbrace$$

There are essentially four ways for a diophantine equation to have a non-empty solution set:

  1. a finite non-empty solution set $N$
    which necessarily has an infinite complement $\overline{N} = \mathbb{N} \setminus N$
    (type $\tau_{1/\omega}$)

  2. an infinite solution set with an infinite complement
    (type $\tau_{\omega/\omega}$)

  3. an infinite solution set with a finite complement
    (type $\tau_{\omega/1}$)

  4. an infinite solution set with an empty complement
    (type $\tau_{\omega/0}$)

Accordingly the MRDP theorem says:

There is no algorithm for determining whether an arbitrary diophantine equation $p(n_1,\dots,n_k,x)=0$ is not of type $\tau_{0/\omega}$ (i.e. does not have an empty solution set).

But this is equivalent with:

There is no algorithm for determining whether an arbitrary diophantine equation $p(n_1,\dots,n_k,x)=0$ is of type $\tau_{1/\omega}$ or of type $\tau_{\omega/\omega}$ or of type $\tau_{\omega/1}$ or of type $\tau_{\omega/0}$.

My first question is:

($*$) Is it decidable (or semi-decidable) whether the solution set of an diophantine equation is of type $\tau_{\omega/0}$, i.e. for all $x \in \mathbb{N}$ it holds that $$(\exists n_1,\dots,n_k)\ p(n_1,\dots,n_k,x)=0$$

Naively, one might believe that the answer is "yes" because

Conjecture: The solution set of an diophantine equation $p(n_1,\dots,n_k,x)=0$ is of type $\tau_{\omega/0}$ iff there are $n_i, k$ and another polynomial $p'(n_1,\dots,n_k,x)$ such that $$p(n_1,\dots,n_k,x) = p'(n_1,\dots,n_k,x)(x-n_i)^k$$

Because in this case $x$ – via $n_i$ – can take every value. But even when this conjecture is too naive and false, the question ($*$) might be answered in the positive in another way.

But if the question ($*$) is to be answered in the negative, this post stops here.


Otherwise it continues. In this case we can omit the type $\tau_{\omega/0}$ from the disjunction above and obtain:

There is no algorithm for determining whether an arbitrary diophantine equation $p(n_1,\dots,n_k,x)=0$ is of type $\tau_{1/\omega}$ or of type $\tau_{\omega/\omega}$ or of type $\tau_{\omega/1}$.

And another question arises naturally:

($*\!*$) Is it decidable (or semi-decidable) whether the solution set of an diophantine equation is of type $\tau_{\omega/1}$, i.e. for all but finitely many $x \in \mathbb{N}$ it holds that $$(\exists n_1,\dots,n_k)\ p(n_1,\dots,n_k,x)=0$$

And so on. Which results in the question:

Can the undecidability of a diophantine equation to be not of type $\tau_{0/\omega}$ be reduced to the undecidability of a diophantine equation to (positively) be of another type?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

My first remark is that your question really has little to do with diophantine solutions sets, since by the MRDP theorem these are precisely the computably enumerable sets. So all your questions amount to exactly equivalent questions about the c.e. sets. In other words, every Turing machine program $e$ computes a c.e. set $W_e$, and you are asking about deciding whether $W_e=\mathbb{N}$? whether $W_e$ is infinite? whether $W_e$ is finite? whether $W_e$ is co-finite? whether $W_e$ is empty?

All these questions are undecidable, and furthermore, none of them are even c.e. So there are no such decision procedures to decide the problems you mention in your question. The MRDP theorem explains exactly that every c.e. set $W_e$ is diophantine and conversely.

Let's begin by showing that the set $\text{Inf}$ of programs $e$ such that $W_e$ is infinite, is not computable, and indeed, it is not even semi-decidable; it is a $\Pi^0_2$-complete set, and thus equivalent to the double jump. One cannot answer this question even with an oracle for the halting problem.

To see that there is no computable procedure to decide if a given c.e. set $W$ contains every number, suppose toward contradiction that you could decide this. Then the halting problem would be decidable by the following procedure: given a Turing machine program $p$, define $W$ to consist of all numbers, if $p$ halts on $0$, and otherwise nothing. This is a c.e. set, and $p$ halts on $0$ just in case $W$ is everything, and so if we could decide if $W$ is everything, then we could decide the halting problem, a contradiction.

Essentially similar reasoning shows that you cannot decide whether a given c.e. set is infinite, whether it is co-finite, whether it is finite, and so on.

Let's now prove the further property that $\text{Inf}$ is not even c.e. One can get a hint of this by looking at the quantifier complexity. Namely, to say that a c.e. set is everything is to assert $\forall x W(x)$, where $W(x)$ is c.e. and hence of the form $\exists n\phi(n,x)$, so we have $\forall x\exists n\phi(n,x)$, which is complexity $\Pi^0_2$. One can show that the set $\text{Inf}$ of all programs $e$ that accept every input (which is equivalent to your decision problem) is $\Pi^0_2$-complete, and hence not $\Sigma^)_1$ and therefore not c.e. To see this, suppose that we have any given $\Pi^0_2$ question $\forall x\exists n\phi(x,n,y)$. Define a c.e. set $W$ that starts checking this: it starts with $x=0$ and searches for a witness $n$, enumerating $x$ into $W$ when the witness is found; and then it moves to $x+1$. This set $W$ will be everything just in case the $\Pi^0_2$ statement is true, and it will be finite otherwise, including all the $x$ up to the first failing instance $x$. So this reduces the $\Pi^0_2$ question to the question of whether a given c.e. set is everything or not. So that property is $\Pi^0_2$-complete and hence cannot be c.e.

Similar argument shows that the set of programs $e$ which compute finite sets is $\Sigma^0_2$-complete, and therefore not c.e.; the set of programs $e$ that compute the empty set is $\Pi^0_1$-complete, and therefore not c.e., the set of programs $e$ that compute infinite sets is $\Pi^0_2$-complete, and therefore not c.e. These are all explained in detailed in Soare's book on the Computably Enumerable sets and degrees, or any other decent book on computability theory.

And each of these facts about the c.e. sets corresponds to an analogous fact about the diophantince sets, in light of the MRDP theorem.

share|improve this answer
1  
It might be useful to mention that, in converting the question from Diophantine sets to c.e. sets, you've tacitly used that the MRDP theorem holds uniformly, in the sense that, from an index $e$, one can effectively compute a Diophantine definition for $W_e$. –  Andreas Blass Jul 8 at 2:03
    
Yes, that is completely right. We can go back and forth computably from any of the usual presentations of the c.e. sets, in terms of diophantine equations, Turing machines, definability complexity, and so on, in a completely uniform manner. –  Joel David Hamkins Jul 8 at 2:32
    
Thanks for the elaborate answer! But why do you say, that the question has little to do with diophantine sets? Since c.e. and diophantine sets are the same, it has to do with diophantine sets - like your answer does. You prefer Turing machines, I prefer diophantine equations. So why did you insist on it in your first remark? –  Hans Stricker Jul 8 at 6:37
1  
Oh, I had just meant that when it comes to decidability questions about general diophantine sets, most of what we know comes from computability theory and the characterization of the diophantine sets as the c.e. sets, rather than from the general theory of diophantine sets. I think of the diophantine characterization as just another characterization on the list, like (many versions of) Turing machines, register machines, numerous other machine characterizations, group presentations, (failures of) tiling problems, game of life, and so on. –  Joel David Hamkins Jul 8 at 10:45
    
@Andreas: Once you know that the $W_e$’s are well-defined in the first place (i.e., there exists a universal r.e. predicate), the uniform version of the MRDP theorem is a trivial corollary of the plain MRDP theorem, so this does not really make a difference. –  Emil Jeřábek Jul 8 at 11:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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