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:

  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.


1 Answer 1


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$$

  • $\begingroup$ I was occupied by this problem so much for some past weeks so that the simplicity of this solution makes me doubtful about its validity. It's also questioning why no where I could find it, specially in the mentioned books. So I will wait for feed back before accepting the answer. $\endgroup$
    – Beleg
    May 13, 2018 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.