When does an extendible 1:1 p.c. function have a 1:1 computable extension?
-
05-11-2019 - |
题
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:
Obviously, $\varphi_e$ itself should be injective.
$|\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.
没有正确的解决方案