I've been thinking about how to show this but I'm stuck.
I'm required to prove this:
"Show that the language TOT={#M# | M is a Turing Machine that halts with all inputs} is not recursively enumerable nor its complement. (#M# is an encoded Turing Machine with only zeros and ones). "
I think we have to proceed by contradiction, assuming that T is recursively enumerable, so there must be a Turing Machine that we will call T such that it can process any possible encoding #M# of a TM M and only accept those machines that halt with all inputs.
So in order to confirm that TOT is r.e., T should be able to do this for every #M# that halts with all inputs. My idea is to show that this is not possible because the set TOT is not countable, so maybe I can show this using the diagonalization argument, but I'm not sure.
So what is the correct way to proof this?
Thanks
Best Answer
Whenever you approach one of these problems, the first thing to do is what Rogers calls a Tarski-Kuratowski computation: find the level of the arithmetical hierarchy where the set in question lives. In this case, we have that $e \in \text{Tot}$ if for every $n$ there exists an $s$ with $\phi_{e,s}(n)\downarrow$ (that is, $\phi_e(n)$ halts in $s$ steps). Therefore Tot is $\Pi^0_2$ and its complement is $\Sigma^0_2$.
So how can we diagonalize against Tot to show it is not computably enumerable? Well, we can use the leading $\forall$ quantifier in its definition, and the fact that the halting set $K$ is already $\Sigma^0_1$, to show that if Tot was $\Sigma^0_1$ then the halting set would be computable. Recall that, in general, a set is computable if both it and its complement are $\Sigma^0_1$, which is equivalent to the set and its complement both being $\Pi^0_1$.
Let $e$ be given. We want to tell whether $e \in K$, that is, whether $\phi_e(0)$ halts. Let $g$ be such that $g(s) = 0$ if $\phi_{e,s}(0)\uparrow$ and $g(s)$ diverges if $\phi_{e,s}(0)\downarrow$. Notice that $g$ is a partial computable function, and $g$ is total if and only if $\phi_e(0)\uparrow$, and we can compute an index $\gamma_e$ for $g$ uniformly from an index $e$. Therefore, we have $$ e \in K \leftrightarrow (\exists s)[\phi_{e,s}(0) \downarrow]\\ e \not \in K \leftrightarrow \gamma_e \in \text{Tot} $$ So, if Tot was computably enumerable, the two facts there the would show that $K$ is computable, which is impossible. The method here was to leverage the $\forall$ quantifier in Tot; if we had a way to decide membership in Tot, that gives us a "free pass" to decide that universal quantifier. The definition of $\gamma_e$ leverages the universal quantifier to tell whether $\phi_e(0)$ does not halt.
How can we show that Tot is not $\Pi^0_1$? Well, we can use the inner $\exists$ quantifier in the definition of Tot, and the fact that the complement $\bar K$ of the halting problem is not computable. In the first part we used Tot to tell whether $\phi_e(0)\uparrow$. Now we will use Tot to tell whether $\phi_e(0)\downarrow$. Given $e$, let $h(x) = \mu s [\phi_{e,s}(0) \downarrow]$. Then $h$ is total if and only if $\phi_e(0)\downarrow$, which is equivalent to $e \not \in \bar K$. Also, we can compute an index $\eta(e)$ for $h$ uniformly from $e$. Thus: $$ e \in \bar K \leftrightarrow (\forall s)[\phi_{e,s}(0)\uparrow]\\ e \not \in \bar K \leftrightarrow \eta(e) \in \text{Tot} $$ Therefore, if $\text{Tot}$ was $\Pi^0_1$ then $\bar K$ would be computable, which is impossible.