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:

a finite non-empty solution set $N$

which necessarily has an infinite complement $\overline{N} = \mathbb{N} \setminus N$

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

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

(type $\tau_{\omega/1}$)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

notof 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$

isof type $\tau_{1/\omega}$orof type $\tau_{\omega/\omega}$orof type $\tau_{\omega/1}$orof 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

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