I'm going through a textbook and the recursion theorem was introduced. The proof is a bit all over the place and kind of hard to follow so I thought I'd ask my question here. The theorem, as stated in my book, goes as follows:
Let $G$ be a partially recursive function of $(k+1)$ parameters. Then there exists $e\in\mathbb N$ such that $\{e\}^k(\vec x)\simeq G(e, \vec x)$
Here $\{e\}^k(x)$ denotes the result of applying $k$ to the function encoded in $e$.
But does the proof of the theorem give me a way to actually compute the $e$ for some $G$? Say we have $G(x, y)=x+y$. What this would basically amount to is a program that adds it's own index to the argument that was given to it.
I tried playing around with this specific example but it seems like the size of the program (and hence its index) grow much faster than what the resulting code can add to its argument.
Yes, the recursion theorem tells you how to find fixed points. Let's look at the case $k=0$ for simplicity.
The proof of the recursion theorem goes as follows:
Let $t$ be a total recursive function such that $\Phi_{t(d)}=\Phi_{\Phi_d(d)}$ whenever $\Phi_d(d)$ is defined, and $\Phi_{t(d)}$ is a never-halting function otherwise. Building such a function is a standard exercise.
Let $d$ be the index of the recursive function $G$ you're trying to find a fixed point for.
Then we have $$\Phi_{t([G\circ t])}(x)=\Phi_{\Phi_{G\circ t}([G\circ t])}=\Phi_{G(t([G\circ t]))}$$ (where "$[F]$" is a code for the recursive function $F$). This means that $t([G\circ t])$ is a fixed point of $G$.