Is the set {i | $\phi_i$ is total } recursively enumerable?

Question

Is the set {i | $\phi_i$ is total } recursively enumerable?

and can you please tell me why ?

Bests Norman

Answer 1

No, its not by the theorem of Rice-Shapiro:

Let $A$ be a class of monadic partial recursive functions whose corresponding index set ${\rm prog}(A) = \{x\in{\Bbb N}_0\mid \phi_x\in A\}$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g \in A$ such that $g \subseteq f$ (i.e., $f$ is an extension of $g$).

If the set $A=\{x\mid \phi_x\mbox{ total}\}$ given is r.e., it will contain finite functions (functions with finite domain), which is not possible.