How to prove that "Total" is not recursive (decidable)

Question

$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable.

$\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable).

I need some help in proving that $\mathrm{Total}$ is not recursive (decidable).

I know the diagonalization proof for the halting problem, I just need the same kind of proof for $\mathrm{Total}$. I'm posting the proof for the halting problem for reference:

Undecidability of the halting problem

Assume we can decide the halting problem. Then there exists some total function $\mathrm{Halt}$ such that $$ \mathrm{Halt}(x,y) = \begin{cases} 1 & \text{if $\phi_x(y)$ is defined}, \\ 0 & \text{if $\phi_x(y)$ is not defined}.\end{cases} $$

Here, we have numbered all programs and $\phi_x$ refers to the $x$'th program in this ordering. We can view $\mathrm{Halt}$ as a mapping from $\mathbb{N}$ into $\mathbb{N}$ by treating its input as a single number representing the pairing of two numbers via the one-one onto function $$ \mathrm{pair}(x,y) = \langle x,y \rangle = 2^x (2y + 1) – 1 , $$ with inverses $$ \begin{align*} \langle z \rangle_1 &= \exp(z+1,1), \\ \langle z \rangle_2 &= ((( z + 1 ) // 2^{\langle z \rangle_1}) – 1 ) // 2 \end{align*} $$ Now if $\mathrm{Halt}$ exists, then so does $\mathrm{Disagree}$, where $$ \mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Halt}(x,x)=0$, i.e., if $\phi_x(x)$ is not defined}, \\ \operatorname*{\mu}_y (y=y+1) & \text{if $\mathrm{Halt}(x,x)=1$, i.e., if $\phi_x(x)$ is defined}. \end{cases} $$

Since $\mathrm{Disagree}$ is a program from $\mathbb{N}$ into $\mathbb{N}$, $\mathrm{Disagree}$ can be reasoned about by $\mathrm{Halt}$. Let $d$ be such that $\mathrm{Disagree} = \phi_d$, then

$$\mathrm{Disagree}(d)\text{ is defined} \Leftrightarrow \mathrm{Halt}(d,d) = 0 \Leftrightarrow Φ_d(d)\text{ is undefined} ⇔ \mathrm{Disagree}(d)\text{ is undefined}.$$

But this means that $\mathrm{Disagree}$ contradicts its own existence. Since every step we took was constructive, except for the original assumption, we must presume that the original assumption was in error. Thus, the halting problem is not decidable.

Answer 1

A set $A$ is recursive iff $A$ is recursive enumerable and $A^c$ is recursive enumerable. You know that $Halt$ is recursive enumerable but not recursive so $Halt^c$ must not be recursive enumerable. You can show that $Total$ is not recursive enumerable (and therefore not recursive) by showing that it is reducible from $Halt^c$.

Formally, to show that $Halt^c \leq_M Total$ you need to find a total computable function $f$ such that $$x \in Halt^c \Leftrightarrow f(x) \in Total$$

Answer 2

We would like to modify the proof above by defining $$ \mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Total}(d)=0$}, \\ \operatorname*{\mu}_y (y=y+1) & \text{if $\mathrm{Total}(d)=1$}, \end{cases} $$ where $\mathrm{Disagree} = \phi_d$. The problem is, how can a program know its own number? This is taken care of by the recursion theorem, a classical theorem in recursion theory. The idea extends further to prove Rice's theorem, a generalization of the undecidability of both $\mathrm{Halt}$ and $\mathrm{Total}$.

I should mention that $\mathrm{Total}$ is in fact harder than $\mathrm{Halt}$: even given an oracle to $\mathrm{Halt}$, $\mathrm{Total}$ is undecidable. In terms of the arithmetical hierarchy, $\mathrm{Halt}$ is $\Sigma_1$-complete and $\mathrm{Total}$ is $\Pi_2$-complete.