2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here is an example of an extendible, non-injectively-extendible p.c. function $\psi$ which nonetheless satisfies your conditions (and I think indicates in general that any sufficient condition will be quite complicated):

Let $\langle\cdot,\cdot\rangle$ be your favorite computable bijection $\mathbb{N}^2\rightarrow\mathbb{N}$. We define $\psi$ as follows (with the role of "$2^k$" being merely to control the range of $\psi$, and consequently show that just demanding that the range be "small" won't yield a sufficient condition):

  • Suppose $k$ is even. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$. We define $\psi(k)$ to be $2^k$ if $\varphi_{a_k}(a_k)$ halts strictly before $\varphi_{b_k}(b_k)$ does, and we let $\psi(k)$ be undefined otherwise.

  • Suppose $k$ is odd. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$+1. We define $\psi(k)$ to be $2^{k-1}$ if $\varphi_{b_k}(b_k)$ halts strictly before $\varphi_{a_k}(a_k)$ does, and we let $\psi(k)$ be undefined otherwise.

$\psi$ is clearly 1-1, p.c., of co-infinite range (indeed, the range is "computably coinfinite" in the sense that the complement of the range contains an infinite computable set; in jargon, the range of $\psi$ is non-simple), and extendible: it is extended by the function $x\mapsto 2^{2floor({x\over 2})}$. However, it's easy to show that it's not extendible to a 1-1 total computable function, essentially since such an extension would have to always guess correctly whether one program halts before another does.

$\endgroup$

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.