From Odifreddi's "Classical Recursion Theory", Vol 1., page 165.
The Fixed-Point Theorem can be used directly to find programs exhibiting self-referential features. E.g., by considering $f$ recursive such that $\varphi_{f(e)}(x) = e$ we get an index $e$ such that $\varphi_e(x) = e$ which can be interpreted as the code of a program printing itself.
Here is the statement of the theorem:
Fixed-point theorem
Given a recursive function $f$ there is an $e$ such that $\varphi_e \simeq \varphi_{f(e)}$, i.e. $e$ and $f(e)$ compute the same function.
To me it seems that the outlined procedure here is:
- pick a recursive $f$ such that $\varphi_{f(e)}(x) = e$
- take the $e'$ of the recursion theorem such that $\varphi_{e'} \simeq \varphi_{f(e')}$
- we get $\varphi_{e'}(x) = e'$, i.e. a quine
Why such an $f$ exist? Note that $f$ must be recursive.
Related but with other nuances
Does the recursion theorem give quines?
On the existence of an injective recursive function such that all its values are also its indexes.
Best Answer
Let $\psi$ be a recursive function (no need for partial recursive, because is just the projection function) such that: $\psi(x,y) = x$.
By the parameter theorem (S-m-n theorem), there exist a recursive function $f$ such that:
$$\phi_ {f(x)}(y) = \psi(x,y) = x.$$
As $f$ is recursive, by the fix-point theorem, it has a fix-point $e$, i.e. $\phi_{f(e)} = \phi_e$.
Then:
$$ \phi_e(y) = \psi(e,y) = e.$$
I think he is assuming this reasoning for the existence of $f$. Note that it don't matter witch constant you choose for $x$ before using the fix-point theorem (i.e. making $x=e$ we get $\phi_{f(e)}(x) = e$, the before-using-fix-point-theorem part on the Odifreddi text).