5
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .