Is the set of indices of partial computable functions with finite domains r.e.?

Question

Let $W_x$ be the domain of the partial computable function $\varphi_x$. I know that the set $$\operatorname{Fin} = \{x : W_x\text{ is finite}\}$$ is not computable (as a corollary of Rice's theorem, for instance). My question is,

Is the set $\operatorname{Fin}$ recursively enumerable?

that is, is its semi-characteristic function computable? I think it's not, intuitively, there's no way to accept elements of this set since in this case we would need to compute $\varphi_x(n)$ for all $n$ and see if this eventually comes undefined for large enough $n$'s, but this requires infinitely many computations of course.

Answer 1

There is a general method to answer this kind of question, which Rogers called the Tarski-Kuratowski computation in his book. You first write down a definition of the set in the arithmetical hierarchy, in which all the leading quantifiers explicitly shown in prenex form and in which the central "matrix" is decidable: $$ e \in \text{Fin} \Leftrightarrow (\exists k)(\forall i)(\forall s) [ \phi_{e,s}(i)\mathord{\downarrow} \Rightarrow i < k]$$ Here as usual $\phi_{e,s}(i)\downarrow$ says that $\phi_e(i)$ halts in no more than $s$ steps, which is a decidable question.

From this, we see that the set Fin is $\Sigma^0_2$. That means you should next try to show the set is $\Sigma^0_2$ hard, at which point you will know the set is $\Sigma^0_2$ complete. In particular, that would mean the set is not r.e. because the r.e. sets are exactly the $\Sigma^0_1$ sets, and a $\Sigma^0_2$ hard set cannot be $\Sigma^0_1$.

In practice, most sets that arise in practice will be complete for the level of the arithmetical hierarchy that the natural prenex form of the set suggests ($\Sigma^0_2$, in this case). That is why this method is worth knowing.

The thing that remains is showing that the set Fin is $\Sigma^0_2$ hard. To do that, suppose you have a $\Sigma^0_2$ formula $\psi(x) \equiv (\exists n)(\forall m)\phi(n,m,x)$. Given $x$, we need to make a program $e = e(x)$ that will be in Fin if and only if $\psi(x)$ holds. That is not too hard to do, using the fact that $\phi(n,m,x)$ is decidable from $n$, $m$, and $x$. I'll leave it to you.

It also helps to know some examples of particular sets at particular levels of the hierarchy:

• The halting set $\{e : \phi_e(0)\mathord{\downarrow}\}$ is $\Sigma^0_1$ complete, and its complement is $\Pi^0_1$ complete.
• Fin is $\Sigma^0_2$ complete. So is the set of programs that compute non-total functions.
• The complement of Fin is the set of programs with infinite domain. This set is $\Pi^0_2$ complete. So is the set of programs that compute total functions.
• The set of programs whose domain is cofinite is $\Sigma^0_3$ complete. Its complement, the set of programs which diverge on an infinite set of inputs, is $\Pi^0_3$ complete.

Once you know these, you can use them to show other sets are at particular levels of the arithmetical hierarchy.

Answer 2

Carl has give a good general approach to questions of this sort, but let me give a possibly simpler answer for just the question you asked. Given any index $e$ for a Turing machine that takes no inputs (i.e., any index for a 0-ary partial recursive function), let $f(e)$ be an index for the machine that takes one input and does the following. On any input $x$, it first runs the machine with index $e$; if and when that halts, it outputs 0 (without even looking at its input $x$). There is a recursive $f$ that carries out this index manipulation. Notice that the domain $W_{f(e)}$ of the partial recursive function with index $f(e)$ is all of $\mathbb N$ if machine $e$ halts and is $\varnothing$ otherwise. In particular, $e$ does not halt if and only if $W_{f(e)}$ is finite. Thus, $f$ is a many-one reduction of the complement of the halting problem to Fin. Since the halting problem is r.e. but not recursive, its complement is not r.e., and therefore neither is Fin.