PCAs and Kleene's Recursion Theorem

Question

I might need some help with the following question.

Given a Partial Combinatory Algebra, we can define the fixed point combinator $Y := [\lambda^{*}xy.y(xxy)][\lambda^{*}xy.y(xxy)]$. How does this relate to Kleenes recursion theorem, aka. fixed point theorem?

In the setting of Kleenes first PCA, ie. the PCA of computable functions on $\mathbb{N}$, given a (partial) computable function $f = \varphi_c$ the fixed point combinator satisfies $Yc = c(Yc)$. As I understand it this means that taking d := Yc it translates to $f(d) = \varphi_c(d) = cd = d$, ie. $f$ having a fixed point.

However Kleene's recursion theorem originally gives a weaker assertion, namely that for every total computable function $g$ there is some $n$ such that $\varphi_{g(n)} \simeq \varphi_n$ (cf. Odifreddi - Classical Recursion Theory, Theorem II.2.10).

This really confuses me and I couldn't make up my mind what to do about it. I hope someone can help me out. Anyway, thank you for your time.

Answer 1

As I understand it this means that taking $d := Yc$ it translates to $f(d)=φ_{c}(d)=cd=d$, ie. $f$ having a fixed point.

Not every recursive function has a fixed point in the sense of $f(n)=n$ - for example, $f(n)=n+1$. Therefore, there must be something wrong with this proof. As noted in comments, this proof works only if $d=Y c$ is defined.

As you've noticed, you can work around this issue by using a variant of the Y combinator:

Just taking Ycc′=c(Yc)c′ doesn't seem to make your problem any better

But it does! To avoid confusion, I'll call this combinator Z. We have

$Zcc′=c(Zc)c′$.

Let's take a function $f=\varphi_c$ and let $d = Z c$, just like in the previous proof. Now, $d$ is guaranteed to be defined. We have

$d c' \equiv c d c'$

By the definition of application in the Kleene's first algebra this means:

$\varphi_{d}(c')$ $ \simeq \varphi_{\varphi_{c}(d)}(c')$

$\varphi_{d}(c')$ $ \simeq \varphi_{f(d)}(c')$

$\varphi_{d}$ $ \simeq \varphi_{f(d)}$

which is the Kleene's recursion theorem.

Well, literally the same problem arises in the proof of the Recursion theorem in Odifreddi's Classical Recursion Theory, Theorem II.2.10. There he takes $b$ to be a code satisfying $\varphi_{b}(e) \simeq f(\varphi_e(e))$.

No, $b$ is defined in Theorem II.2.10 using the equation:

$\varphi_{\varphi_{b}(e)} \simeq \varphi_{f(\varphi_e(e))}$

Importantly, $b$ is a code - it is a well-defined natural number that encodes a specific program. Furthermore, for every $e$, $\varphi_b(e)$ is also a code - it is not the result of running $f(\varphi_e(e))$, it is merely a code of a function which given $n$, runs the function $\varphi_{f(\varphi_e(e))}$ on $n$. (This difference mirrors the difference between Y and Z combinators.)