Prove that $\{p: U(p,p)\downarrow\}\equiv_m K_e=\{p:\phi_p()\downarrow\}$

50 Views Asked by At

Let $U$ be a universal function for the class of computable functions of one argument. This means $U:N\times N\to N$ is a partial computable function, and for any partial computable $f$ of one argument, $f(x)=U(n,x)$ for some $n$.

Let $$K=\{p\in N: U(p,p)\downarrow\}\\ K_1=\{\pi(p,x)\in N:U(p,x)\downarrow\}$$ where $\pi$ is the Cantor pairing function.

Also let $K_e=\{p\in N:\phi_p()\downarrow\}$ where $\phi_p$ is the function defined by the program with number $p$. So above, $U(p,x)=\phi_p(x)$.

I proved that $K$ and $K_1$ are $m$-reducible to each other. In the proof I used the method I demonstrated here. I'm trying to show that $K_e$ is also $m$-reducible to, say, $K$.

First I'm wondering how to write $\phi_p()$ using universal functions (if it's possible). I would need a universal function for the class of computable functions of 0 arguments. That would be a partial computable function $\widetilde U : N\to N$ such that for any computable function of zero arguments (I guess $\emptyset\to N$ ?) $\widetilde U(n)=??$. This doesn't make sense to me.

If it's not possible to write that condition using univesal functions, I don't know how to prove the equvalence. As I mentioned, I used the existence of Godel universal functions (see the link above) to prove the $m$-equivalence of $K$ and $K_1$ and I'm not sure how to avoid using it.