Theorem II.5.8 in P. Odifreddi's Classical Recursion Theory states that
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:
- 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.
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.
