2

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.

Carl Mummert
  • 81,604
Daniel
  • 6,999
  • Once you learn the general method for finding the exact level of the arithmetical hierarchy, you'll see that Rice's theorem is like wrecking ball, incapable of doing precision work, while more advanced methods related to the arithmetical hierarchy and Post's theroem allow for much more precise characterizations of sets. – Carl Mummert Oct 01 '16 at 16:18
  • @Carl Thanks. We'll probably learn about that in the next few classes. It actually makes sense to break your head with Rice's theorem for a while before we learn more advanced methods, it help us see the usefulness of more advanced methods. – Daniel Oct 01 '16 at 16:32
  • Another theorem that solves this directly is Rice-Shapiro. Of course, it does not give as much information as Carl's very nice answer, but it gives a complete characterization of the r.e. sets of indices. What I don't know is whether this theorem follows as an easy consequence from the results on the arithmetical hierarchy. – Keplerto Jul 21 '23 at 14:53

2 Answers2

3

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.

Carl Mummert
  • 81,604
  • And a $\Sigma^0_2$ hard set can't be $\Sigma^0_1$ since there are other known sets in $\Sigma^0_2$ that are not in $\Sigma^0_1$, right? I could build the program for the last part, thanks! – Daniel Oct 01 '16 at 16:28
  • Right. Post's theorem says that for every $n$ there are $\Sigma^0_{n+1}$ sets that are not $\Sigma^0_n$, and so in particular $\Sigma^0_{n+1}$ hard sets cannot be $\Sigma^0_n$. In particular, Post showed that for each $n$ the $n$th Turing jump of the empty set is $\Sigma^0_{n}$ complete. – Carl Mummert Oct 01 '16 at 16:30
  • Thanks a lot Carl, I'll be looking forward to learn these topics on class. However, I want to give an "elementary" proof of the fact that Fin is no r.e. ("elementary" in the sense that it only uses things I've learned so far). Your argument works quite well, I only need to show the existence of a different $\Sigma^0_2$ problem that's not $\Sigma^0_1$. Can you think in one of these problems? – Daniel Oct 01 '16 at 16:36
  • 1
    The set of total functions is another one. But you can also do a more direct diagonalization to show that the set Fin is not r.e., without computing the level the set is at. This uses the recursion theorem. Assume that Fin is r.e, and let $e$ be a program that enumerates the indices that are supposed to have finite domains. Let $j$ be a program that knows its own index and watches the enumeration given by $e$. Make $j$ respond in such a way that if $j$ is ever enumerated then $j$ causes itself to have an infinite domain, while if $j$ is not enumerated then $j$ will have a finite domain. – Carl Mummert Oct 01 '16 at 16:41
  • I meant "non-total functions". The diagonalization has the property that it does not require any knowledge of many-one reductions, just the recursion theorem. But, like Rice's theorem, it gives less information. – Carl Mummert Oct 01 '16 at 16:47
  • Thanks for this comment, as you mention, it's a direct approach but we obtain less information from it. However, it suffices my current requirements. In any case, thanks a lot for you answer above, it gave a grasp of new types of proofs, and how the levels of the hierarchy can be useful. – Daniel Oct 01 '16 at 20:02
3

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.

Andreas Blass
  • 71,833
  • Thanks for your answer Andreas! this is closer to what I was looking for: I more direct proof using tools like reductions. Also, Carl's answer has been extremely instructive too! – Daniel Oct 01 '16 at 19:59