Question

A partial computable function $\varphi_e$, defined on a c.e. set $W_e$, is called extendible if there exists some computable function $f$ which extends $\varphi_e$, i.e. $\varphi_e(W_e) = f(W_e)$.
My question is what are the conditions for a p.c. function $\varphi_e$ to have an injective extension.

So far I have found some necessary conditions:

  1. Obviously, $\varphi_e$ itself should be injective.

  2. $|\overline{W_e}| \leq |\overline{\varphi_e(W_e)}|$. Because $f(\overline{W_e})$ should have no intersection with $f(W_e) = \varphi_e(W_e)$, so $f(\overline{W_e}) \subseteq \overline{\varphi_e(W_e)}$.
    This rules out $\varphi_e(x) = x/2$, defined on even numbers. And also any other surjective partial function.

I couldn't manage to find a sufficient condition yet.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top