Finding the image in a computable way

Question

Suppose we have a partial computable injective function $f: \mathbb N\to \mathbb N$ whose image is computable. I'm trying to show that then the image of every computable set is computable, and that this is false for non-injective functions (by a counterexample).

Suppose $X$ is computable and one wants to check if $y$ lies in $f(X)$. The problem asks to construct an algorithm of how to do this. What I can think of is this: the algorithm accepts $y$. Since $im(f)$ is computable, we one can tell whether $y\in im(f)$. If this is false, then $y\notin f(X)$ either. Suppose $y\in im(f)$. Then for some $x\in dom(f)$, $f(x)=y$. Now it would be natural to find such an $x$ (which would be unique due to injectivity). (And then one would be able to tell whether $x\in X$ or not.) But how to find an algorithm/program doing this? The domain of $f$ may be infinite, so it may be not possible (in finite time) to check for every $x\in dom(f)$ if $f(x)=y$. Also I don't see how the computability of $f$ can be used here.

As for the counterexample, once I understand how to find $x$ with $f(x)=y$, the most trivial counterexample should work, like $\{1,2\}\to \mathbb N, 1,2\mapsto 1$. Is that right?

Answer 1

For the first problem, you have the right idea. In fact in your question you have already given an informal description of an algorithm to compute $f(X)$.

Here's the part you seem confused by: you have some $y$ which you know to be in the range of $f$ and you want to find $x$ such that $f(x) = y$. Yes, there are infinitely many possible $x$'s, but the point is that if you start searching for one, eventually you will be successful because you know that such an $x$ exists. The one tricky part is that since $f$ is a partial function, you may run into some candidate $x$'s where $f(x)$ does not converge. The answer is just to try them out in parallel.

Here's what I mean: first check if $f(0)$ converges in one step of computation. Then check if either $f(0)$ or $f(1)$ converge in two steps of computation. Then check if any of $f(0)$, $f(1)$, and $f(2)$ in three steps. Etc. Eventually you will see some $f(x)$ converge and equal $y$ then you can stop the search. Once again, the search is guaranteed to stop after a finite number of steps because $y$ is in the range of $f$.

The ability to perform this kind of unbounded search is what makes computation stronger than e.g. primitive recursion.

For your second problem, nothing with finite range will work because the image of any set will be finite, and therefore computable.

One way to find a counterexample is to recall that every r.e. set is the image of a partial computable function. Start with a partial computable function whose range is a noncomputable r.e. set. Then modify this function in some way so that its range becomes computable but knowing its image on some particular set would tell you the original r.e. set. Or you can just do it by some kind of direct diagonalization.