Question in the Proof of the Recursion theorem - why is $d(u)$ total Recursive?

37 Views Asked by At

I saw a proof for the Recursion Theorem (Fixed Point Theorem), in Soare's book, Recursively Enumerable Sets and Degrees (pag. 36), and I didn't understand something.

So the theorem states, that if $f$ is a recursive function, then there is a natural number, $n$, such that $\varphi_n = \varphi_{f(n)}$, where $\varphi$ denotes the enumeration of the Partial Recursive functions.

In the proof, he defines a function, $d(u)$, in the following manner: $$ \varphi_{d(u)}(z) = \begin{cases} \varphi_{\varphi_u(u)}(z) & \varphi_u(u)\downarrow\\\ \uparrow & o.w. \end{cases}$$

The part I don't understand, is why $d(u)$ is a $1:1$ total Recursive function, as stated in the book. Aparently it's due to the $s$-$m$-$n$ theorem, by I don't really understand why. If $\varphi_1(1)$ doesn't halt, wouldn't $d(1)$ not halt as well?

So my question is why $d(u)$ is a total Recursive function, and how one can prove that from the $s$-$m$-$n$ theorem.