Corollary of Kleene's recursion theorem - can we find a constructive proof? It is not a homework assignment, rather it is a question arising from teaching myself.
In a lecture note by Weber, following statement gives as a corollary of Kleene's recursion theorem:

For total computable function $f$ there is infinitely many $n$ s.t. $\phi_{f(n)} = \phi_n$.

My attempt of a proof is as follows: We shall show that, for each $N\in \Bbb{N}$ there is $n>N$ s.t. $\phi_{f(n)} = \phi_n$. Take $k\in \Bbb{N}$ satisfying $\phi_k \neq \phi_n$ for all $n\le N$. Such $k$ exists since there are countably many distinct computable functions.
For such $k$, define $g$ as
$$g(n) = \begin{cases} k & \text{if } n\le N \\ f(n)&\text{otherwise}\end{cases}.$$
$g$ is totally computable, and there is $n$ s.t. $\phi_n = \phi_{g(n)}$. But if $n\le N$, then $\phi_n = \phi_k$, a contradiction. Thus $n>N$.
I believe my proof is right. However I think my proof is nonconstructive in the sense that the procedure finding $k$ is not constructive. My questions are:


*

*Is my proof correct?

*Is there a constuctive proof (that is, a proof providing how to calculate such $n$ to given $N$) of the statement?
 A: The proof you gave seems fine to me. It does require a choice of $k$ that is not uniformly computable from $n$. 
There is a constructive proof of the corollary, in the specific sense that if $f\colon \mathbb{N}\to\mathbb{N}$ is total computable then there is an infinite r.e. set of fixed points for $f$. To make this set, begin with the proof by Weber. 
Given $N$, we can replace her function $s$ with a function $s_N$ which has the added property that its output is always larger than $N$. This is because, by padding, we can enumerate (uniformly) an infinite r.e. set of equivalent indices for any given index, and thus we can ensure that the index returned by $s$ is not too small. 
Now, lower in the proof, we take $m$ to be an index of $s_N$, and we take $$n = \phi_m(m) = s_N(m) > N.$$ 
The key point here is that the s-m-n theorem can be tweaked to give an infinite r.e. set of indices instead of a single index. This is because we can always pad an algorithm to do some useless operations before doing what we really want. Adding useless extra instructions will give a different index, but the index will compute the same function as long as we do it carefully. Thus many other theorems that appeal to the s-m-n theorem can also be modified to give an infinite set of indices. 
