# Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional?

If $\{\psi_e\}_{e\in\omega}$ is an acceptable system of indices, then there is a recursive permutation $h$ such that $$h(\psi_e(x)) = \varphi_{h(e)}(h(x)) .$$

where $\varphi$ is the standard enumeration of p.c. functions.

My question is whether the converse case holds: For the standard enumeration $\varphi$, some permutation $h$ and some computable enumeration of p.c. functions $\psi$, if we have $h(\psi_e(x)) = \varphi_{h(e)}(h(x))$, then $\psi$ is an acceptable enumeration.

Some possible approaches:

1. Prove this simpler form and then prove it is equivalent to question:

For some computable permutation $h$ and standard enumeration $\varphi$, $\theta_e(x) = h(\varphi_e(x))$ is also an acceptable enumeration.

1. H. Rogers' Theory of Recursive Functions p54, defines a universal partial function to be a partial computable function $\psi$ for which exists a computable function $f$ of two variables, such that $\forall x; \varphi_x = \lambda y.\psi f(x,y)$. So $f$ codes both index and argument and $\psi$ takes it as its single input. Then it proves that

If $\psi$ is universal and $g$ and $h$ are recursive permutations, then $\eta = g^{-1}\psi h$ is universal.

Is this statement, for $g=h$, equivalent to the mentioned converse above?

It seemed very obvious to me at first, though I couldn't manage to prove it. What am I possibly missing?

Update Removed the second question as an intermediate approach to solve the main question.

For the standard enumeration $\varphi$ and some computable permutation $h$, $$\forall e;~ \psi_e = h^{-1} \varphi_{h(e)}h ~~~~(*)$$
We want to prove that such $\psi$ is an acceptable enumeration. It suffices to find computable functions $f$ and $g$ such that for all $e$, $\psi_e = \varphi_{f(e)}$ and $\varphi_e = \psi_{g(e)}$.
$h^{-1} \varphi_{h(e)}h$ is partial computable. So by s-m-n theorem, there is a computable function $f$ such that for all $e$, $h^{-1} \varphi_{h(e)}h = \varphi_{f(e)}$, therefor by $*$ we have, $\psi_e = \varphi_{f(e)}$
$h \varphi_e h^{-1}$ is also partial computable. So again by s-m-n theorem, there is computable $g'$ such that for all $e$, $h \varphi_e h^{-1} = \varphi_{g'(e)}$. Define computable function $g$ as $g = h^{-1} g'$. In $*$ replace $e$ with $g(e)$ to get $$\psi_{g(e)} = h^{-1} \varphi_{hg(e)}h ~.$$ By definition of $g$, we have $h g = h h^{-1} g' = g'$, so $$\psi_{g(e)} = h^{-1} \varphi_{g'(e)}h ~.$$ By definition of $g'$ $$\psi_{g(e)} = h^{-1} h \varphi_e h^{-1} h ~,$$ and thus $$\psi_{g(e)} = \varphi_e ~. ~~\Box$$