Some types of diophantine equations and their decidability

Question

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?

Answer 1

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.